Hash maps Flashcards
What functions are implemented in a hash map?
Insert(k,v)
Search(k) => value
Delete(k)
What is the best and worst time complexity of a hash map?
Worst = O(n) - linear time Best = O(1) - constant time
What are entries in the hash table called?
Buckets
What’s the term for when a hash function creates the same hash for two different keys?
Collisions
What type of hash functions are there?
U.M.D.
- Universal hashing - worse case probability of collision 1/m (m = number of slots)
- Multiplication method
- Division method
When does Python’s dictionary (hash table) resize and by how much?
When m > 2/3 full (m = number of slots)
- Total slots < 50k = size x 4
- Total slots ≥ 50k = size x 2
What is the algorithm with the tortoise and the hare called and what questions can you solve with it?
Rabin-Karp (remember: Rabbit Carp = hare corp)
Used to solve cycling questions
What is open addressing?
Method of collision resolution that uses “probing” to find an empty slot.
The hash function accepts a trial count
e.g. h = (key, trial) => x
What is the simplest solution to collisions?
Hashing with chaining (linked lists)
What is the expected probability of collision in universal hashing?
1/m
What are 3 properties of universal hashing?
- Guarantees very few conflicts (1/m)
- Needs randomness
- Hash function is chosen from a hash family