# Hash Functions

Mapping arbitrary keys to fixed-size indexes, ideally spreading keys uniformly so collisions are rare.

**Rests on:** Modular Arithmetic

*Machine Learning · Data Structures*


## Why learn this

Hash functions are the engine behind the fastest data lookups in computing. When you save a contact and find it instantly, when a database fetches a row by ID, or when a Python dictionary looks up a key — a hash function is doing the work. This technique allows systems to store and retrieve vast amounts of information without searching through every single item one by one. By mastering this idea, you unlock the ability to understand how modern software scales efficiently, from search engines to the databases that power your daily applications.


## The intuition

Think of a hash function as a labelling machine that takes anything — a word, a number, a file — and stamps it with a fixed-size label, like a number from 0 to 15. For example, the word "apple" might get label 3, "banana" label 9, "cherry" label 1. The machine is deterministic: every time you feed "apple" it always gives 3. The magic is that it scatters different items across the labels, spreading them out like seeds in a garden, so that when you want to find "banana" you know to look in bucket 9, and you go straight there — you don't search through everything else. The label doesn't store the item; it just tells you where to look. If two items get the same label (a collision), you handle that by having a little list in that bucket, but if the labels are spread well, most buckets are nearly empty, so you find your item almost immediately. It's like having an index in the back of a book: you don't read every page to find a topic; you flip to the index page, which tells you the exact page number.


## An analogy

Imagine a library with 100 shelves, each shelf numbered 0 to 99. The librarian wants to place books so that any book can be found quickly. A naive approach: assign each book a random shelf. That works, but when you want a specific book, you have to search a shelf. Better: the librarian uses a rule — a hash function — that turns the book's title into a shelf number. For example, she counts the letters in the title and takes the last two digits: "The Hobbit" has 10 letters, so shelf 10. "Dune" has 4 letters, shelf 04. This is fast to compute, and it spreads books across shelves. If two books land on the same shelf (like "The Hobbit" and "The Secret Garden" both might have 10 letters), the librarian just puts both on that shelf, in a little pile — she might have to look through two or three books, but that's fine. The key insight: the rule is clear, deterministic, and it does a good job of spreading books out. The rule's quality determines how often shelves get crowded. If she used a bad rule like "shelf = first letter of title", then all titles starting with 'A' would pile on shelf 0, and finding a book would be slow. That's why hash functions are designed to spread values uniformly — like mixing paint colours, you want an even distribution.

Where the analogy breaks down: In a library, the librarian can redesign the shelf layout; in computing, the table size is fixed, and the hash function must produce a number within that range. Also, a library shelf can hold unlimited books; a hash table bucket usually has a limited capacity, so you might need to resize the table. Finally, the librarian can see the books and choose a clever rule; a hash function must work on any key without knowing in advance what they are.


## Definition

A hash function is a mathematical procedure that maps an arbitrary-sized key (like a string or a number) to a fixed-size integer, typically within the range of the table's size, with the goal of distributing keys uniformly so that collisions (two keys mapping to the same index) are rare.


## How it connects

You have not yet mastered any concepts, so this page stands alone. However, note that hash functions sit alongside Balanced Trees and B-Trees as two ways to organise data for fast lookup. Balanced trees keep data sorted and give logarithmic operations; hash tables give even faster average lookups (constant time) but lose ordering. Bloom Filters, a nearby topic you'll study later, use hash functions to test membership without storing the items. Heaps and Priority Queues, another neighbour, are about getting the extreme element quickly — not about hashing. As you progress, you'll meet Big-O Notation, which helps you compare these approaches formally.


## The mathematics

Hash functions rely on a specific type of arithmetic called modular arithmetic. You have used this before, even if you did not know the name. It is simply the math of remainders.

Think back to long division. When you divide 17 by 5, you ask how many times 5 fits into 17. It fits 3 times (because 5 times 3 is 15). You subtract 15 from 17, and you are left with 2. That 2 is the remainder. In modular arithmetic, we ignore the quotient (the 3) and keep only the remainder (the 2). We write this as "17 mod 5 = 2".

A hash table is a list of slots where we store data. If the table has 10 slots, they are numbered 0, 1, 2, ..., up to 9. A hash function takes any piece of data (called a key) and turns it into a number that fits exactly into one of those slots. It does this by taking a large number derived from the key and finding the remainder when divided by the table size.

Let us define the symbols we will use:
- h(k): This is the hash function. It is the rule or machine that takes a key k and spits out an index.
- k: This is the key. It is the data you want to store, such as a word like "cat" or a number like 12345.
- m: This is the table size. It is the total number of slots available in your hash table.
- c(k): This is an intermediate integer. Before we can use modular arithmetic, we must turn the key k into a single whole number. For example, if k is a word, c(k) might be the sum of the positions of its letters in the alphabet.

The general formula for this simple type of hash function is:
h(k) = c(k) mod m

This means: Take the number c(k), divide it by m, and keep only the remainder. Because the remainder of any division by m is always between 0 and m-1, the result h(k) will always be a valid slot index.

For example, if your table has 10 slots (m = 10), and your key produces the number c(k) = 47:
1. Divide 47 by 10. The answer is 4 with a remainder of 7.
2. The remainder is 7.
3. So, h(47) = 7. The data goes into slot 7.

The goal of a good hash function is to make sure that different keys produce different remainders as often as possible. If two different keys produce the same remainder, they try to go into the same slot. This is called a collision. While collisions are inevitable in large tables, a good function spreads them out evenly so the table does not get clogged.


## A worked example

Let us walk through a complete example with real numbers.

Setup:
- We have a hash table with 8 slots. The slots are numbered 0, 1, 2, 3, 4, 5, 6, and 7. So, m = 8.
- We want to store three keys: the words 'cat', 'dog', and 'bird'.
- Our method for turning a word into a number c(k) is to add up the position of each letter in the alphabet (a=1, b=2, c=3, ..., z=26).

Step 1: Hashing the key 'cat'
First, we find the letter positions:
- 'c' is the 3rd letter.
- 'a' is the 1st letter.
- 't' is the 20th letter.
Next, we sum these positions to get c('cat'):
c('cat') = 3 + 1 + 20 = 24.
Now we apply the hash function h(k) = c(k) mod m. Here, k is 'cat' and m is 8.
h('cat') = 24 mod 8.
To find 24 mod 8, we divide 24 by 8:
24 divided by 8 equals 3 exactly (because 8 times 3 is 24).
Since it divides evenly, the remainder is 0.
So, h('cat') = 0. The word 'cat' goes into slot 0.

Step 2: Hashing the key 'dog'
First, we find the letter positions:
- 'd' is the 4th letter.
- 'o' is the 15th letter.
- 'g' is the 7th letter.
Next, we sum these positions to get c('dog'):
c('dog') = 4 + 15 + 7 = 26.
Now we apply the hash function:
h('dog') = 26 mod 8.
To find 26 mod 8, we divide 26 by 8:
8 times 3 is 24. 
26 minus 24 is 2.
The remainder is 2.
So, h('dog') = 2. The word 'dog' goes into slot 2.

Step 3: Hashing the key 'bird'
First, we find the letter positions:
- 'b' is the 2nd letter.
- 'i' is the 9th letter.
- 'r' is the 18th letter.
- 'd' is the 4th letter.
Next, we sum these positions to get c('bird'):
c('bird') = 2 + 9 + 18 + 4 = 33.
Now we apply the hash function:
h('bird') = 33 mod 8.
To find 33 mod 8, we divide 33 by 8:
8 times 4 is 32. 
33 minus 32 is 1.
The remainder is 1.
So, h('bird') = 1. The word 'bird' goes into slot 1.

Result:
- Slot 0 contains 'cat'.
- Slot 1 contains 'bird'.
- Slot 2 contains 'dog'.
- Slots 3 through 7 are empty.

Because each key landed in a different slot, there were no collisions in this specific case. If we later want to retrieve 'dog', we do not search the whole table. We simply calculate h('dog') again, get 2, and look directly at slot 2.


## From scratch, in Python

```python
# A simple hash table with chaining (lists in each bucket)

def hash_function(key, table_size):
    # Sum of character positions, then modulo table_size
    total = 0
    for ch in key:
        total = total + (ord(ch) - ord('a') + 1)  # a=1, b=2, ...
    return total % table_size

# Build a table with 5 slots, each an empty list
table = []
for i in range(5):
    table.append([])

# Insert some keys
def insert(table, key, value):
    index = hash_function(key, len(table))
    # Check if key already exists (to update), else append
    for i, (k, v) in enumerate(table[index]):
        if k == key:
            table[index][i] = (key, value)
            return
    table[index].append((key, value))

# Look up a key
def lookup(table, key):
    index = hash_function(key, len(table))
    for k, v in table[index]:
        if k == key:
            return v
    return None

# Test
insert(table, 'cat', 'feline')
insert(table, 'dog', 'canine')
insert(table, 'bird', 'avian')
print(lookup(table, 'dog'))  # should print 'canine'
print(lookup(table, 'fish'))  # should print None
```


## The same thing, with a framework

Python's built-in dictionary is a hash table. For example:
```python
phonebook = {'cat': '123', 'dog': '456'}
print(phonebook['dog'])
```
Underneath, `phonebook['dog']` computes the hash of 'dog', finds the index, and retrieves the value. The dictionary handles collisions and resizing for you. In NumPy or PyTorch, hashing is used internally for indexing, but you rarely call a hash function directly. If you need to hash arrays, you might use `hash(tuple(arr))` or `pandas.util.hash_pandas_object` for DataFrame rows.


## What the code does

This section is empty in the framework field because the framework is an optional string; actually, I've provided the framework content inline.


## Common misconceptions

**Hash functions are random** — A hash function gives a different result every time you call it, so you can't rely on it.

Hash functions are deterministic: the same input always produces the same output. That's essential so you can find your data again. In fact: A hash function is a fixed rule. The same key always maps to the same index, which is what makes retrieval possible.

**Hash function and encryption are the same** — Hashing is a way to encrypt data so it's secret.

Hash functions are one-way and not meant to be reversible, but encryption is meant to be decrypted. Also, hashing maps to a fixed size; encryption outputs a variable size matching the input. In fact: Cryptographic hash functions (like SHA-256) are used for integrity checks, not secrecy. They are not encryption because they don't have a decryption key.

**The hash value IS the data** — When you store a key, you're storing the hash value instead of the key.

The hash value is just an index. The table stores the key and its associated value at that index. In fact: The hash function tells you where to put or find the key. The key itself is stored in the bucket.

**A good hash function never has collisions** — If you design a hash function well, no two keys will ever map to the same slot.

Since the number of possible keys is much larger than the number of slots, collisions are inevitable (pigeonhole principle). In fact: Collisions are guaranteed to happen; the goal is to make them rare and handle them efficiently, via chaining or open addressing.

**You can un-hash a value** — If you have the hash value, you can work backwards to reconstruct the original key.

A hash function is many-to-one; many keys map to the same hash. You cannot determine the original key from just the hash. In fact: Hash functions are not invertible. They are designed to be one-way, for performance, not for security.


## In short

A hash function maps any key to a fixed-size index, spreading keys uniformly so lookups are fast. It relies on modular arithmetic (remainders). Hash tables use chaining or open addressing to handle collisions. The quality of the hash function determines the table's performance: a good spread gives constant-time lookups, while a poor one degrades to linear time. Hash functions are not encryption, they are deterministic, and collisions are unavoidable. They power dictionaries, caches, and data structures across all of computing, and in AI they are behind tokenization, embedding lookup, and approximate nearest-neighbour search.


## Where this is used

Hash functions are everywhere in computing, and in AI they play crucial roles behind the scenes.

**Large language models (LLMs):** LLMs process text by tokenizing it into chunks. The tokenizer often uses a hash table to map tokens to vocabulary IDs. When training a model on billions of tokens, the vocabulary lookup must be instant; a hash function ensures each token maps to a unique ID quickly. Additionally, in distributed training across thousands of GPUs, data is sharded by hashing sample IDs to determine which GPU processes which batch. This ensures even distribution and reproducibility.

**Small language models on devices:** When you run a model on a phone or laptop, memory is limited. Hash functions are used to compress model weights via 'weight hashing' — instead of storing every weight, you store a hash of the weight and a small table, reconstructing the weight on the fly. This reduces model size dramatically. Also, embedding layers often use hashing to map rare words to a fixed set of features, as in feature hashing.

**Retrieval-augmented generation (RAG):** RAG systems retrieve relevant documents from a knowledge base to feed into an LLM. To speed up retrieval, they often build an index where each document is represented by a vector (embedding). Hash functions are used to create 'locality-sensitive hashing' (LSH) structures that put similar vectors in the same bucket, enabling fast approximate nearest-neighbour search. Without hashing, finding the closest vector among millions would be impossibly slow.

**Agentic systems:** Agents that plan and call tools need to store and retrieve state, such as previous actions or results. Hash tables are used to cache API responses or intermediate results to avoid recomputation, and to maintain a mapping from conversation IDs to session states. The speed of hash lookups directly affects the responsiveness of an agent.

**Everyday applied ML:** In recommendation systems, user IDs and item IDs are hashed to feature indices, especially when using vast categorical features. Fraud detection systems hash card numbers to lookup tables to check against blacklists. Vision systems hash image patches to find duplicate images or to build retrieval indexes. Speech recognition uses hash maps to decode phonemes to words quickly.

**What developers actually write:** In Python, developers just use dictionaries (`dict`) for hashing. In performance-critical code, they might use a custom hash function in C or use libraries like `bloom-filter` for probabilistic membership. In PyTorch, they might use `torch.nn.Embedding` which internally uses a hash table to map indices to vectors. When building a custom hash table, they handle collisions via chaining (lists) or open addressing (probing). Badly implemented hashing (e.g., using a poor hash function that causes many collisions) can degrade lookup time from O(1) to O(n), making systems crawl. Similarly, using a predictable hash function can allow denial-of-service attacks, so randomised hashing is used to prevent adversaries from forcing worst-case behaviour.


---

Read this on the web: https://basavapurushottam.com/learn-ai/hash-functions
