Collision
- Algorithms course
- Beginner
- Lesson 71/80
- 4 min
Two keys hitting the same index and chaining to resolve it.
Search in hash table
Search in a hash table: hash the key, search for the key in the list at that index. If found, return the value; if not, None.
Search is average O(1) because with few collisions the list is short. The worst case (all at one index) is O(n).
Load factor
Load factor = number of elements / table size. A high load factor increases collisions and decreases performance.
If the load factor exceeds 0.7, the table is resized (rehash). This maintains O(1) average access.
Practice Get from hash table
Write ht_get(table, key, size). Find index with hash_func, search for key. Print a with print(ht_get([[(5,'a')],[],[]], 5, 3)).
Starter code
def ht_get(table, key, size):
# Get valueSample solution
def ht_get(table, key, size):
# Get value
idx = hash_func(key, size)
for pair in table[idx]:
if pair[0] == key:
return pair[1]
return None
print(ht_get([[(5, 'a')], [], []], 5, 3))Expected output
a
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Collision: match the terms
| Term | Meaning |
|---|---|
search |
O(1) average |
collision |
Search in list |
load factor |
Fullness |
rehash |
Resize |
2 What does the load factor measure?
- Fullness ratio Correct answer
- Table size
- Hash quality
- Search speed
Explanation: It measures the fullness ratio.
3 Rehash
When the load factor is high, ____ is done.When the load factor is high, rehash is done.Explanation: rehash is right.