Flashcards on Hash Tables: Efficient Dictionary Data Structures
Hash Tables: Efficient Dictionary Data Structures Guide
Tap to flip · Swipe to navigate
Perfect Hashing
20 cards
Card 1
Question: What is the definition of perfect hashing in terms of memory accesses for search in the worst case?
Answer: A hashing technique is called perfect hashing if O(1) memory accesses are required to perform a search in the worst case.
Card 2
Question: What two-level structure is used to achieve perfect hashing?
Answer: Two levels of hashing: an outer (first-level) hash that distributes keys into m slots and, for each slot j, a small secondary hash table S_j with its
Card 3
Question: How are keys distributed at the first level in perfect hashing?
Answer: The n keys are hashed into m slots using a single first-level hash function h chosen from a universal family; keys that hash to slot j are handled by
Card 4
Question: What is the purpose of the secondary hash tables S_j in perfect hashing?
Answer: Each secondary table S_j stores all keys hashing to slot j using a carefully chosen hash function h_j so that there are no collisions within S_j.
Card 5
Question: How large is each secondary table S_j relative to the number n_j of keys assigned to slot j?
Answer: The size m_j of S_j is set to m_j = n_j^2 (the square of the number n_j of keys hashing to slot j).
Card 6
Question: Why is it acceptable to make each secondary table size quadratic (n_j^2) when that seems large?
Answer: Although m_j is quadratic in n_j, by choosing the first-level hash function carefully (from a universal family) we can limit the expected total space
Card 7
Question: What family of hash functions is used for the first-level hash in the described perfect hashing scheme?
Answer: The first-level hash function comes from the universal class H_{p,m}, where p is a prime greater than any key value, and h(k) = ((a k + b) mod p) mod
Card 8
Question: How does choosing hash functions from universal families help in perfect hashing?
Answer: Using universal hashing at both the first and secondary levels enables probabilistic guarantees that secondary tables can be made collision-free and k
Card 9
Question: What worst-case search time does perfect hashing guarantee and why?
Answer: It guarantees worst-case O(1) search time because each key is stored in a secondary table with no collisions, so locating it requires a constant numbe
Card 10
Question: In the example given, what are the roles of parameters a, b, p, and m in the outer hash function h?
Answer: They define the outer hash h(k) = ((a k + b) mod p) mod m; a and b are chosen constants, p is a prime > any key, and m is the number of first-level sl