Data structures — Hash tables/ Associative Arrays

Lets discuss about hash table data structure and how is it used in Python. This blog is split into three sections, catering to readers from casual explorers to hardcore techies.

Basics of Hash tables — What , why & How?

Hash tables are in general unordered associative arrays. Seems like a typical text book definition so lets try to break it down & understand it in a better way. An array can be ordered(sorted) or unordered if we consider it based on the value it stores but if you look at the index of the arrays its always ordered & if we know the index of the value which we are trying to retrieve is simple but if we don't know the exact index then we need to retrieve the value by sequentially moving over the index.

Why?

O(n) is the time complexity to retrieve the value if we don't know the index of an value we are looking for. Lets take the above image and suppose we want to retrieve orange and we don’t know the index of it , we need to go through each and every index of an array starting from index 0 to search for the value orange. It would end up almost a linear search here.

Hash table :

A key-value pair based and unordered. Storage happens based on the a technique calling hashing of the key which point to the contagious memory block so that retrieval is fast and follow O(1) as time complexity.

So in above picture , Key refers to fruit which is a string and by using hash function a number related to memory block is generated where the Value Apple is stored. Next time when we again search for fruit since the key remains the same here the hash function redirects to exact location to retrieve the apple value.

I will take another real world common example to try to understand it in a better way before moving into the real world examples. Not sure how many of you used the good old keypad based mobile phones. It was such a pain to search a contact in the old mobile phones. People had to go through each and every contact starting from letter A until they find the required contact name. This is classic example of an array. Lets take our smart phone contacts now. Once we start searching with the name , the results are instant. Smart phone contacts are classic example of hash tables where contact person name is treated as Key and contact number is the value.

# Contacts stored in a dictionary (hash table)
contacts = {
    "Alice": "555-1234",
    "Bob": "555-5678",
    "Charlie": "555-9876",
    "David": "555-4321"
}

# Searching by name
name = "Alice"
number = contacts.get(name)

print("Found:", number)
# Output: Found: 555-1234

How?

A hash function converts a key (like "Alice") into a numeric value called a hash code. That number determines where in memory the key–value pair will be stored in the hash table.

In Python’s dictionary:

• The key "Alice" is passed through a built‑in hash function.
• The result might be something like hash("Alice") → 123456789.
• Python then maps that number to a slot in the table (say slot 15).
• When you later search for "Alice", Python re‑computes the same hash, jumps to slot 15, and retrieves "555‑1234" instantly.

This section is for Tech Enthusiasts. Classic example of hash table is caching of web pages in browser. Have you ever noticed that that an already visited website in your browser takes less time to load when compared against opening an unvisited new website? In general , our web browser stores the visited webpages in browser cache which would help for faster retrieval. When we try to reopen an visited www.example.com webpage , the name of the website is considered as Key for dictionary(in python and hash table) to retrieve the value associated which is the webpage from the cache memory to load it.

This section is for hard core techies :

Python uses a hashing algorithm called SipHash internally to hash strings and bytes keys for its dictionaries from 3.4 version onwards.

1. String Hashing: When you insert a string key into a dictionary (my_dict["key"] = value), Python uses SipHash to convert that string into a 64-bit integer hash. [1, 2]
2. Index Mapping: Python uses a bitmask on the resulting hash to map it to a specific index slot in the dictionary’s internal memory array.
3. Collision Handling: If two different keys result in the same array index, CPython resolves the collision using a specific open addressing technique called quadratic probing

Thats all and thanks for your time.