B4.1.6 · Core principles of abstract data types

Hash tables and the core principles of ADTs

A cloakroom attendant never searches every hook for your coat. Your ticket number tells them exactly which hook, instantly. A hash table gives a program that same shortcut.

HL only Typically 1–2 marks per part · AO1/AO2 Command term: describe, explain

Explainer

With the list-backed set from B4.1.5, checking membership means looking at every item until you find it (or run out of items). A hash table skips that search entirely: it computes exactly where a value belongs before ever looking at the data.

A hash table stores data in an array-like structure, but instead of the programmer choosing a numeric index, a key (like a name or an ID) is fed through a hashing algorithm that computes the index for you. Under ideal conditions this gives O(1) average-time complexity: search, insert and delete all take roughly the same amount of time no matter how much data is stored.

How the hashing algorithm produces an index

One simple method: convert each character of the key to its ASCII value, add them up, then use modulus with the table size to bring the total back into range. Using the key "name" on a table with 10 slots:

ASCII valuesn=110, a=97, m=109, e=101

Sum110 + 97 + 109 + 101 = 417

Mod table size417 mod 10 = 7

Stored atindex 7

This is exactly what Python's dict and Java's HashMap do underneath, with a more sophisticated hashing algorithm than simple ASCII-summing.

# A dict IS a hash table: Python does the hashing for you
lockers = {}

# Store two entries, each under its own key
lockers["A14"] = "N. Okafor"
lockers["B07"] = "S. Ferreira"

# Look one up: hashed straight to its slot, no scanning
holder = lockers["A14"]

# Release a locker
del lockers["B07"]

import java.util.HashMap;

// A HashMap IS a hash table; the two type parameters
// are the key type and the stored value type
HashMap<String, String> lockers = new HashMap<>();

// Store two entries, each under its own key
lockers.put("A14", "N. Okafor");
lockers.put("B07", "S. Ferreira");

// Look one up: hashed straight to its slot, no scanning
String holder = lockers.get("A14");

// Release a locker
lockers.remove("B07");

Python's set and Java's HashSet (from B4.1.5) are built on this exact mechanism, more on exactly how further down this page.

Collision. Two different keys can hash to the same index, for example two names whose ASCII sums both land on 7. This is called a collision, and no hashing algorithm can guarantee it will never happen.

Load factor. Divide how many entries are actually stored by how many slots the table has, load factor = (entries stored) / (total slots), and that fraction tells you how crowded the table already is. Push it too high and collisions start piling up, which is exactly why most implementations watch this number and trigger a rehash (a bigger array, everything reinserted) once it crosses a threshold, commonly 0.7.

Worked example

Inserting six keys with the hashing algorithm `key mod 6`

A 6-slot table (indices 0–5). The keys 174, 259, 202, 391, 88 and 133 are inserted one at a time, in that order. Watch what happens when two keys hash to the same index.

start

An empty 6-slot table.

Step 1 of 7

Index 1 and index 4 each end up holding more than one key. That's chaining: the collision-resolution method used here, where every index can hold a small list of entries instead of just one.

How a set uses this exact structure to store and manage data

The table above is really a hash table storing key-value pairs, each slot holds a key AND a value looked up by it. A set is the same structure with one thing removed: no value. Only the key is stored. The key being present at its hashed slot IS the entire answer to "is this in the set?", nothing else needs to be looked up or compared beyond that.

Membership testA yes/no check: "is this value in the collection?" Nothing about position, count, or order, just present or not. First introduced in B4.1.5., using the SAME finished table above. Treat it as a set of six numbers: {174, 259, 202, 391, 88, 133}. Two lookups, worked through:

contains(174)?174 mod 6 = 0 → bucket 0 holds [174] → 174 == 174 → True

contains(55)?55 mod 6 = 1 → bucket 1 holds [259, 391, 133] → compare 55 against each, none match → False

Both lookups jump straight to ONE bucket, never scan the other five. That's the O(1) speed. The second lookup still has to check a few values inside its bucket (this is where a collision's cost shows up: not in finding the bucket, but in checking everything already chained there), which is exactly why a low load factor matters, a near-empty bucket usually means zero or one comparison, not three.

This is also how a set enforces uniqueness, the SAME rule B4.1.5 built by hand with a linear contains() check, now backed by hashing instead: calling add(174) again hashes to bucket 0, finds 174 already sitting there via that same equality check, and does nothing. Adding a genuinely new value that happens to hash to bucket 0 would instead extend the chain there, exactly like 391 and 133 did at bucket 1 above.

This is why Python's real set and Java's real HashSet (from B4.1.5) are so much faster at membership testing than the list-backed version built by hand in that statement: same uniqueness rule, but a hashed jump to one bucket instead of a scan through every stored item.

Chaining vs open addressing

Chaining (shown above) is one way to resolve a collision. The other main approach, open addressing, never lets more than one entry live at a single index at all. This is B4's own guiding question in miniature, which ADT is most appropriate for a given situation: both are valid answers to "how do I resolve a collision," and the right one depends on what the situation actually needs.

Chaining

Real example: the table above. Index 1 holds a small linked list: 259, then 391, then 133, all chained together at the same slot.

Advantage

Tolerant of crowding (a chain simply grows longer as more entries land on it, so there is no hard ceiling the way a fixed array has)

Disadvantage

Memory overhead (each entry in a chain needs extra memory for the link to the next one)

Open addressing

Real example: if 391 collided with 259 at index 1, open addressing would instead search forward (index 2, then 3...) for the next empty slot and place 391 there.

Advantage

No extra structure to maintain (every entry sits directly inside the array itself, there is no separate linked list bolted onto each slot)

Disadvantage

Clustering (once one probe chain forms, new entries keep landing on the same stretch of slots and lengthening it further, so a later insert, search or delete has to step past a longer and longer run before it finds what it's after)

Rehashing, in order

Once the load factor gets too high, the table itself is rebuilt bigger. Before the abstract steps, look at what this means for the exact table built above.

The table above is already overloaded. It has 6 slots and, after the last step, 6 entries stored: load factor = 6 / 6 = 1.0. That's well past the 0.7 threshold, so in a real system, inserting that 6th key (133) is exactly the moment that would trigger the rehash described below.

Here is what actually happens to it, one step at a time:

Watch the load factor climb. The table keeps tracking it after every insert, and crossing the threshold, commonly 0.7, is the trigger, not something a person decides case by case.
Our table: 1.0 > 0.7, so rehashing starts now.
Build a new array, bigger. Doubling is the usual jump, and landing on a prime size specifically cuts down on how often future keys collide.
Our table: 6 slots doubles to 12, then rounds up to the next prime, 13 slots.
Work out where every key lands now. The same hashing algorithm runs again on every key already stored, only this time it divides by the new, bigger slot count, so most keys end up somewhere new.
Our table: the hashing algorithm changes from key mod 6 to key mod 13. See the full recompute below.
Place every key at its new spot. One at a time, into the new array, resolving any collision that turns up exactly the way it would have before.

Step 3 in full: every key from the old table, recomputed against the new size.

Key	Old index (mod 6)	New index (mod 13)
174	0	5
259	1 (chained)	12
202	4 (chained)	7
391	1 (chained)	1
133	1 (chained)	3
88	4 (chained)	10

Under the old table, indices 1 and 4 each held a 3-entry and 2-entry chain. Under the new 13-slot table (step 4, reinsert), all six keys land on six DIFFERENT indices, zero collisions. This is exactly why rehashing exists: the same data, spread across more room, stops colliding.

Check your understanding

A leisure centre hashes locker allocations with the algorithm card number MOD 40. What index does card number 906 hash to?

Common mistake

Grounded in the the syllabus's own worked treatment of B4.1.6

RecurringCandidates often describe a hash table's speed advantage without connecting it to the load factor at all, treating O(1) performance as guaranteed rather than conditional on the table staying reasonably empty.

What a weak answer looks like: "Hash tables are fast because you can jump straight to the index." True, but ignores what happens as the table fills up.

✓

What it should say: "Hash tables are fast only while the load factor stays low. As more entries are added, collisions become more frequent, and lookups degrade toward checking every item in a chain, which is why rehashing exists to keep the load factor down." Names the condition the speed depends on.

Linking question

How this connects to the rest of the syllabus

The IB syllabus is deliberately woven together, not a stack of isolated topics. Here's how hash tables connect specifically to B2 (file processing), worth thinking through, not just memorising: it's the kind of synthesis a Paper 1/2 question can genuinely ask for.

How can abstract data types be used to optimize file-processing operations like read and write? (Hashing is exactly how real database and file systems achieve fast indexed lookups, the same mechanism built above, applied to records on disk instead of numbers in an array.)

Revision questions

Past-paper style. Write an answer, then reveal the marking points and mark yourself.

Question 1 · 1 mark

[1]Using the 6-slot table built above, determine the index that key 208 hashes to, and state whether inserting it causes a collision.

Question 2 · 2 marks

[2]The finished table holds 6 entries in 6 slots. Calculate its load factor, and explain what the program should do next.

Question 3 · 2 marks

[2]After rehashing, key 174 moves from index 0 to index 5 and key 133 moves from index 1 to index 3. Explain why every stored key must be recomputed rather than copied straight across.

Flashcards

Active recall for this statement's key terms.