Flashcards
Static Perfect Hashing
Cards in this deck (7)
- 1What is the difference between a static dictionary and a dynamic dictionary?A static dictionary is not allowed inserts or deletes.
- 2How many collisions can we expect from the FKS Hashing Scheme?None
- 3What is the worst case lookup time for the FKS Hashing Scheme?O(1)
- 4Explain the FKS Hashing SchemeInsert everything into hash table T of size n using a weakly universal hash function.
The ni items in T[i] are inserted into another hash table Ti of size ni^2 using w.u hash function hi.
Immediately repeat if either T has more than n collisions, or some Ti has a collision. - 5How much space does the FKS hashing scheme use?O(n)
- 6What is the preprocessing time for the FKS hashing scheme?O(n)
- 7How do we perform a lookup in the FKS Hashing scheme?1. Compute i = h(x)
2. Compute j = hi(x)
3. The item is in Ti[j]