Hash function
- Algorithms course
- Beginner
- Lesson 70/80
- 4 min
A hash function turns a key into an index.
Collision
A collision is when two different keys hash to the same index. Collisions are inevitable but a good hash function reduces them.
Collision resolution methods: separate chaining (a list at each index) and open addressing (searching for an empty slot).
Separate chaining
In separate chaining, a list is kept at each index. Colliding keys are added to the same list. Search is done within the list.
If collisions are few, each list is short and search remains approximately O(1). With many collisions, it approaches O(n).
Practice Insert into hash table
Write ht_insert(table, key, value, size). Find index with hash_func, add to table. Call print(ht_insert([[]]*3, 5, 'a', 3)) to find index 2.
Starter code
def ht_insert(table, key, value, size):
# InsertSample solution
def ht_insert(table, key, value, size):
# Insert
idx = hash_func(key, size)
table[idx].append((key, value))
return idx
print(ht_insert([[], [], []], 5, 'a', 3))Expected output
2
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Collision
When two keys hash to the same index, a ____ occurs.When two keys hash to the same index, a collision occurs.Explanation: collision is right.
2 Hash function: match the terms
| Term | Meaning |
|---|---|
collision |
Same index |
chaining |
List solution |
open addressing |
Find empty slot |
hash function |
Generates index |
3 What is one collision resolution method?
- Linear search
- Separate chaining Correct answer
- Binary search
- Bubble sort
Explanation: Separate chaining is a resolution method.