hash maps Flashcards
(27 cards)
What data can be stored in an abstract data type?
Stores collection of (key, value) pairs
Each possible key appears at most once and allows access to elements using a key.
What is the insert operation in an abstract data type?
Adds a new (key, value) pair to the collection, mapping the key to its new value
Any existing mapping is overwritten.
What does the remove operation do in an abstract data type?
Removes a (key, value) pair from the collection, unmapping a given key from its value.
What is the search operation in an abstract data type?
Finds the value of the corresponding key and returns its value
If no value exists, returns a default value like zero or null.
What is a hash table?
Uses a hash function to map a universe of keys to slots on the hash table.
What is the time complexity of searching in a hash table with chaining?
Θ(1 + α) under the assumption of simple uniform hashing.
What is a direct address table?
An array where each slot corresponds to a key in the universe of keys.
How does the delete operation work in a direct address table?
Sets T[x.key] = NULL.
What is the load factor of a hash table?
α = n / m
Load factor is the average number of elements per slot.
What is simple uniform hashing?
Each key is equally likely to hash to an integer between 0 and m - 1.
What happens when a collision occurs in a hash table?
Two keys map to the same location in the hash table.
What are the methods to resolve collisions in a hash table?
- Chaining
- Linear probing
- Quadratic probing
What is chaining in hash tables?
All keys that hash to the same slot are placed into the same linked list.
What is linear probing?
Places the element in the next available slot.
What is quadratic probing?
Adds a function of i to the hash value.
What is the consequence of a high load factor in hash tables with chaining?
Increased look-up time due to long linked lists.
True or False: Hash functions should be collision resistant.
True.
What is a perfect hash function?
Injective hash function where every element in S maps to a different value.
What is the hashing function for linear probing?
H(k,i) = h’(k) + i mod m for i = 0, …, m - 1.
What are the pros of chaining in hash tables?
- No need for resizing
- Simple to implement
What are the cons of chaining in hash tables?
Increased look-up time in the worst case.
What is the expected value of the list length nj in simple uniform hashing?
Expected value of nj is α.
What is the probing number in probing hash tables?
A second input to the hash function.
What is primary clustering in linear probing?
Many collisions can lead to a large number of consecutive slots being filled.
