hashing item hop item hop item hop figure hopscotch hashing table insertion of continuesnextb is evictedand finallywe have spot that is close enough to the hash value and can insert universal hashing although hash tables are very efficient and have constant average cost per operationassuming appropriate load factorstheir analysis and performance depend on the hash function having two fundamental properties the hash function must be computable in constant time ( independent of the number of items in the hash table the hash function must distribute its items uniformly among the array slots in particularif the hash function is poorthen all bets are offand the cost per operation can be linear in this sectionwe discuss universal hash functionswhich allow us to choose the hash function randomly in such way that condition above is satisfied as in section we use to represent tablesize although strong motivation for the use of universal hash functions is to provide theoretical justification for the assumptions used in the classic hash table analysesthese functions can also be used in applications that require high level of robustnessin which worst-case (or even substantially degradedperformanceperhaps based on inputs generated by saboteur or hackersimply cannot be tolerated as in section we use to represent tablesize definition family of hash functions is universalif for any ythe number of hash functions in for which (xh(yis at most | |/ notice that this definition holds for each pair of itemsrather than being averaged over all pairs of items the definition above means that if we choose hash function randomly from universal family hthen the probability of collision between any two distinct items