Summary - Hash table

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.

Exercise 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')],[]])).

Show example 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')], []]))

Test yourself

Summary - Hash table: match the terms

Hash table

Key-value
O(1)

Average
collision

Same index
chaining

List

Hash table

A hash table stores ____ pairs.

Show answer

A hash table stores key-value pairs.

What is the worst-case complexity of a hash table?
- O(1)
- O(n)
- O(n^2)
- O(log n)
Show answer

O(n^2) — Worst case is O(n).

Next lesson: What is a set?

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies