Hash function

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).

Exercise 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.

Show example 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))

Test yourself

Collision

When two keys hash to the same index, a ____ occurs.

Show answer

When two keys hash to the same index, a collision occurs.

Hash function: match the terms

collision

Same index
chaining

List solution
open addressing

Find empty slot
hash function

Generates index
What is one collision resolution method?
- Linear search
- Separate chaining
- Binary search
- Bubble sort
Show answer

Separate chaining — Separate chaining is a resolution method.

Next lesson: Collision

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies