howevercuckoo hashing is extremely sensitive to the choice of hash functionsthe inventors of the cuckoo hash table reported that many of the standard hash functions that they attempted performed poorly in tests furthermorealthough the insertion time is expected to be constant time as long as the load factor is below the bound that has been shown for the expected insertion cost for classic cuckoo hashing with two separate tables (both with load factor lis roughly /( ( ) / )which deteriorates rapidly as the load factor gets close to (the formula itself makes no sense when equals or exceeds using lower load factors or more than two hash functions seems like reasonable alternative hopscotch hashing hopscotch hashing is new algorithm that tries to improve on the classic linear probing algorithm recall that in linear probingcells are tried in sequential orderstarting from the hash location because of primary and secondary clusteringthis sequence can be long on average as the table gets loadedand thus many improvements such as quadratic probingdouble hashingand so forthhave been proposed to reduce the number of collisions howeveron some modern architecturesthe locality produced by probing adjacent cells is more significant factor than the extra probesand linear probing can still be practical or even best choice the idea of hopscotch hashing is to bound the maximal length of the probe sequence by predetermined constant that is optimized to the underlying computer' architecture doing so would give constant-time lookups in the worst caseand like cuckoo hashingthe lookup could be parallelized to simultaneously check the bounded set of possible locations if an insertion would place new item too far from its hash locationthen we efficiently go backward toward the hash locationevicting potential items if we are carefulthe evictions can be done quickly and guarantee that those evicted are not placed too far from their hash locations the algorithm is deterministic in that given hash functioneither the items can be evicted or they can' the latter case implies that the table is likely too crowdedand rehash is in orderbut this would happen only at extremely high load factorsexceeding for table with load factor of the failure probability is almost zero (exercise let max_dist be the chosen bound on the maximum probe sequence this means that item must be found somewhere in the max_dist positions listed in hash( )hash( hash( (max_dist in order to efficiently process evictionswe maintain information that tells for each position xwhether the item in the alternate position is occupied by an element that hashes to position as an examplefigure shows fairly crowded hopscotch hash tableusing max_dist the bit array for position shows that only position has an item (cwith hash value only the first bit of hop[ is set hop[ has the first two bits setindicating that positions and ( and dare occupied with items whose hash value is and hop[ has only the third bit setindicating that the item in position (ehas hash value if max_dist is no more than the hop array is essentially an array of -bit integersso the additional space requirement is not substantial if hop[poscontains all for some posthen an attempt to insert an item whose hash value is pos will clearly