Summary - Hash table
- Algorithms course
- Beginner
- Lesson 72/80
- 4 min
Add key-value pairs and print them in a mini task.
Summary - Hash table
In this group you learned what a hash table is, hash functions, collisions and resolution methods. Average access is O(1).
Hash tables provide fast key-value access. Collisions are resolved with chaining or open addressing.
Practice List keys
Write ht_keys(table). Collect all keys in an array and return. Print [1, 2] with print(ht_keys([[(1,'a'),(2,'b')],[]])).
Starter code
def ht_keys(table):
# Collect keysSample solution
def ht_keys(table):
# Collect keys
result = []
for bucket in table:
for pair in bucket:
result.append(pair[0])
return result
print(ht_keys([[(1, 'a'), (2, 'b')], []]))Expected output
[1, 2]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - Hash table: match the terms
| Term | Meaning |
|---|---|
Hash table |
Key-value |
O(1) |
Average |
collision |
Same index |
chaining |
List |
2 Hash table
Question
A hash table stores ____ pairs.
Answer
A hash table stores key-value pairs.Explanation: key-value is right.
3 What is the worst-case complexity of a hash table?
- O(1)
- O(n)
- O(n^2) Correct answer
- O(log n)
Explanation: Worst case is O(n).