How Does a Hash Table Work When Two Keys Share a Slot?

By Julia Berens · · 4 min read

A grainy black-and-white view of a tabletop with cups, a saucer, and a small rectangular object.

Given a book ID, you want to find its title without checking every book in the catalog. A hash table gives you a place to start: it uses the ID to pick a slot in an array. So how does a hash table work when two book IDs point to the same slot? With a method called chaining, the table keeps both entries in that slot and checks their IDs when you look one up.

How does a hash table work with five slots?

A hash table stores keys and their associated values. In our catalog, the book ID is the key and the title is the value. The table stores both together as an entry, such as (12, Atlas). Keep an eye on the distinction between a key and a slot number: the key identifies the book, while the slot number tells the table where to look for its entry.

Start with five empty slots numbered 0 to 4. For this example, use a simple hash rule: take the remainder when you divide the key by 5. In code, write that as key % 5. For key 12, dividing by 5 gives a quotient of 2 and a remainder of 2. The table uses the remainder, not the quotient, so the entry goes in slot 2. This rule works for our nonnegative integer keys because the remainder is always a valid slot number.

Insert two keys into the same slot

To insert (12, Atlas), calculate 12 % 5 = 2 and go to slot 2. It is empty, so put the entry there. Now insert (17, Rivers). This time, 17 % 5 = 2 as well. Two different keys have mapped to the same slot. That is a collision. Replacing the entry for key 12 with the entry for key 17 would lose a book from the catalog, even though the two IDs are different.

With separate chaining, each slot can hold a collection of entries. You can picture a slot as the start of a short list. In our example, insertion checks whether the key is already in the list and, if it is new, adds the entry at the end. The table checks key 17 against key 12, sees they differ, and adds the new pair after the first. Add one more entry, (9, Forests). Since 9 % 5 = 4, that pair goes into its own list in slot 4.

SlotEntries in order
0Empty
1Empty
2(12, Atlas), then (17, Rivers)
3Empty
4(9, Forests)

A collision is not the same as inserting a key that already exists. If you insert (12, World Atlas), the table finds key 12 in slot 2 and changes its value. It does not add a second entry for key 12 or change the title stored under key 17. For the lookup below, keep the original entries shown in the table.

Look up a key without searching every slot

To find the title for key 17, repeat the same calculation you used to insert it. The table might have several entries in the chosen slot, so getting there is only the first step.

  1. Calculate 17 % 5 = 2 and go directly to slot 2.
  2. Compare the requested key, 17, with the first stored key, 12. They differ, so move to the next entry.
  3. Compare 17 with the next stored key, 17. They match, so return its value, Rivers.

Looking up key 12 also takes you to slot 2, but you get Atlas after the first comparison. Neither lookup examines slot 4, even though there is another book there. The slot calculation narrows the search. The key comparison tells you which value to return.

Now try key 22. It also gives remainder 2, but neither 12 nor 17 matches 22. Once you reach the end of the list, you can report that key 22 is absent. You do not need to search elsewhere: if 22 had been inserted into this table, the same rule would have put it in slot 2. For key 8, the lookup is even shorter. It takes you to empty slot 3, so there are no stored keys to compare.

Short chains make lookups fast

The lookup for key 17 took two key comparisons. If you put thirty entries in the same slot and the match was last, the lookup would take thirty comparisons. In the worst case, all entries land in one slot, and finding a key can take as long as scanning a single list of all the entries.

A well-distributed hash function spreads keys across slots. If the keys are well distributed and the table keeps the average number of entries per slot bounded as it grows, lookup takes expected constant time, written O(1), assuming hashing and key comparison each take constant time. That does not mean every lookup takes one comparison. It means the expected lookup cost stays bounded as the number of entries grows under those assumptions.

With our remainder rule, making the array larger changes where some keys belong. If you grow from five slots to seven, key 12 maps to slot 5 and key 17 maps to slot 3. Just adding empty slots would leave those entries in the wrong places for future lookups. A resize must redistribute existing entries according to the new slot calculation.

Try one insertion and one update by hand

Copy the five slots from the table and insert (7, Oceans). Then update key 17 to Great Rivers and look up key 7. Write down each key you compare during that last lookup before checking your work: with entries appended in insertion order, you should compare against 12, 17, and then 7. The update changes only the value beside key 17. Slot 4 still holds (9, Forests).

For more practice tracing data structures, browse the Computer Science Explained articles or work through the ICSC training and practice problems.

Frequently asked questions

Does a collision mean two keys are equal?

No. A collision means two different keys map to the same slot. The table compares the full keys to tell the entries apart.

Why does the table store the key with the value?

Several entries can share a slot. The stored key lets the table identify the right entry instead of returning whichever value it sees first.

Can a lookup stop at the first different key?

Not with the unsorted chains in this example. A matching key could be farther down the chain, so the lookup continues until it finds a match or reaches the end.