PCCST303 · Module 4: Sorting and Searching
Hashing and Hash Functions
Binary search gets search down to O(log n), but that's still not constant time. Hashing aims for O(1) average-case access by computing directly where a key belongs, instead of comparing it against other keys at all.
Idea
Definition
Hashing maps a key to an array index using a hash function h(key), so that storing or retrieving a value at that key means computing h(key) once and going straight to that position, no searching or comparing needed. The array used this way is called a hash table.
Compare this to a plain array search: to find a value, you'd normally have to check elements one by one (or, if sorted, binary search down to O(log n)). Hashing skips that entirely, by computing where the value must be, instead of searching for it.
Walking through it
Say we want to store the numbers 23, 45, 12, 8, 30 in a hash table of size m = 7 (slots 0 to 6).
We need a rule that turns any key into a slot number between 0 and 6. The remainder after dividing by 7 always lands in exactly that range, no matter how big the key is, so that's our hash function: h(key) = key mod m. This is called the division method, and it's the simplest and most common hash function.
Insert 23: h(23) = 23 mod 7 = 2, so 23 goes into slot 2.
Insert 45: h(45) = 45 mod 7 = 3, so 45 goes into slot 3.
Insert 12: h(12) = 12 mod 7 = 5, so 12 goes into slot 5.
Insert 8: h(8) = 8 mod 7 = 1, so 8 goes into slot 1.
So far, every key has landed in its own slot, computed directly with no searching. Now insert one more key:
Insert 30: h(30) = 30 mod 7 = 2.
But slot 2 is already taken by 23. Two different keys, 23 and 30, hashed to the same index. This is a collision.
Key Idea
Collisions are not a bug or a sign the hash function was chosen badly, they are mathematically unavoidable: with more possible keys than table slots, some pair of keys must eventually land on the same index (this is the same reasoning as the pigeonhole principle). What a good hash function can do is spread keys out uniformly, so collisions are rare and don't cluster, while still being fast to compute. Deciding what actually happens to 30 when its slot is already full, where it goes instead, is the job of a separate topic: collision resolution.
For a hash table of size m, h(key) must always return a value in the range 0 to m - 1 (the valid indices of an array of size m). key mod m guarantees exactly that, for any key.
Common hash functions
The walkthrough above used the division method, but it's not the only way to compute h(key). Different hash functions trade off simplicity, speed, and how well they spread out a particular kind of key. The four below are the standard techniques covered in this course, in roughly increasing order of how much they account for the internal structure of the key.
Division method
Definition
The division method is exactly what the walkthrough above used: h(key) = key mod m, where m is the table size. It's the simplest and most common hash function.
m as a prime number, not too close to a power of 2, tends to spread keys more evenly. If m shares a common factor with many keys (e.g. m = 10 with keys that are all multiples of 5), the hash values cluster instead of spreading out. The walkthrough above used m = 7, a prime, for exactly this reason.
Mid-square method
Definition
The mid-square method squares the key, then extracts a fixed number of digits from the middle of the squared result as the hash value.
For a 2-digit hash value (table size around 100), key = 44:
44² = 1936
Middle 2 digits: 93
h(44) = 9310, 20, 30, ... that would hash poorly under some other methods.
Folding method
Definition
The folding method splits the key into equal-sized parts, then adds those parts together (optionally taking the result mod m) to produce the hash value.
Example (shift folding): key = 123456789, split into 3-digit parts:
123 + 456 + 789 = 1368If a fixed-width result is needed, take the last few digits or apply mod m: 1368 mod 11 = 4.
Boundary folding is a variant where every other part is reversed before adding, meant to further mix the digits:
123 + 654 (456 reversed) + 789 = 1566Digit analysis method
Definition
The digit analysis method examines all keys in the dataset in advance, and selects the digit positions that vary the most across keys (dropping positions that are mostly constant), using only those selected digits to form the hash value.
For a set of employee IDs all starting with the same branch code, e.g. 2024-XXXX, the leading 2024- digits are useless for hashing, since every key shares them and they don't distinguish anything. Only the varying XXXX digits are used.
Comparing the four methods
| Method | Basis | Needs advance knowledge of all keys? | Good for |
|---|---|---|---|
| Division | key mod m | No | General-purpose, most common default |
| Mid-square | Middle digits of key² | No | Keys with non-random patterns |
| Folding | Sum of key's parts | No | Long keys (e.g. long numeric IDs) |
| Digit analysis | Manually chosen varying digits | Yes | Static datasets with known key structure |
Quick recall
- A hash function
h(key)maps a key directly to a table index, aiming forO(1)average lookup instead of comparison-based search. - Division:
key mod m, simplest, works best withmprime. - Mid-square: middle digits of
key², mixes all digits of the key well. - Folding: split the key into parts and add them, good for long keys.
- Digit analysis: manually pick the most-varying digit positions across a known, fixed key set.
- No hash function eliminates collisions entirely: that is handled separately by collision resolution.