Static Perfect Hashing

Flashcards by msladey, updated more than 1 year ago
Created by msladey almost 6 years ago



Resource summary

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]
Show full summary Hide full summary


Hash Functions
Cuckoo Hashing
Lowest Common Ancestor
Data Structures & Algorithms
Reuben Caruana
Data Structures & Algorithms
Martyn Haigh
Computer science unit 2
Somto Ibeme
Algorithms ♡
lauren ♥
Computational Thinking ♡
lauren ♥
Searching and Sorting Algorithms
Josh Calvert
Systems Software Revision
Grafy I.
Michal Roch