hashing item hop figure hopscotch hashing table the hops tell which of the positions in the block are occupied with cells containing this hash value thus hop[ indicates that only position currently contains items whose hash value is while positions and do not failsince there would now be max_dist items trying to reside within max_dist positions of pos--an impossibility continuing the examplesuppose we now insert item with hash value our normal linear probing would try to place it in position but that is too far from the hash value of so insteadwe look to evict an item and relocate it to position the only candidates to go into position would be items with hash value of or if we examine hop[ ]we see that there are no candidates with hash value but hop[ produces candidategwith value that can be placed into position since position is now close enough to the hash value of hwe can now insert these stepsalong with the changes to the hop informationare shown in figure finallywe will attempt to insert whose hash value is linear probing suggests position but of course that is too far away thus we look in hop[ ]and it tells us that can move downfreeing up position now that is vacantwe can look in hop[ to find another element to evict but hop[ has all zeros in the first three positionsso there are no items with hash value that can be moved so we examine hop[ there we find all zeros in the first two positions so we try hop[ ]where we need the first position to be which it is thus can move down these two steps are shown in figure notice that if this were not the case--for instance if hash(fwere instead of --we would be stuck and have to rehash howeverthat is not problem with our algorithminsteadthere would simply be no way to place all of ciadebhand (if ' hash value were )these items would all have hash values between and and would thus need to be placed in the seven spots between and but that would be eight items in seven spots--an impossibility howeversince this is not the case for our exampleand we have evicted an item from position we can now continue figure shows the remaining eviction from position and subsequent placement of