A weakness of hashing Problem: For any hash function h, a set of keys exists that can cause the average access time of a hash table to skyrocket An adversary can pick all keys from kEU: h(k)=i for some slot i IDEA: Choose the hash function at random independently of the keys Even if an adversary can see your code, he or she cannot find a bad set of keys since he or she doesn ' t know exactly which hash function will be chosen o 2001 by Charles E Leiserson Introduction to Algorithms Day 12 L8.2© 2001 by Charles E. Leiserson Introduction to Algorithms Day 12 L8.2 A weakness of hashing Problem: For any hash function h, a set of keys exists that can cause the average access time of a hash table to skyrocket. IDEA: Choose the hash function at random, independently of the keys. • Even if an adversary can see your code, he or she cannot find a bad set of keys, since he or she doesn’t know exactly which hash function will be chosen. • An adversary can pick all keys from {k ∈ U : h(k) = i} for some slot i