2806293
| Question | Answer |
| What is the difference between a static dictionary and a dynamic dictionary? | A static dictionary is not allowed inserts or deletes. |
| How many collisions can we expect from the FKS Hashing Scheme? | None |
| What is the worst case lookup time for the FKS Hashing Scheme? | O(1) |
| Explain the FKS Hashing Scheme | Insert 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. |
| How much space does the FKS hashing scheme use? | O(n) |
| What is the preprocessing time for the FKS hashing scheme? | O(n) |
| How 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] |
Want to create your own Flashcards for free with GoConqr? Learn more.