IB COMPUTER SCIENCE | B4.1.6 ADTs and Hash Tables (HL)

Lesson objective

Explain ADT contracts and hash-table mechanics, including collision resolution, load factors, sets and mappings in Python and Java.

Learn

B4.1.6 | ADTS AND HASH TABLES (HL ONLY)

01 | THE PROMISE AND THE MACHINERY

A school app looks up a student from an ID and checks whether that ID is registered for an event. The first task needs a map from keys to values; the second needs a set of distinct members. These are logical requirements, not instructions about where bytes must be stored.

An abstract data type describes data and associated operations at a high level, including what those operations mean. A hash table is one family of representations that can supply fast keyed lookup for maps and membership for sets.

This lesson connects the contract to the machinery: hash functions choose a starting location, collision policies preserve distinct keys, and capacity management helps control the work needed for lookup.

02 | MAP AND SET CONTRACTS ARE DIFFERENT

ADT Logical data Example operations
Map Distinct keys associated with values put/update, get by key, remove by key, contains-key
Set Distinct members add, contains, remove, union, intersection

A map such as {17: "Leo"} associates key 17 with a value. Updating key 17 replaces its associated value rather than adding a second mapping for the same key. Different keys can still have equal values.

A set such as {17, 24} stores membership rather than a separate user-supplied value for each key. The representation may reuse mapping-style machinery internally, but the public contract remains different.

03 | FROM KEY TO TABLE LOCATION

1 | KEY

Receive a permitted key, such as student ID 17.

2 | HASH AND REDUCE

Derive a hash and map it to the current table’s index range.

3 | RESOLVE AND COMPARE

Inspect the candidate entry or collision path and compare the stored key.

Real implementations commonly produce a hash code and then compress or mix it into a table index. The index must be in the table’s valid range. The original key is retained so equality can be checked when a candidate is inspected.

Hashing does not itself prove that the first candidate is the requested key. Several distinct keys can lead to the same initial location.

04 | A SMALL DIVISION-HASH MODEL

For a clear worked model, use non-negative integer keys and index = key MOD m, where m is the bucket count. This combines the hash/index calculation into one simple formula. It is a teaching model, not the exact indexing algorithm of Python or Java collections.

Key Calculation for m = 7 Initial bucket
10 10 MOD 7 3
17 17 MOD 7 3
24 24 MOD 7 3
31 31 MOD 7 3
11 11 MOD 7 4

MOD gives the remainder. Because these four keys differ by multiples of 7, they all start at bucket 3. A larger key is not necessarily stored at a larger index.

05 | COLLISIONS ARE NORMAL, NOT DUPLICATES

A hash-table collision occurs when distinct keys compete for the same bucket or initial slot. The keys 10 and 17 remain different IDs even though their initial bucket is the same. They must both be preserved.

An equal key is a different situation. A second put for key 17 updates that mapping under our contract; a second set add for member 17 leaves one membership. Collision resolution must compare actual keys rather than assume that sharing a bucket means equality.

A full hash-code collision and a collision after reduction to a smaller table range are related but distinct events. Either way, the table must retain enough information to distinguish unequal keys.

06 | SEPARATE CHAINING: KEEP SEVERAL ENTRIES IN A BUCKET

BUCKET 0

Empty

BUCKET 1

Empty

BUCKET 2

Empty

BUCKET 3

10: Maya | 17: Leo | 24: Sam

BUCKET 4

Empty

BUCKET 5

Empty

BUCKET 6

Empty

Separate chaining with 7 buckets; bucket 3 retains all three unequal keys.

Separate chaining gives each bucket a collection of entries. Our teaching model uses a list of key-value pairs in each bucket. A linked chain is another familiar representation; real libraries may use additional techniques.

To add an unequal colliding key, store another entry in that bucket. Do not overwrite the previous entry. Chaining can store more entries than buckets, so its load factor can exceed 1 without being mathematically invalid.

07 | LOOKUP AND UPDATE WITH CHAINING

Get key 24 from bucket 3 Action
Inspect stored key 10 Unequal: continue
Inspect stored key 17 Unequal: continue
Inspect stored key 24 Equal: return Sam

A lookup calculates the same starting bucket used for insertion and searches the entries according to the collision policy. If no stored key matches, apply the missing-key policy. Our custom map raises KeyError.

A put for existing key 17 changes its value and leaves the entry count unchanged. A put for new key 31 adds a distinct entry and increments the count. Equal-key updates and unequal-key collisions must follow different branches.

08 | REMOVE FROM A CHAIN WITHOUT LOSING ITS NEIGHBOURS

After finding a matching entry inside a chained bucket, remove only that pair. Other colliding keys stay in the bucket and remain reachable by later lookups. If the key is absent, our remove operation returns False without changing state.

For the bucket holding 10, 17 and 24, removing 17 leaves 10 and 24. A later get(24) must still succeed. The exact removal cost depends on the bucket representation: removing from a Python list may shift later pairs within that bucket.

Unlike basic open-addressed probing, this bucket-list model does not need a tombstone marker to keep a probe path intact. The collision mechanism determines the correct deletion rule.

09 | LOAD FACTOR: COUNT ENTRIES RELATIVE TO CAPACITY

Quantity Meaning Worked value
n Number of stored distinct entries 3
m Number of buckets or slots 7
α = n / m Current load factor 3 / 7 ≈ 0.429

Load factor relates the amount of logical data to the table size. It is not a count of collisions and does not say whether one particular bucket is crowded. Three entries can be spread over three buckets or all collide in one.

With chaining, α is the average number of entries per bucket and may exceed 1. With ordinary open addressing, each live entry occupies one slot, so live-entry load cannot exceed 1. Deleted markers can still affect probing even when they are not counted as live entries.

10 | OPEN ADDRESSING: FIND ANOTHER SLOT IN THE TABLE

Open addressing keeps entries in the table slots themselves. If the initial slot holds an unequal key, follow a defined probe sequence to find that key or a place where a new entry can be stored.

Insert into 7 initially empty slots Probe route Stored position
10 3 3
17 3 occupied, then 4 4
24 3 occupied, 4 occupied, then 5 5

This example uses linear probing: try index (start + i) MOD m for i = 0, 1, 2 and so on. Wraparound after the final index returns to 0. The keys still keep their original values; their displaced location is an implementation detail.

11 | SEARCH MUST FOLLOW THE SAME PROBE RULE

To find 24 in the linear-probing example, start at 24 MOD 7 = 3. Compare key 10, then 17, then 24. Looking only at slot 3 would falsely report the key absent.

A never-used empty slot normally proves absence along that probe path. A deleted marker does not. Searches must be bounded, such as at most m probes in this simple model, so a full or marker-filled table cannot cause an infinite loop.

Linear probing can create clusters of occupied slots, increasing later probe lengths. Other strategies include quadratic probing and double hashing; their step and capacity choices must give a suitable probe coverage rather than assuming every formula reaches every slot.

12 | DELETED IS NOT THE SAME AS NEVER USED

After removing 17 from the probed table Slot 3 Slot 4 Slot 5
Correct marker state 10 DELETED 24
Unsafe empty-state interpretation 10 NEVER USED 24

A lookup for 24 must continue past the deleted slot 4 to reach slot 5. If removal incorrectly labels slot 4 as never used, a normal search can stop too early and miss 24.

A tombstone marks an available-for-reuse slot whose old occupancy must not terminate a search. Some algorithms instead repair the probe cluster after deletion; the teaching example uses tombstones because the distinction is easy to see.

13 | REUSE A TOMBSTONE WITHOUT CREATING A DUPLICATE

An insertion can remember the first tombstone encountered, but it may need to continue probing to check whether the key already exists farther along the path. Storing immediately in that tombstone could create a second copy of an existing key.

Suppose slot 3 holds 10, slot 4 is DELETED and slot 5 holds 24. Inserting 24 must find and update slot 5, not create a new 24 at slot 4. Inserting new 31 can reuse slot 4 once the search has established that 31 is absent.

The probe loop also needs a full-table outcome. If every slot is occupied by a live unequal key, either resize under the implementation policy or report failure. Do not overwrite a live entry.

14 | RESIZE POLICY AND CURRENT LOAD ARE NOT THE SAME

The current load factor is n/m. A maximum-load threshold is a policy used to decide when to grow or rebuild. A threshold of 0.75 means an implementation might trigger growth when a new distinct insertion would exceed the chosen rule; it is not the current load of every table.

Example policy calculation Result
6 entries in 8 slots α = 0.75
Adding a seventh distinct entry before growth 7/8 = 0.875
7 entries after growing to 16 slots 7/16 = 0.4375

Different implementations use different capacities, thresholds and marker policies. Java HashMap documents a default load-factor setting of 0.75. Do not apply that number as a universal rule for Python dict, Python set or every open-addressing design.

Java HashMap reference

15 | REHASH: RECOMPUTE LOCATIONS FOR THE NEW CAPACITY

Key Old index MOD 7 New index MOD 11
10 3 10
17 3 6
24 3 2

BUCKET 0

Empty

BUCKET 1

Empty

BUCKET 2

24: Sam

BUCKET 3

Empty

BUCKET 4

Empty

BUCKET 5

Empty

BUCKET 6

17: Leo

BUCKET 7

Empty

BUCKET 8

Empty

BUCKET 9

Empty

BUCKET 10

10: Maya

After rehashing the same logical entries into 11 buckets, their MOD-based locations change.

Growing the array and leaving entries in their old slots is not enough when the index rule depends on capacity. Reinsert or reposition entries under the new rule so later lookups search the correct locations.

A rebuild costs work across the entries and capacity. Occasional resizing can support good amortized performance, but the single insertion that triggers a rebuild may be expensive. If poor hashes all remain equal, adding capacity alone cannot guarantee useful distribution.

16 | INTERACTIVE COLLISION AND REHASH WALKTHROUGHS

Choose a scenario and predict each inspected bucket or slot. These are small, explicitly defined teaching models using key MOD capacity. They are not animations of Python or Java’s exact internal layout.

The display separates current live-entry load from the probe or bucket route. In the tombstone case, watch an equal-key update continue past the deleted marker before a new unequal key reuses it.

17 | HOW A HASH-BASED SET PRESERVES UNIQUENESS

To add an element to a hash-based set, use its hash to locate the appropriate bucket or probe route, then compare candidate elements for equality. If an equal element is already present, preserve one membership. If only unequal collisions are found, continue under the collision strategy.

A set needs member storage but no separate application-supplied value per member. A map stores a value associated with each distinct key. Java HashSet uses a backing HashMap as an implementation technique; the user-facing set contract still differs from the map contract.

Java HashSet reference

Neither a shared bucket nor a shared hash code is sufficient proof that two elements are equal. The equality rule is essential for both uniqueness and collision correctness.

18 | PYTHON DICT: KEYED VALUES

students = {10: "Maya", 17: "Leo", 24: "Sam"}
students[17] = "Leo updated"
print(students[17])
print(24 in students)
print("Sam" in students)
print("Sam" in students.values())
print(students.get(99, "Not found"))
# Leo updated
# True
# False
# True
# Not found

Dictionary membership checks keys, not values. Direct indexing an absent key raises KeyError, while get can return a supplied default. A default equal to a legitimate stored value may not distinguish absence, so use a membership check or sentinel if the application needs that distinction.

Python dict preserves insertion order as a language guarantee. Updating a key’s value does not move its position. This does not make lookup a binary search or mean a general map ADT must promise insertion order.

19 | PYTHON SET: DISTINCT MEMBERSHIP

registered = {17, 24}
registered.add(17)
registered.add(31)
registered.discard(99)
print(sorted(registered))
print(24 in registered)
# [17, 24, 31]
# True

Set add leaves an existing membership unduplicated. discard tolerates an absent member, while remove raises KeyError. The Python set does not promise an iteration sequence; sorted creates a presentation list.

dict keys and set elements must be hashable. Immutable strings and suitable tuples can be used, whereas mutable lists cannot normally serve as keys or set members. The logical ADT and the chosen implementation’s element requirements are related but distinct.

Python dictionary and set reference

20 | JAVA HASHMAP AND HASHSET

Task HashMap use HashSet use
Create Use Map with a HashMap implementation Use Set with a HashSet implementation
Add or update put(key, value) add(element)
Test membership containsKey(key) contains(element)
Read associated value get(key) / getOrDefault No separate mapped value in the set contract
Remove remove(key) remove(element)

HashMap does not promise iteration order; HashSet also does not. Use a separately chosen ordered collection or sorted presentation when the requirement needs it. Java Map.get can return null for absence, but HashMap also permits null values, so containsKey distinguishes those cases.

Java put returns the previous mapped value, whereas the custom teaching map below returns whether a new key was inserted. Do not assume matching names imply identical return contracts.

21 | COMPLETE PYTHON CHAINED MAP

Save this as chained_map_demo.py. It intentionally uses integer key MOD capacity, independent list buckets, explicit missing-key errors and manual rehashing. It does not automatically resize or reproduce a built-in hash-table implementation.

class ChainedMap:
    def __init__(self, capacity=7):
        if type(capacity) is not int or capacity <= 0:
            raise ValueError("Capacity must be a positive integer")
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0

    @property
    def capacity(self):
        return len(self._buckets)

    @property
    def size(self):
        return self._size

    @property
    def load_factor(self):
        return self.size / self.capacity

    def _index(self, key):
        if type(key) is not int:
            raise TypeError("This teaching map uses integer keys")
        return key % self.capacity

    def put(self, key, value):
        bucket = self._buckets[self._index(key)]
        for i, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                bucket[i] = (key, value)
                return False
        bucket.append((key, value))
        self._size += 1
        return True

    def get(self, key):
        bucket = self._buckets[self._index(key)]
        for stored_key, value in bucket:
            if stored_key == key:
                return value
        raise KeyError(key)

    def remove(self, key):
        bucket = self._buckets[self._index(key)]
        for i, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                bucket.pop(i)
                self._size -= 1
                return True
        return False

    def items(self):
        return tuple(pair for bucket in self._buckets for pair in bucket)

    def rehash(self, capacity):
        if type(capacity) is not int or capacity <= 0:
            raise ValueError("Capacity must be a positive integer")
        entries = self.items()
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0
        for key, value in entries:
            self.put(key, value)
table = ChainedMap(7)
table.put(10, "Maya")
table.put(17, "Leo")
table.put(24, "Sam")
print(table.get(17))
print(table.size, round(table.load_factor, 3))
print(table.put(17, "Leo updated"))
print(table.get(17), table.size)
table.rehash(11)
print(sorted(table.items()))
print(table.remove(10), table.remove(99))
print(sorted(table.items()))

put returns True for a new key and False for an equal-key update. get raises KeyError when absent; remove returns a Boolean. Rehash changes the bucket layout but preserves every mapping. The initial load 3/7 prints as 0.429 after rounding.

The bucket comprehension creates independent lists. Writing [[]] * capacity would repeat references to one shared bucket, which would not represent the intended table.

22 | COMPLETE BUILT-IN PYTHON AND JAVA EXAMPLES

The Python program uses the real dict and set APIs rather than the integer-only teaching map. Its output includes dictionary keys in insertion order and a sorted set for presentation.

students = {10: "Maya", 17: "Leo", 24: "Sam"}
students[17] = "Leo updated"
print(students[17])
print(24 in students)
print("Sam" in students)
print(students.get(99, "Not found"))
del students[10]
print(list(students))

registered = {17, 24}
registered.add(17)
registered.add(31)
registered.discard(99)
print(sorted(registered))
print(24 in registered)

The Java program below uses HashMap and HashSet. Save it as HashCollectionsExample.java and run main. Sorted key/set copies make display predictable without promising HashMap or HashSet iteration order.

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class HashCollectionsExample {
    public static void main(String[] args) {
        Map<Integer, String> students = new HashMap<>();
        students.put(10, "Maya");
        students.put(17, "Leo");
        students.put(24, "Sam");
        students.put(17, "Leo updated");
        System.out.println(students.get(17));
        System.out.println(students.containsKey(24));
        System.out.println(students.containsValue("Sam"));
        System.out.println(students.getOrDefault(99, "Not found"));
        students.remove(10);
        System.out.println(new TreeSet<>(students.keySet()));

        Set<Integer> registered = new HashSet<>();
        registered.add(17);
        registered.add(24);
        System.out.println(registered.add(17));
        registered.add(31);
        registered.remove(99);
        System.out.println(new TreeSet<>(registered));
        System.out.println(registered.contains(24));
    }
}

Python prints Leo updated, True, False, Not found, [17, 24], [17, 24, 31], True. Java prints Leo updated, true, true, Not found, [17, 24], false, [17, 24, 31], true. The differing checks and add return are explicit in the two programs.

23 | HASH QUALITY, EQUALITY AND STABILITY

A useful hash distributes the expected keys well and is reasonably inexpensive to calculate. Equal keys must have equal hashes under the collection’s hashing contract. Unequal keys are still allowed to share a hash, so equality comparisons remain necessary.

A key must not change its hash/equality-relevant state while stored. Otherwise a later lookup can begin from a different location or compare differently from the stored entry. Immutable IDs are often easier to reason about than mutable record objects.

Hashing for a collection is not encryption or a password-storage design. This simple MOD function is chosen for easy hand tracing, not for security or universal distribution. Real string hashing and mixing do more work, and long-key processing is not literally free.

24 | EXPECTED SPEED IS NOT A UNIVERSAL GUARANTEE

Situation Consequence
Well-distributed hashing and controlled occupancy Expected short bucket/probe routes; basic operations can be expected O(1) under the stated model
Many colliding keys More equality checks or probe steps
A large chained bucket in this list-based model Lookup can take O(n) worst case
A rebuild One operation may process many entries and slots
An oversized table More spare storage and potentially more work scanning capacity

With chaining, expected lookup is commonly analysed as O(1 + α) under suitable distribution assumptions. With open addressing, long probe routes become more likely as occupancy and clustering increase. Tombstone accumulation can also require a rebuild.

Actual libraries can add implementation-specific protections. Do not assume that every real collection exactly matches the toy worst-case mechanism, and do not claim that hashing always wins over a well-balanced ordered tree for every workload.

25 | TEST COLLISION AND RESIZE CORRECTNESS

table = ChainedMap(7)
assert table.put(10, "Maya")
assert table.put(17, "Leo")
assert table.put(24, "Sam")
assert table.get(24) == "Sam"
assert table.put(17, "Updated") is False
assert table.size == 3
assert table.remove(10)
assert table.get(24) == "Sam"
table.rehash(11)
assert table.get(17) == "Updated"
assert table.get(24) == "Sam"
assert table.size == 2
assert table.remove(99) is False

Run these tests with ChainedMap defined. Also test an empty map, absent get, invalid capacity and several keys that still collide after a resize. Keep the expected mappings in an independent model.

For a probing implementation, specifically test a search beyond a tombstone, updating an equal key beyond it, wraparound, a full table and a table with only tombstones. Those cases distinguish a robust policy from a diagram that works only on the first insertion.

26 | EXPLAIN THE CONTRACT AND THE MECHANISM

A strong explanation starts with the ADT: a map associates each distinct student ID with a value, and a set tracks distinct registered IDs. Then explain the representation: hash and reduce the key, follow the collision strategy and compare actual keys. Capacity policy manages expected route lengths.

Use cause and effect: two unequal keys share a bucket, therefore overwriting the first entry would lose a mapping. A tombstone preserves a probe route, so a later key remains findable. Rehashing recalculates locations because the index rule depends on capacity.

Your challenge is to trace keys 12, 19 and 26 into seven buckets, update 19, remove 12 and rehash into eleven buckets. Record entries, indices, current load and the lookup route at every stage. This completes the B4 content sequence; continue to revision.

MATCH THE HASH-TABLE IDEA

Terminology

Terminology

ADT

A high-level specification of logical data and the operations and behaviour associated with it.

Hash table

A representation that uses hashing and collision handling to organise keyed entries.

Map

An association from distinct keys to values.

Set

Distinct membership without a separate application-supplied value per member.

Hash function

A function deriving a hash value from a key under a stated contract.

Index reduction

Mapping a hash or key-derived value into the current table’s index range.

Bucket

A table location that can hold or identify entries under the chosen representation.

Collision

Distinct keys compete for the same bucket or initial table location.

Key equality

The rule used to decide whether a candidate is the requested logical key.

Separate chaining

Store a collection of colliding entries at each bucket.

Open addressing

Store entries in table slots and resolve collisions through a probe sequence.

Linear probing

Try consecutive offsets from a starting slot, wrapping by capacity.

Probe sequence

The defined order of candidate slots used for lookup or insertion.

Clustering

Groups of occupied slots that can lengthen probe routes.

Tombstone

A deleted-slot marker that does not terminate a probe search.

Never-used slot

An empty marker that can terminate a lookup along a valid probe rule.

Load factor

Current distinct live entry count divided by bucket or slot capacity.

Load threshold

An occupancy policy setting used to trigger growth or rebuilding.

Rehashing

Rebuild or reposition entries using the current or changed table layout/index rule.

Capacity

The number of buckets or slots in the specified table model.

Equal-key update

Replace a mapped value without adding another distinct key.

Hashability

A requirement for suitable stable hashing and equality in a hashed collection.

HashMap

A Java hash-table-based implementation of Map.

HashSet

A Java Set implementation backed by a HashMap.

Python dict

Python’s mutable mapping type with insertion-order preservation.

Python set

Python’s mutable unordered collection of distinct hashable elements.

Expected cost

A cost analysis depending on stated distribution or probabilistic assumptions.

Amortized cost

Cost averaged over a sequence including occasional expensive operations.

Missing-key policy

The specified behaviour when a requested key is absent.

Representation independence

Logical behaviour can remain stable while its internal representation changes.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which distinguish the logical ADTs?
2. Which share the initial bucket under key MOD 7?
3. Which collision statements are correct?
4. Which describe the chained teaching map?
5. Which apply to load factor?
6. Which describe linear probing lookup?
7. Why continue insertion past a remembered tombstone?
8. Which describe resizing?
9. Which API statements are correct?
10. Which efficiency claims are sound?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Explain how an ADT differs from a hash-table representation.

2. Calculate initial indices for 10, 17 and 24 with key MOD 7.

3. Explain why collisions do not justify overwriting an entry.

4. Describe separate-chaining lookup and update.

5. Compare chaining and open addressing.

6. Explain why a tombstone preserves lookup correctness.

7. Explain why insertion may need to continue beyond the first tombstone.

8. Calculate the load of 6 entries in 8 slots and after adding one entry and resizing to 16.

9. Explain rehashing from capacity 7 to 11 for keys 10, 17 and 24.

10. Distinguish Python dict and set membership and ordering.

11. Evaluate the claim that hash tables always provide O(1) operations.

12. Construct a collision-focused test plan.

CALCULATE, TRACE AND EXPLAIN | COLLIDING MAPPINGS

Calculate the home buckets for keys 12, 19 and 26 using key MOD 7. Trace a chained map through insertion, an update to 19, removal of 12 and rehashing to 11 buckets. Explain why the mapping count changes only for distinct-key insertions and successful removals.

Reveal a worked check
table = ChainedMap(7)
for key, value in ((12, "A"), (19, "B"), (26, "C")):
    table.put(key, value)
assert table.size == 3
assert table.put(19, "Updated") is False
assert table.size == 3
assert table.remove(12)
table.rehash(11)
assert table.size == 2
assert table.get(19) == "Updated"
assert table.get(26) == "C"

All three initial buckets are 5. Current load is initially 3/7, stays 3/7 after the update, becomes 2/7 after removal and becomes 2/11 after rehashing. The remaining keys move to indices 8 and 4 under MOD 11. A value update does not create another distinct key.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for B4.1.6 ADTs and Hash Tables (HL) is coming soon. Complete the matching task and written questions in your exercise book.