Static Perfect Hashing

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

Description

Revision

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

Similar

Hash Functions
msladey
Cuckoo Hashing
msladey
Lowest Common Ancestor
msladey
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
cocacolai
Grafy I.
Michal Roch