DEV Community: Ruata Hmar

Hash Indexes: What they are and their limitations

Ruata Hmar — Fri, 02 Oct 2026 19:45:14 +0000

Hash indexes are a type of database index used to speed up lookups by key.

They are commonly implemented using a hash table, which uses hash function to map keys to locations where their corresponding values or references can be found.

I wrote another blog going into more depth about hash maps and how they work. You can check it out here.

How hash indexes work?

Imagine you have a database containing users and their email addresses. If we want to find a user by their email, we could scan every record in the database until we find a match.

That would take O(n) time which is very slow for lookups, especially as our dataset grows.

Instead, we can use a hash index.

A hash function takes a key, such as an email address, and converts it into a hash value. This value helps us locate the corresponding entry in the hash table without scanning every record.

This gives hash indexes O(1) average-case lookup time (assuming a well-behaved hash function and a reasonable number of collisions, more on that on the hash map blog) which is pretty fast.

The problem with memory

Like all good things there's a catch. Hash indexes are typically maintained in memory because hash tables rely on fast access to their entries. If the hash table was stored in disk, they would distribute their keys in different areas of disk making it very hard to access different parts of the disk fast. Keeping the hash table in RAM allows lookups to happen much faster than repeatedly accessing random locations on disk.

However, RAM is expensive compared to disk, which makes it limited.

If we have a massive database, keeping the entire hash index in memory can become a problem. The index itself might be too large to fit in RAM, even if the actual data lives on disk. So hash indexes are better suited for smaller datasets that require frequent and fast access.

But RAM is volatile

If our server crashes, the in-memory hash table disappears. If that hash table was the only place where our index existed, we'd lose the index and have to rebuild it.

One solution is to use a write ahead log, or WAL.

Think of a WAL as a log of changes that have been made, or are about to be applied, to our data structure.

Whenever we perform a write or update, we first append the corresponding change to the log on disk before applying it to the in-memory index. This is the basic idea behind write ahead logging.

We store the log on disk because we need the changes to survive a crash. If the server goes down, we can use the log to recover the changes that were recorded, rather than losing everything when RAM is cleared.

Another neat thing about this is that WALs are written sequentially.

Instead of jumping around the disk to update lots of different locations, we can append changes to the end of a log. Sequential writes are generally much more efficient than random disk writes, especially on traditional hard drives.

The WAL doesn't magically make every operation faster though. It provides durability and supports recovery, while sequential appends can also make the write path more efficient.

No range queries

Hash indexes have one more major limitation: they don't support efficient range queries.

A range query is a query that retrieves records whose keys fall between two values.

For example:

SELECT *
FROM users
WHERE age BETWEEN 18 AND 25;

A hash function distributes keys according to their hash values, not their original order.

This means that even if the original keys are ordered, their corresponding hash values won't preserve that ordering.

If we want to find all keys within a particular range, we generally have to examine the entries and check which ones match. That can take O(n) time in a basic hash-table implementation.

This is where other index structures, such as B-tree indexes perform better.

So, basically

Hash indexes are useful when we need fast exact-key, hash tables provide O(1) average-case reads and writes.
Hashing doesn't preserve key order and are not good for ranged queries.
Hash tables can consume a lot of RAM, so its better for smaller datasets.
A write-ahead log helps recover changes after a crash.

Ultimately, choosing an index comes down to understanding the kind of queries your application needs to perform and the trade-offs you're willing to make.

That's it for my learnings on this topic, please correct me if I'm wrong

How hash maps work.

Ruata Hmar — Thu, 01 Oct 2026 15:00:32 +0000

This blog is a result of a short rabbit hole i went through as a part of me learning about hash indexing. I have also written a blog on hash indexing, you can check it out here.

Firstly, what problem does a hash map solve?

Imagine you have an array:

names= ["Bruh","Bro","Dude","Bob"]

If I ask you to find "Bob", you might scan the array until you find it.

Scanning through an array take O(n) time.

But image if you could calculate exactly where the value should live, instead of searching for it?

That's the central idea behind a hash map.

The hash function doesn't usually return an array index directly. It produces a hash value (using a hash function), which the hash map then converts into an index.

What is a hash function?

Simply put a hash function takes an input and transforms it into a number.

For example, imagine we create a simple hash function:

def hash_key(key):
    return sum(ord(char) for char in key)

ord() gives us the numeric value of a character.

For "cat":

c → 99
a → 97
t → 116

Therefore:

h("cat")=99+97+116=312

This function converts strings into numbers. That's hashing.

You will notice "act" also produces 312, because addition doesn't care about character order.Real hash functions are better designed to distribute keys more effectively.

We need numbers because arrays use integer indices. Suppose our hash map uses an underlying array with 10 slots, indexed from 0 to 9. Our hash values might be much larger than 9, so we need to turn them into valid array indices.

A simple approach is the modulo operator:

index=h(key)mod capacity

For "cat": 312mod10=2
For "dog": 314mod10=4

Now we have valid array indices.

Our hypothetical hash table

This is the basic mechanism behind a hash map: hash the key, calculate an index, and use the underlying array to access the entry.

A hash function does not have to be cryptographically secure to work well in a hash map. General-purpose hash functions and cryptographic hash functions solve different problems.

For example, SHA-256 is designed for cryptographic uses. A programming language's built-in hashing mechanism is generally designed around efficient data-structure operations and its own requirements.

What happens when two keys get the same index?

I think this is probably everyone’s first question.

Suppose we insert "cat" and "tac".

Our terrible hash function gives both strings the same hash because their characters add up to the same number. Both end up at index 2. This is called a collision.

And collisions aren't just a problem with bad hash functions. Even good hash functions produce collisions when mapping a huge number of possible keys into a finite number of array slots. Collisions don't mean the hash map is broken. Collision resolution is part of the data structure's design.

There are two major strategies for handling them.

Strategy A: Separate chaining

Each array slot holds a collection of entries, often a linked list or another small structure (like an array).

For example:

Index 0:  empty
Index 1:  empty
Index 2:  cat -> tac -> act
Index 3:  empty
Index 4:  dog

When multiple keys hash to the same index, they share that bucket.

To look up "tac":

Hash "tac" to get index 2.
Go to bucket 2.
Search the entries in that bucket.
Compare the actual keys to find "tac".

Strategy B: Open addressing

Instead of storing a collection inside each bucket, every entry lives directly in the array. If the desired slot is occupied, the hash map searches for another available slot according to a probing strategy.

For example, with linear probing:

Index 0:  empty
Index 1:  empty
Index 2:  cat
Index 3:  tac    <- goes to the next available slot
Index 4:  dog
...

To find "tac", the map starts at index 2, sees "cat", checks the next slot, and finds "tac" at index 3. There are more sophisticated probing strategies, but that's the core idea.

Resizing

Imagine the underlying array has 10 slots, and you keep inserting hundreds of entries.

Eventually, the table gets crowded. Collisions become more frequent, and operations slow down.

Many hash maps solve this by resizing the underlying array and redistributing the entries.

For example:

Before:
Capacity = 10
Entries  = 8

Resize:

After:
Capacity = 20
Entries  = 8

The entries generally need to be placed again because their indices depend on the table's capacity:

index=h(key)mod capacity

If the capacity changes, the index can change too.

Resizing is expensive when it happens.

Time analysis

Operation	Average case	Worst case
Insert	O(1)	O(n)
Lookup	O(1)	O(n)
Delete	O(1)	O(n)

Why is the average case constant time?

Calculating an index is constant time.
Calculating a hash takes time based on the key's size.
Accessing an array slot is constant time.

Strictly speaking, hashing a string of length k can take O(k) time if the hash must be calculated from scratch. So the usual O(1) claim assumes bounded-size keys or treats hash computation as constant time.

The worst case happens when many keys collide or cluster together, forcing the map to examine many entries.

But in chaining, there are multiple values in an bucket, so if there are m values inside a bucket why does it not take O(m) time to scan through a bucket ?

This is because of an important variable called the load factor;

α=n/m

Where:

n = number of entries.
m = number of buckets.
α = average number of entries per bucket.

For our example:

α=1000/100=10

If the load factor stays bounded as the table grows, and hashing distributes keys reasonably well, the expected time spent searching a bucket remains constant. Therefore O(α) == O(1) in such conditions.

Mini hash map

Lastly this is a mini hash map class i made in python (using the same old crappy hash function)

class Hash_Map:
    def __init__(self, capacity = 10):
        self.capacity = capacity
        self.hash = [[] for _ in range(capacity)]

    def hash_function(self, key):
        sum = 0
        for char in key:
            sum += ord(char) 
        return sum

    def get_index(self, key):
        return self.hash_function(key) % self.capacity

    def set(self, key, val):
        index = self.get_index(key)
        bucket = self.hash[index]

        for i, (oldKey, _oldVal) in enumerate(bucket):
            if oldKey == key:
                bucket[i] = (key, val)
                return

        bucket.append((key, val))

    def get(self, key):
        index = self.get_index(key)
        for old_key, val in self.hash[index]:
            if old_key == key:
                return val

        raise KeyError(key)

Reverse Indexing and Clustering.

Ruata Hmar — Thu, 13 Aug 2026 20:39:03 +0000

What I learnt this week:

Reverse Indexing

I am making a YouTube search application that allows you to search videos that you have saved in your account. This lead me to learning about how searches work and how they are optimised. One of the biggest thing i learnt was about reverse indexing.

If you've worked with SQL databases before you'd know that data is stored in tables with a primary key used to index through the entries. Of course you can add other indexes as well, this is regular indexing, but it has a major limitation for search speeds. Imagine this table below (maybe insert table pic), if you wanted to search for a title "x" in this you'd have to go through all the entries using the index and match each entry's value to the value searched. This takes O(n) time which is not very fast.

This is where reverse indexing comes. Reverse indexing is when the entry values are instead used as the indexes and the values they hold are references to the rows that store these values.

Now you don't have to go through all records to find the entry and can just search in the value index.

PostgreSQL is my database of choice, so i learnt that PostgreSQL implements reverse indexing using a tsvector(text search vector) function which converts a column(or columns) of a table to a vector that represents reverse indexes. tsquery is a function used to convert the search query in a form that can be easily used to match the tsvector values to find the result faster.

Finally there's a GIN or Generalised Inverted Index, which is the actual index structure PostgreSQL uses under the hood for tsvector columns. Think of it like an index but for every unique word, it keeps a list of which rows that word shows up in, so a search for a word goes straight to the word's row to find where the word shows up instead of scanning every row.

This is the first layer of optimisation for my search feature. Depending on the results, I'll decide if it needs more optimisation or not.

Clustering

This is something i revisited on reading Algorithm design by Jon Kleinberg and Éva Tardos. Clustering is basically grouping of elements based on how similar they are. Pretty easy. Now how do we know how similar two elements are? Well we use a distance function duhh and obvious enough smaller distance = more similar. Now there are some basic rules for this distance function

d(a,a) = 0, basically for the same element distance is zero meaning its 100% similar
d(a,b) > 0, different elements have positive distance
d(a,b) = d(b,a), distance between 2 elements is similar no matter where you start from

K-clustering

K-clustering basically means grouping a set S into k number of clusters. There's a very easy way to think about doing this and this is where a new term comes up: spacing. Spacing is the smallest distance between two elements that belong to different clusters.

Spacing tells you how close 2 clusters are to coming in contact. Now if we want clusters to be as distinct as possible we would want 2 clusters to have maximum spacing in between them. This is called maximum spacing clustering. There may be different ways to cluster a set but I'll focus on the clustering with the max spacing.

An easy algorithm proposed for maximum space clustering is Kruskal's algorithm but with slight tweaks. We merge nearby points as early as possible. we simply merge points in order of closeness until k clusters are formed. a different approach could also be to just delete k-1 of the max distance edges from a minimum spanning tree and it would result in a max spacing cluster.