Collision

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.

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

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

Test yourself

Collision: match the terms

search

O(1) average
collision

Search in list
load factor

Fullness
rehash

Resize
What does the load factor measure?
- Fullness ratio
- Table size
- Hash quality
- Search speed
Show answer

Fullness ratio — It measures the fullness ratio.

Rehash

When the load factor is high, ____ is done.

Show answer

When the load factor is high, rehash is done.

Next lesson: Summary - Hash table

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies