Introduction to Hash Tables

Back to: Python Data Structure and Algorithims

Introduction to Hash Tables

A hash table is a data structure that stores data in key-value pairs and allows fast access to values based on their keys.

Think of it like a hardware store inventory: you want to quickly find the quantity of nails, screws, or bolts.

---

🧩 Real-World Example

Suppose we have the following items in our store:

In Python, we could use a dictionary:

Here, the key is the item ("nails") and the value is the quantity (1000).

---

🔹 How a Hash Table Works

1. Hash Function:
   A hash table uses a hash function to convert a key into an address in memory.

   Example:

   hash("nails") → 2


   This means "nails" will be stored at address 2 in our list.

2. Deterministic:
   The hash function always produces the same address for the same key.

   hash("nails") → 2 (every time)


3. One-Way Function:
   You cannot reverse the hash to get the original key:

   hash⁻¹(2) ≠ "nails"


---

🔹 Building Our Own Hash Table

We can implement a hash table using a list to represent addresses:

---

🔹 Storing Items

1. Set an item:

   • Key: "nails"

   • Value: 1000

   • Hash to find the address:

     address = hash("nails") % 8 # ensure address fits in our list
hash_table[address] = ["nails", 1000]


2. Handle collisions:

   • If multiple keys hash to the same address, store them as a list of key-value pairs at that address.

---

🔹 Getting Items

To retrieve a value:

1. Hash the key to find the address:

   address = hash("bolts") % 8


2. Go directly to that address in the list.

3. If there are multiple items at the same address, loop through the list to find the correct key.

Example:

---

🔹 Advantages of Hash Tables

• Fast lookup: Access items in O(1) time on average.

• Deterministic: Same key always hashes to the same address.

• Efficient storage: Keys are directly mapped to addresses.

---

🔹 Key Points

---

🔹 Summary

A hash table is an incredibly efficient data structure for mapping keys to values.
Even though Python provides dictionaries as built-in hash tables, building one from scratch helps understand hashing, collisions, and memory addressing.