Hashing Flashcards
(21 cards)
What are the two main types of access structures discussed?
Direct access structures and linear access structures
What is a major disadvantage of direct access structures?
Need to allocate size in advance
What issue arises when overestimating the size of a direct access structure?
Ends up with a very sparse structure
In hash tables, how is a key k stored?
Stored in slot hash(k)
What is the function that maps the universe of keys into the slots of a hash table?
h : U –> {0,1,…,m-1} where m is the size of the table
What is a characteristic of a good hash function?
Satisfies the assumption of uniform hashing
What is the division method based on in hash functions?
Where m is the size of the hash table
What is a good choice for the size m of a hash table?
Prime numbers that are close to n divided by the number of desired average probes
What does the multiplication method depend on?
A constant A between 0 and 1
What is the importance of order preservation in hash functions?
Similar to the stability property in sorting
What are the two classes of collision resolution in hash tables?
- Separate chaining
- Open addressing
What does separate chaining involve?
Mixing linked lists and direct access structures
What happens when a collision occurs in a hash table using separate chaining?
The new key is stored in the linked list at that location
What is the purpose of the hash function h(k) = k mod size?
To create hash values for integer keys
What is the worst-case performance of hash search?
O(n)
What is the average-case performance of hash search if m = O(n)?
O(1)
What does linear probing suffer from?
Primary clustering
What is a technique used in open addressing that involves adding a squared term?
Quadratic probing
What is the risk associated with random probing?
Suffers from secondary clustering
What is rehashing in the context of hash tables?
A technique where a sequence of hashing functions is used in order
What is the method to search for a target in a hash table?
Hash the target and search in the linked list at the corresponding slot
