Hash Tables – The Principle Behind Dictionaries

After completing this topic

You will be able to explain how hash tables work and understand why Python dictionaries achieve O(1) lookups.

Problem: Finding One in a Million

If you want to find a specific value in a list, you have to compare it one by one from the beginning.

users = ["Kim Hoon", "Lee Soo", "Park Jin", ...]  # 1 million people
"Kim Hoon" in users  # Worst case: compares 1 million times — O(n)

If the data increases tenfold, the search time also increases tenfold. Is there no other way?

Hash tables are data structures where search time remains almost constant, no matter how much the data increases.

Hash Function – Converting Keys to Addresses

The core idea of a hash table is simple: convert the key to a number (address) and access it directly at that address.

"Kim Hoon" → hash function → 427 → stored at table[427]
"Lee Soo" → hash function → 12 → stored at table[12]
"Park Jin" → hash function → 891 → stored at table[891]

The library analogy is appropriate. When looking for a book in a library, you don't browse the shelves from beginning to end. You look at the classification number (call number) and go directly to the corresponding shelf. The hash function is just this "classification number generator."

# Python built-in hash function
hash("Kim Hoon")     # -4340382828924905128 (different each time)
hash("Lee Soo")     # 7421390584116839301
hash(42)         # 42 (integers are their own hash value)

# Divide by table size to determine the index
index = hash("Kim Hoon") % 1000  # index in the range of 0 to 999

Collision – What if Two Items End Up at the Same Address?

The hash function may assign the same index to different keys. This is called a collision.

"Kim Hoon" → hash → 427
"Choi Young" → hash → 427 ← Collision!

The most common solution is chaining. Create a linked list at the same index to store multiple items.

table[427] → ("Kim Hoon", "010-1234") → ("Choi Young", "010-5678")
table[12]  → ("Lee Soo", "010-9012")

If there are few collisions, the chain length is 1, which is O(1). If there are many, the chain becomes long and it slows down. Therefore, a good hash function is important to distribute data evenly.

Python Dictionary = Hash Table

Python's dict is implemented as a hash table. This is why it has such performance.

# Dictionary — O(1) lookup
users = {"Kim Hoon": "010-1234", "Lee Soo": "010-5678"}
users["Kim Hoon"]     # Hash calculation → direct access — O(1)
"Park Jin" in users   # O(1)

# List — O(n) lookup
user_list = [("Kim Hoon", "010-1234"), ("Lee Soo", "010-5678")]
# To find "Kim Hoon", you have to compare one by one — O(n)

Whether it's 1 million or 10 million items, dictionary lookups take almost the same amount of time.

Weaknesses of Hash Tables

It's not a silver bullet.

• Memory Usage: Empty slots must be reserved in advance, so it uses more memory than a list.
• No Order: Originally, hash tables did not guarantee insertion order (Python dict guarantees it from 3.7).
• Key Constraints: Keys must be immutable — strings, numbers, and tuples are fine, but lists cannot be keys.

# Lists cannot be used as keys
d = {[1, 2]: "value"}  # TypeError: unhashable type: 'list'

# Tuples are allowed
d = {(1, 2): "value"}  # OK — tuples are immutable and can be hashed

Key Takeaways

Hash tables achieve O(1) lookups with the simple principle of "key → hash function → index → direct access." When you use dict in Python, a hash function is working inside. If you need to frequently search for something in the data, using a dictionary instead of a list is almost always the right answer.