🔐 Advanced Dictionary Implementation — Hashing and Performance

Master the hash table internals that make dictionaries incredibly fast.

🎯 Hash Function and Key Distribution

Python dictionaries use hash functions to map keys to array indices. A good hash function distributes keys uniformly.

# Hash values for various types
print(hash("hello"))      # -9223372036854775208
print(hash(42))           # 42
print(hash((1, 2, 3)))    # 2528714134463
print(hash([1, 2, 3]))    # TypeError: unhashable type: 'list'

# Hash determinism (same object = same hash in same session)
s = "hello"
print(hash(s))            # Same value in this session
print(hash(s))            # Same value

# Hash randomization (different sessions)
# Running Python again: different hash value for security

# Custom hash function example
class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __hash__(self):
        return hash((self.name, self.age))

    def __eq__(self, other):
        return self.name == other.name and self.age == other.age

people = {}
alice = Person("Alice", 30)
people[alice] = "Developer"

💡 Hash Collision and Resolution

When multiple keys hash to the same index, Python uses open addressing to find the next available slot.

# Creating collisions is difficult due to randomization, but:

# Dictionary internal structure
d = {'a': 1, 'b': 2, 'c': 3}

# CPython stores in a hash table:
# Index: 0    1    2    3    4    5    6    7
# Entry: [a:1][--][b:2][--][c:3][--][--][--]

# With collision (hypothetically):
# hash('a') % 8 = index 0
# hash('x') % 8 = index 0 (collision!)
# Probing: tries index 1, 2, 3... until finding empty slot

# Load factor affects performance
# CPython resizes table when load factor > 2/3
# Triggers rehashing of all existing keys

🎨 Dictionary Growth and Rehashing

import sys

# Monitor dictionary size growth
d = {}
for i in range(10):
    d[i] = i
    print(f"Keys: {len(d)}, Memory: {sys.getsizeof(d)} bytes")

# Output shows table resizing:
# Keys: 1, Memory: 240 bytes
# Keys: 2, Memory: 240 bytes
# Keys: 3, Memory: 240 bytes
# ...
# Keys: 6, Memory: 240 bytes
# Keys: 7, Memory: 368 bytes  <- Resized!
# Keys: 8, Memory: 368 bytes

# Rehashing cost
large_dict = {i: i for i in range(1000)}
# All 1000 keys rehashed when growing

📊 Dictionary Performance Profile

🎯 Dictionary Views and Iteration

# Views are dynamic—reflect changes
d = {'a': 1, 'b': 2}
keys_view = d.keys()

print(list(keys_view))  # ['a', 'b']

d['c'] = 3
print(list(keys_view))  # ['a', 'b', 'c'] - updated!

# Memory efficient iteration
for key in d:           # Iterates through keys
    print(key)

for key in d.keys():    # Same as above
    print(key)

for value in d.values():
    print(value)

for key, value in d.items():
    print(key, value)

# Iteration order (Python 3.7+)
# Dictionaries maintain insertion order
d = {}
d['z'] = 26
d['a'] = 1
d['m'] = 13
list(d.keys())  # ['z', 'a', 'm'] - insertion order preserved!

🔑 Key Takeaways

• ✅ Dictionaries use hash tables for O(1) average lookup

• ✅ Hash function maps keys to indices uniformly

• ✅ Open addressing resolves collisions

• ✅ Resizing triggers when load factor exceeds 2/3

• ✅ Dictionary views are dynamic and memory efficient

• ✅ Insertion order preserved (Python 3.7+)

Ready to practice? Challenges | Quiz