15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A hash function maps a key to an array index. The division method computes h(k) = k mod m, which always lands in 0 through m - 1 and returns the same index for the same key. It takes O(1) time, but different keys can share an index, and that is a collision.
| Division method | h(k) = k mod m, for a nonnegative key and capacity m > 0 |
|---|---|
| Index range | 0 through m - 1 |
| Cost per call | O(1) time and O(1) auxiliary space |
| Determinism | same key, same capacity, same function gives the same index |
| Collision example | h(10) = h(17) = 3 when m = 7; the function does not say how to store both |
| Invalid input | capacity 0 is rejected, because modulo by zero has no index range |
A key is the input value used to locate stored data. In this lesson, keys are nonnegative integers.
A hash function turns a key into an array index. For a table with capacity m, its valid indices are:
We will use this hash function:
Here:
k is the key.m is the table capacity.k mod m is the remainder after dividing k by m.For this lesson, capacity must be positive. If m = 0, modulo is undefined and there is no valid index range.
Use a table of capacity:
Its index range is 0 through 6.
The keys are:
The hash function is:
Start with the table indices visible:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| State 0 | empty | empty | empty | empty | empty | empty | empty |
Now compute the first key:
Key 10 maps to index 3.
The index 3 is not the key. The key is still 10. The number 3 only tells us where this hash function sends that key.
The array is still only a set of possible destinations. This lesson does not choose a policy for storing keys when two keys choose the same destination.
With h(k) = k mod 7, keys 10 and 17 both map to index 3 while 4 maps to index 4. Different keys can share an index, and the hash alone does not say how both fit.
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Table state | empty | empty | empty | empty | empty | empty | empty |
| Key | Computed index |
|---|---|
| 10 | 3 |
Key 10 points to index 3.
| Key | Computed index |
|---|---|
| 10 | 3 |
| 17 | 3 |
Key 17 also points to index 3.
Two distinct keys, 10 and 17, map to the same index. The shared index is a collision.
A collision does not mean the keys are equal:
The keys have equal hash indices for capacity 7.
| Key | Computed index |
|---|---|
| 10 | 3 |
| 17 | 3 |
| 4 | 4 |
Key 4 points to index 4.
The table capacity gives only seven possible indices:
There can be more possible keys than possible indices. Distinct keys can therefore share an index. The pigeonhole principle permits collisions.
A hash function tells us which index to begin with. By itself, it does not tell us how both 10 and 17 should be stored at index 3.
Look at the same key twice while capacity stays 7:
Compute it again:
The result does not change. A lookup depends on this behavior. If an inserted key went to one index but a later search computed a different index, the search could miss the key.
The central invariant is:
For a fixed capacity and hash function, every lookup for a given key computes the same valid index.
There are two parts.
m, k mod m is in the range 0 through m - 1.k, m, and hash function, the remainder calculation produces the same remainder.The invariant does not say that different keys get different indices. The example already showed why:
Equal indices do not imply equal keys.
We need a small operation that accepts a nonnegative integer key and a positive capacity.
Start from the required index range:
For a positive m, the remainder of a nonnegative key divided by m already has exactly that property. Compute:
Before computing it, reject m = 0. There is no index range from 0 through -1, and modulo by zero is undefined.
The operation has no collision-handling step. If 10 and 17 both produce 3, this operation returns 3 for each key. Another part of a hash table would need a defined policy to store and later distinguish colliding keys.
Input
key: a nonnegative integer key.capacity: an integer table capacity.Return
0 through capacity - 1 when capacity > 0.Failure behavior
capacity = 0 as invalid.Mutation behavior
key, capacity, or any table.Helper contract
remainder(a, b) returns the remainder of nonnegative integer a divided by positive integer b.0 through b - 1.11 function hashIndex(key, capacity):
22 require key >= 0
33 if capacity <= 0:
44 reject "capacity must be positive"
55
66 index <- remainder(key, capacity)
77 return indexFor this lesson, line 6 is equivalent to:
1index <- key mod capacityUse the original capacity 7 and keys [10, 17, 4].
The function runs separately once per key. It does not store the keys.
hashIndex(10, 7)| Line | Action | Result |
|---|---|---|
| 1 | Receive key = 10, capacity = 7. | Inputs are unchanged. |
| 2 | Check key >= 0. | 10 >= 0, so continue. |
| 3 | Check capacity <= 0. | 7 <= 0 is false. |
| 6 | Compute remainder(10, 7). | 10 mod 7 = 3, so index = 3. |
| 7 | Return index. | Returns 3. |
Mapping after this call:
hashIndex(17, 7)| Line | Action | Result |
|---|---|---|
| 1 | Receive key = 17, capacity = 7. | Inputs are unchanged. |
| 2 | Check key >= 0. | 17 >= 0, so continue. |
| 3 | Check capacity <= 0. | 7 <= 0 is false. |
| 6 | Compute remainder(17, 7). | 17 mod 7 = 3, so index = 3. |
| 7 | Return index. | Returns 3. |
Mapping after this call:
The second result matches the first index, so the keys collide. The function still returns a valid index.
hashIndex(4, 7)| Line | Action | Result |
|---|---|---|
| 1 | Receive key = 4, capacity = 7. | Inputs are unchanged. |
| 2 | Check key >= 0. | 4 >= 0, so continue. |
| 3 | Check capacity <= 0. | 7 <= 0 is false. |
| 6 | Compute remainder(4, 7). | 4 mod 7 = 4, so index = 4. |
| 7 | Return index. | Returns 4. |
Final mappings:
There is no loop or recursion here, so correctness follows directly from the checks and the remainder operation.
Assume capacity > 0, because line 3 rejects any nonpositive capacity.
At line 6, the algorithm computes:
By the contract of remainder for a nonnegative key and positive capacity:
The returned index is therefore always in the valid table range:
For fixed key and fixed positive capacity, line 6 performs the same remainder calculation each time.
Two evaluations produce the same result:
The function does not modify either input. If the key and capacity remain unchanged, a later lookup computes the same valid index as an earlier operation.
The algorithm returns an index, not a claim that two keys are equal.
For example:
Both calls return 3, while 10 and 17 remain distinct keys. A complete hash table must compare keys and use a collision policy to decide how colliding keys are stored. This hash function alone does not specify that policy.
For one call to hashIndex:
key and capacity.capacity <= 0.The number of these steps does not depend on how many entries are already stored in a table. There is no loop over entries and no collision-handling work in this function.
Index computation uses:
Insertion, search, and deletion in a complete hash table can take different amounts of time. Those operations depend on a collision-handling policy, which has not been defined here.
capacity as an indexIncorrect assumption: h(key) may return capacity.
Incorrect line:
1index <- capacitySmallest exposing input:
1key = 7
2capacity = 7Wrong result:
1index = 7A capacity-7 table has indices only from 0 through 6. Index 7 is outside the table.
Correction:
1index <- key mod capacityThen:
So the correct index is 0.
Incorrect assumption: Keys 10 and 17 are the same because both hash to 3 when m = 7.
Exposing input:
1capacity = 7
2keys = 10, 17Wrong state:
110 -> 3
217 -> 3
3therefore discard one keyThe operation discards a distinct key. The equality claim is false:
Correction: Compare keys for equality. Shared indices are collisions, not proof that keys are identical. A separate collision policy is required to store both keys.
Incorrect approach:
1index <- random value from 0 through capacity - 1Exposing input:
1insert key = 10
2search for key = 10Wrong state:
3.5.Correction:
1index <- key mod capacityThe same key with the same capacity always computes the same index.
Incorrect line:
1index <- key mod capacitywith no capacity check.
Exposing input:
1key = 0
2capacity = 0Wrong result: The program attempts modulo by zero. There is also no valid index range for a zero-capacity table.
Correction:
1if capacity <= 0:
2 reject "capacity must be positive"| Key | Capacity | Calculation | Correct index |
|---|---|---|---|
| 0 | 7 | 0 mod 7 | 0 |
| 6 | 7 | 6 mod 7 | 6 |
| 7 | 7 | 7 mod 7 | 0 |
| any nonnegative key | 1 | key mod 1 | 0 |
With capacity 1, index 0 is the only valid index, so every nonnegative key maps there.
Implement:
1hashIndex(key, capacity)Objective: For nonnegative integer keys, return the modulo index.
The tests will verify this contract for every positive capacity:
and:
The implementation must reject zero capacity rather than attempt modulo by zero.
1def hash_index(key, capacity):
2 assert key >= 0
3 if capacity <= 0:
4 raise ValueError("capacity must be positive")
5 return key % capacity # always in 0 .. capacity - 1
6
7for k in (10, 17, 4, 7):
8 print(f"{k} -> {hash_index(k, 7)}")
9print("10 and 17 collide:", str(hash_index(10, 7) == hash_index(17, 7)).lower())
10try:
11 hash_index(0, 0)
12except ValueError:
13 print("capacity 0 rejected")1public class Main {
2 static int hashIndex(int key, int capacity) {
3 if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
4 return key % capacity; // always in 0 .. capacity - 1
5 }
6
7 public static void main(String[] args) {
8 for (int k : new int[]{10, 17, 4, 7}) {
9 System.out.println(k + " -> " + hashIndex(k, 7));
10 }
11 System.out.println("10 and 17 collide: " + (hashIndex(10, 7) == hashIndex(17, 7)));
12 try {
13 hashIndex(0, 0);
14 } catch (IllegalArgumentException e) {
15 System.out.println("capacity 0 rejected");
16 }
17 }
18}1#include <iostream>
2#include <stdexcept>
3using namespace std;
4
5int hashIndex(int key, int capacity) {
6 if (capacity <= 0) throw invalid_argument("capacity must be positive");
7 return key % capacity; // always in 0 .. capacity - 1
8}
9
10int main() {
11 for (int k : {10, 17, 4, 7}) {
12 cout << k << " -> " << hashIndex(k, 7) << endl;
13 }
14 cout << "10 and 17 collide: " << (hashIndex(10, 7) == hashIndex(17, 7) ? "true" : "false") << endl;
15 try {
16 hashIndex(0, 0);
17 } catch (const invalid_argument&) {
18 cout << "capacity 0 rejected" << endl;
19 }
20}1function hashIndex(key, capacity) {
2 if (capacity <= 0) throw new Error('capacity must be positive');
3 return key % capacity; // always in 0 .. capacity - 1
4}
5
6for (const k of [10, 17, 4, 7]) {
7 console.log(`${k} -> ${hashIndex(k, 7)}`);
8}
9console.log(`10 and 17 collide: ${hashIndex(10, 7) === hashIndex(17, 7)}`);
10try {
11 hashIndex(0, 0);
12} catch (e) {
13 console.log('capacity 0 rejected');
14}Textbook methods are division (k mod m), multiplication, folding and mid-square. Multiplication scales the fractional part of k times a constant between 0 and 1 by m. Folding adds parts of the key, and mid-square takes the middle digits of its square. Universal hashing picks the function at random from a family.
It turns any key into an array index, so a lookup goes to one slot instead of scanning. Without it, a table needs one slot per possible key, as in direct addressing.
No. A table hash only needs to be fast and spread keys evenly. Cryptographic hashes such as SHA-256 add security properties and cost far more per call. This page covers the table sense.
Yes. With m = 7, keys 10 and 17 both map to index 3. The pigeonhole principle forces this when there are more possible keys than indices, so a table needs chaining or open addressing.
Reject capacity 0, because modulo by zero has no valid index range. This lesson uses nonnegative keys. In Java, C++ and JavaScript a negative key gives a negative remainder, so those languages need a fix such as ((k % m) + m) % m.