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 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.
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
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.
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.
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.