Published on 25 August 2026 · Updated on 31 August 2026 · 16 min read

Hash tables explained

Imagine a coat-check desk responsible for one million coats. For each coat, the attendant records a claim code and the shelf where the coat was placed. One record might connect the code CAT to shelf 12. When its owner returns, the attendant needs to turn that short code back into the right shelf. The simplest record system is one long list. The attendant starts at the first entry and compares claim codes until CAT appears. This works, but an unlucky search may inspect almost all one million records. Keeping the records sorted allows a faster halving search, but every new record then has to be inserted in the right place. Maintaining that order also costs work.

A hash table takes a less orderly route. It turns the claim code into a number and uses that number to choose one small part of an array. The attendant normally searches a short group of records instead of the complete collection. In return, the table reserves more memory than its entries alone require, and different claim codes sometimes select the same place. The table must do extra bookkeeping when that happens. The result is an exact data structure with fast operations in normal use. Lookup, insertion, and deletion take constant time on average when the table has enough spare room and its keys spread well. Constant time means that the expected amount of work does not grow with the number of stored entries. It does not mean one processor instruction, nor does it promise identical timing for every operation. If many keys crowd into the same place, a lookup can still end up scanning every entry.

How does a hash table work?

A hash table stores key-value pairs. A key identifies a value. In the coat-check example, CAT is the key and shelf 12 is its value. The key is what the customer presents, while the value is the information the attendant wants to retrieve. An ordinary array already offers fast access when a programme knows a numeric position. Picture an array as a row of numbered slots in memory: slot 0, slot 1, slot 2, and so on. The programme can calculate where a known slot lives and read it directly. The snag is that CAT is text, not an array position. We need a repeatable way to turn it into a number.

That calculation is called a hash function. It accepts a key and returns an integer called a hash code. For a small example, we can make a teaching function that adds the character code of every letter. Character codes are numbers used to represent text in memory. Here, C is 67, A is 65, and T is 84.

hash code for "CAT" = 67 + 65 + 84 = 216

This toy function is intentionally poor. Words made from the same letters get the same result, and similar text tends to bunch together. Real hash functions mix their input much more carefully. The simple addition is useful here because we can follow it without hiding the table behind pages of arithmetic.

Our table has an array of eight positions, which we will call buckets. Hash code 216 cannot be an array position because the only valid positions run from 0 to 7. The programme divides 216 by eight and keeps the remainder. The remainder operation always gives a number that fits inside the array.

216 divided by 8 leaves remainder 0
bucket index for "CAT" = 0

The hash code and bucket index are not the same thing. The hash function produced 216 from the key. The table then combined 216 with its current array size to choose bucket 0. That distinction matters when the array later changes size.

Following the buckets in memory

We will handle collisions with a method called separate chaining. Each bucket stores a reference to a short list of entries. A reference is a value that tells the programme where another piece of data lives in memory. Each entry holds both the original key and its value. At the start, the programme allocates an array of eight empty buckets.

bucket 0 -> empty
bucket 1 -> empty
bucket 2 -> empty
bucket 3 -> empty
bucket 4 -> empty
bucket 5 -> empty
bucket 6 -> empty
bucket 7 -> empty

Now insert CAT -> shelf 12. The programme calculates hash code 216, selects bucket 0, and finds no entries there. It allocates a new entry containing the original key CAT and the value shelf 12. Bucket 0 receives a reference to that entry. The other seven buckets remain unchanged.

bucket 0 -> [CAT, shelf 12]
bucket 1 -> empty
bucket 2 -> empty
bucket 3 -> empty
bucket 4 -> empty
bucket 5 -> empty
bucket 6 -> empty
bucket 7 -> empty

Next, insert ACT -> shelf 31. Its letters have the same character codes in a different order, so our teaching function again returns 216. The new key also selects bucket 0. This is a collision. Two unequal keys have chosen the same bucket, but that is not evidence that the keys are equal or a sign that the table has failed. The programme allocates a second entry and adds it to bucket 0’s list. Nothing replaces the first coat record.

bucket 0 -> [CAT, shelf 12] -> [ACT, shelf 31]
bucket 1 -> empty
bucket 2 -> empty
bucket 3 -> empty
bucket 4 -> empty
bucket 5 -> empty
bucket 6 -> empty
bucket 7 -> empty

A lookup for ACT repeats the same hash calculation and goes straight to bucket 0. The programme compares the requested key with the first stored key, CAT. They differ, so it follows the next reference and compares ACT with ACT. That comparison succeeds, and the programme returns shelf 31. The hash narrowed the search to one bucket. Comparing the original keys settled which entry was correct.

Updating a value follows the same path. Suppose the CAT coat moves to shelf 44. The programme searches bucket 0, finds the existing CAT entry, and replaces shelf 12 with shelf 44. It does not allocate another entry, so the table still contains two key-value pairs.

A useful hash function has to obey a few rules. An unchanged key must keep producing the same hash code while it remains in the table. Two keys that the programme considers equal must have the same hash code. The results should also spread realistic keys across the buckets instead of crowding them into a few lists. Unequal keys are still allowed to share a result, which is why every correct table needs both a collision strategy and equality checks.

The word “hash” also appears in cryptography, but the priorities differ. A table’s hash function is mainly chosen for speed and good distribution, with some designs also protecting against attacker-chosen collisions. It does not automatically hide a key or make the calculation impractical to reverse. Cryptographic hash functions are designed around different guarantees.

How does a hash table work in code?

The pseudocode below implements the same eight-bucket table. It writes operations as words and keeps the collision lists explicit so that each memory change is visible. makeArrayWith calls its function once per bucket, so every bucket receives its own list. appendTo adds an entry to the chosen list without replacing the list.

; Memory starts as an array of eight empty bucket lists.
(define bucketCount 8)
(define buckets
  (makeArrayWith bucketCount (function () (makeEmptyList))))
(define entryCount 0)

(define hashKey (function key)
  (define hashCode 0)

  (forEach character key
    (set hashCode
      (add hashCode (characterCode character))))

  (return hashCode)))

(define bucketIndexFor (function key)
  (return (remainder (hashKey key) bucketCount))))

(define setValue (function key value)
  (define bucketIndex (bucketIndexFor key))
  (define bucketEntries (arrayGet buckets bucketIndex))

  ; An equal key already in this bucket means this is an update.
  ; Replacing its value does not allocate a duplicate entry.
  (forEach entry bucketEntries
    (if (equals (entryKey entry) key)
      (do
        (setEntryValue entry value)
        (return))))

  ; No equal key exists in this bucket.
  ; Allocate one entry and add its reference to the bucket list.
  (appendTo bucketEntries (makeEntry key value))
  (set entryCount (add entryCount 1))))

(define getValue (function key)
  (define bucketIndex (bucketIndexFor key))
  (define bucketEntries (arrayGet buckets bucketIndex))

  ; Lookup changes no stored memory. It scans only this bucket.
  (forEach entry bucketEntries
    (if (equals (entryKey entry) key)
      (return (entryValue entry))))

  (return notFound)))

(setValue "CAT" "shelf 12")
; bucket 0 now contains [CAT, shelf 12].

(setValue "ACT" "shelf 31")
; bucket 0 now contains [CAT, shelf 12] followed by [ACT, shelf 31].

(getValue "ACT")
; Returns "shelf 31" after two key comparisons.
; The buckets and entries remain unchanged.

(setValue "CAT" "shelf 44")
; The first entry's value changes. entryCount remains 2.

Follow the first insertion in memory. hashKey starts with a temporary number set to zero, then replaces it as it reads each character. After C, A, and T, that number contains 216. bucketIndexFor reduces it to zero. setValue reads the reference in array position zero, sees an empty list, and adds a newly allocated entry. The temporary calculation can then disappear. The stored memory consists of the bucket array, its list reference, and the entry holding both strings.

The lookup allocates no new entry and moves nothing. It calculates the same position, reads the list reference, and walks through the entries already there. If no stored key equals the requested key, it returns notFound. In a real interface, that result must be distinguishable from a value the caller is allowed to store. Languages solve this with a separate presence flag, a result that explicitly represents either a value or nothing, or an error for a missing key.

When are hash tables used?

Many programming languages put a hash table behind a familiar built-in type. A Python dictionary connects keys to values, so an expression such as userByEmail[email] uses this idea beneath its compact syntax. The implementation does not necessarily use the linked lists from our teaching example, but it still hashes the email address, checks candidate entries, and verifies equality. A hash set uses similar machinery when a programme only needs to remember keys. Suppose an import contains one million email addresses and must reject duplicates. The programme can place each address in a hash set, then ask whether the next address is already present. It does not need to scan every earlier address for every new row. The set stores no separate shelf value because membership itself is the useful fact.

Compilers use hash tables to connect names in source code to information about variables and functions. Caches connect a request identifier to a result calculated earlier. Web applications often index active sessions by a random session identifier, while games may connect object names to the objects themselves. These uses share a question with one exact key: “What value belongs to this key?”

Databases use the structure too. During a hash join, PostgreSQL can read rows from one input and build a hash table using the join column as the key. It then reads the other input, hashes each join value, and checks the matching bucket for rows to combine. This avoids comparing every row on one side with every row on the other. The database planner still considers the amount of data, available memory, and other possible plans before choosing a hash join.

A hash table is a poor fit when the question depends on order. Its bucket positions do not follow alphabetical or numerical order, so it cannot naturally answer “give me every timestamp between 10:00 and 11:00” or “find the next larger key.” A balanced search tree or an ordered database index is better suited to range queries. For five or ten entries, a plain list may also be easier to understand and may use less memory. Fast expected lookup is useful, but it is not free.

Collisions are normal

The array has a limited number of buckets, while the set of possible keys is much larger. If nine coats must go on eight shelves, at least one shelf receives two coats. No clever hash function can remove that mathematical limit. It can only make collisions infrequent and spread them evenly for the keys an application actually uses.

Separate chaining is one common response. Every bucket owns a small collection, and collided entries join that collection. Deleting an entry means removing it from the relevant list. This design is easy to explain and tolerates more entries than buckets, but the references and separate entry allocations consume memory. Following those references can also make poorer use of a processor’s nearby-memory cache.

Another family of designs uses open addressing. All entries stay inside the main array. If the first position is occupied by a different key, the table checks other positions according to a fixed sequence until it finds the key or a suitable empty slot. Keeping entries close together can reduce allocations and improve memory access, but deletion becomes trickier. A deleted position may need a special marker that means “an entry used to be here, so keep searching.” Otherwise a lookup could stop too soon and miss a collided key stored farther along the sequence.

Production hash tables refine these ideas in different ways. CPython dictionaries use open addressing and retain special markers for deleted positions. Java’s HashMap can change a heavily collided bucket from a linked list into a balanced tree. The choices come from how each runtime stores entries and what behaviour its public map type promises. There is no rule that every language dictionary must use the same collision strategy.

Spare room and resizing

A table slows down as it becomes crowded. Its load factor describes that crowding. Divide the number of entries by the number of buckets, and six entries in eight buckets give a load factor of 0.75. A high load factor wastes little array space, but it increases the chance of longer lists or longer probe sequences. A low load factor spends more memory to keep searches short. Once a table crosses its chosen limit, it allocates a larger bucket array and calculates a new position for every existing entry. Copying an old position is not enough because the array size participates in the remainder calculation. Hash code 10 selects bucket 2 in an eight-bucket array because division by eight leaves remainder 2. The same code selects bucket 10 in a sixteen-bucket array.

During this resize, the programme temporarily holds the old and new arrays in memory. It walks through the existing entries, places each reference into the correct new bucket, and finally releases the old bucket array. The key-value entries themselves may stay where they are when the implementation can move only their references. Other layouts copy entries into new slots. Either way, the arrangement changes even though the stored keys and values do not. One insertion can therefore be expensive. Most insertions touch one short bucket, but the insertion that triggers growth may redistribute every entry. The costly event happens only occasionally. When we spread its work across a long sequence of insertions, the expected cost per insertion remains constant. This is called amortised constant time. Some individual operations cost more, while the average cost over the whole sequence stays bounded. The article about Big O notation covers this kind of analysis in more detail.

A subtle trap: changing a key

A key’s hash and equality behaviour must remain stable while the key sits in the table. Consider an object with two fields, city: Utrecht and year: 2026. Suppose its hash code selects bucket 5, where the table stores a reference to the object and its value. Code elsewhere now changes the same object’s city to Rotterdam. If the city contributes to the hash calculation, the changed object may select bucket 1. The entry has not moved. It is still linked from bucket 5. A lookup hashes the new contents, searches bucket 1, and reports that the key is missing even though an entry referring to that object remains in the table.

This is why Python requires dictionary keys to be hashable and rejects mutable lists as keys. Saying that keys must always be immutable is slightly broader than the real rule. A key may contain changing data that the table ignores. What must stay fixed is every part used to calculate its hash code or decide equality. If that information needs to change, remove the old key first and insert the changed key again so the table can place it correctly.

Worst cases and hostile input

Good distribution makes bucket lists short in normal use. It does not guarantee that outcome. If every key lands in one bucket, lookup becomes an ordinary scan through all stored entries. With one million entries in that bucket, the coat attendant is back where they started. Expected constant time has degraded to linear time. A weak hash function can cause this by accident. An attacker may also choose keys that collide deliberately and send them to a server in a request. If parsing that request makes the server perform a long scan for every insertion or lookup, processor use can grow enough to deny service to other users. This class of attack is often called HashDoS.

Implementations can respond with a randomly seeded hash function so that an attacker cannot predict collisions in advance, a hash designed to resist such inputs, a limit on table crowding, or a balanced tree for an overloaded bucket. Stronger protection makes either the hash calculation or the table itself more expensive. Rust’s standard HashMap, for example, randomly seeds its default hasher as part of its protection against HashDoS attacks.

Bucket order is also easy to misread. Hashing does not naturally preserve sorted or insertion order. Python dictionaries do preserve insertion order, but that is a guarantee of that implementation rather than a property of hash tables themselves. Resizing can change every bucket position. Concurrency is a separate concern too. A mutable table is not automatically safe when several threads write to it at once. Applications need an implementation designed for concurrent access or their own synchronisation around changes.

Recap and takeaway

A hash table spends extra memory to avoid searching every stored item. It runs a key through a repeatable hash function, turns the resulting hash code into a bucket position, and checks original keys within that bucket. Collisions are unavoidable, so equality checks and a collision strategy are part of the design, not optional repairs. Spare capacity and good distribution keep the search short in normal use, while resizing restores that spare room as the collection grows.

If only one idea sticks, remember this: a hash does not tell the table where an item must be. It tells the table where to start looking. That shortcut gives lookup, insertion, and deletion expected constant time, but poor distribution, mutable keys, an overfull table, or hostile input can remove the advantage.

Further reading

• Big O notation explained
• Cryptographic hash functions explained
• Open Data Structures: Hash tables
• Python documentation: How are dictionaries implemented in CPython?
• PostgreSQL documentation: Planner and optimiser
• Oracle documentation: Java HashMap