15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A hash table stores keys in an array by computing an index from each key with a hash function. The array can be smaller than the set of possible keys, so it uses less space than direct addressing, where the key itself is the index. The price is collisions: two keys can land in the same slot and need a collision strategy.
| Direct addressing | present[k] with one slot per possible key, O(U) space, O(1) per operation |
|---|---|
| Hash table | table[h(k)] with capacity m, O(m) space for the primary array |
| Example sizes | IDs 0 to 9 need 10 direct slots; h(k) = k mod 5 needs 5 |
| Collision | h(2) = h(7) = 2 when m = 5, so a collision strategy is required |
| Use direct addressing when | the whole key universe is known and small enough to allocate |
A hash function maps a key k to an array index, often written h(k).
First separate two ranges:
Suppose valid IDs are 0 through 9. The universe has 10 possible keys, even if we store only two IDs.
With direct addressing, the key itself is the index:
1A[k]A slot needs a way to say whether its key is present. We will use a boolean marker:
1present[k] = true means key k is stored
2present[k] = false means key k is absentDirect addressing requires every allowable key to be a safe array index. For a universe from 0 through 9, valid indices are exactly 0 through 9.
A hash table computes an index in a smaller range:
1table[h(k)]Its primary array can have capacity m smaller than the universe size U. The smaller primary array uses less space, and two different keys can produce the same index. That event is a collision.
Store IDs {2, 9}. Valid IDs are 0 through 9.
We will compare:
0 through 9.5, using:1h(k) = k mod 5Start with one slot for every valid ID.
| ID / index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
present | false | false | false | false | false | false | false | false | false | false |
To store ID 2, mark slot 2 present.
To store ID 9, mark slot 9 present.
The keys are located by their own values:
Direct addressing gives every ID 0 to 9 its own slot. Hashing with k mod 5 uses 5 slots, so 2 and 9 fit, but a later key 7 lands on index 2 and collides.
Use five primary slots, indexed 0 through 4.
For ID 2:
1h(2) = 2 mod 5 = 2For ID 9:
1h(9) = 9 mod 5 = 4The two keys use different hash indices.
| Hash index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Stored key | empty | empty | 2 | empty | 9 |
The hash table allocates 5 primary slots rather than 10.
Consider a future key 7:
1h(7) = 7 mod 5 = 2Key 7 maps to index 2, where key 2 already maps. The smaller index range creates a collision.
Keep the two representations separate. Direct addressing uses the original ID as an index. Hashing computes a smaller index first.
State 0: all valid IDs are absent.
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
present | false | false | false | false | false | false | false | false | false | false |
State 1: insert ID 2.
Use the key as the index:
1present[2] ← true| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
present | false | false | true | false | false | false | false | false | false | false |
State 2: insert ID 9.
Use the key as the index:
1present[9] ← true| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
present | false | false | true | false | false | false | false | false | false | true |
Only two IDs are stored, but all 10 slots were allocated. The other eight slots are unused.
State 3: hash-table primary array is empty.
| Hash index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Stored key | empty | empty | empty | empty | empty |
State 4: insert 2, then insert 9.
First:
1h(2) = 2 mod 5 = 2Place 2 at index 2.
Then:
1h(9) = 9 mod 5 = 4Place 9 at index 4.
| Hash index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Stored key | empty | empty | 2 | empty | 9 |
No collision occurs for the stored IDs in this example.
State 5: compare allocation.
0 through 9.0 through 4.Test the future key 7:
1h(7) = 7 mod 5 = 2Index 2 is already associated with key 2. A plain one-key-per-slot array cannot hold both keys unless the hash table has a stated collision strategy.
In the direct-address table, the rule is simple:
A valid key
kis represented only at slotk.
For our presence table, that becomes:
1present[k] is true exactly when key k is currently stored.No search through other slots occurs. To answer “Is key 9 present?”, inspect slot 9.
The rule depends on two conditions:
k must be in the declared universe.For the valid universe 0 through 9, key 10 is not a valid index. Accessing present[10] is not a valid direct-address operation. Reject it before indexing.
Hashing has a related rule:
A stored key must remain discoverable from its hash index under the selected collision policy.
Distinct keys can share a hash index, so a hash-table lookup cannot treat an occupied index as proof that the requested key is present. The lookup must validate key equality.
For example, both 2 and 7 hash to 2 when m = 5. If index 2 contains key 2, a lookup for 7 must compare the stored key with 7. The keys are different.
Before claiming that a hash table can store both colliding keys, the design must state its collision strategy. The primary array alone does not provide that guarantee.
Implement direct addressing for a declared universe from 0 through maxKey.
The table needs maxKey + 1 slots because both endpoints are included:
1valid keys: 0, 1, ..., maxKey
2indices: 0, 1, ..., maxKeyFor each requested operation:
0 ≤ key ≤ maxKey.insert(k) writes true to present[k].delete(k) writes false to present[k].contains(k) returns present[k].No loop is needed inside one direct-address operation. One valid operation reads or writes one array slot.
Use this algorithm when the full universe is known and manageable as an array. If valid keys range from 0 through 999999, an empty direct-address table still allocates one million slots. The representation requires that allocation regardless of the number of stored keys.
The pseudocode uses a universe beginning at 0.
Input: maxKey, the greatest allowable key, and operations, a sequence of operations of the forms INSERT(k), DELETE(k), and CONTAINS(k).
Return value: A sequence of results, one per operation. CONTAINS produces true or false. An out-of-range operation produces REJECTED. Valid INSERT and DELETE produce APPLIED.
Mutation behavior: The procedure creates and mutates a local present array. It does not modify operations.
11 procedure RunDirectAddressTable(maxKey, operations) -> results
22 require maxKey >= 0
33
44 present ← new boolean array with indices 0 through maxKey
55 for index ← 0 to maxKey
66 present[index] ← false
77
88 results ← empty sequence
99
1010 for each operation in operations
1111 k ← operation.key
1212
1313 if k < 0 or k > maxKey
1414 append REJECTED to results
1515 continue
1616
1717 if operation.type = INSERT
1818 present[k] ← true
1919 append APPLIED to results
2020
2121 else if operation.type = DELETE
2222 present[k] ← false
2323 append APPLIED to results
2424
2525 else if operation.type = CONTAINS
2626 append present[k] to results
2727
2828 else
2929 append REJECTED to results
3030
3131 return resultsHelper contract for the array:
1new boolean array with indices 0 through maxKeyThe helper creates exactly maxKey + 1 boolean slots. The caller may access only indices from 0 through maxKey.
Use the original stored IDs {2, 9} with valid IDs 0 through 9.
1maxKey = 9
2operations = [INSERT(2), INSERT(9), CONTAINS(2), CONTAINS(9)]maxKey = 9, so the requirement holds.present with indices 0 through 9.false.| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
present | false | false | false | false | false | false | false | false | false | false |
results = [].INSERT(2)INSERT(2).k ← 2.2 < 0 is false, and 2 > 9 is false. Do not reject.INSERT.present[2] ← true.APPLIED.| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
present | false | false | true | false | false | false | false | false | false | false |
1results = [APPLIED]INSERT(9)INSERT(9).k ← 9.9 is within 0 through 9.INSERT.present[9] ← true.APPLIED.| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
present | false | false | true | false | false | false | false | false | false | true |
1results = [APPLIED, APPLIED]CONTAINS(2)CONTAINS(2).k ← 2.2 is within range.CONTAINS.present[2], which is true.1results = [APPLIED, APPLIED, true]CONTAINS(9)CONTAINS(9).k ← 9.9 is within range.CONTAINS.present[9], which is true.1[APPLIED, APPLIED, true, true]The same bounds check rejects an invalid key. For CONTAINS(10), line 13 is true because 10 > 9. Line 14 appends REJECTED, and line 15 avoids indexing present[10].
We prove correctness for valid direct-address operations and then account for rejected out-of-range operations.
Before processing operations, every slot is initialized to false. No valid key is represented as stored. The following rule holds:
1For every key k from 0 through maxKey,
2present[k] is true exactly when k has been inserted and not subsequently deleted.Consider one valid operation with key k.
INSERT(k), line 18 sets only present[k] to true. Key k is now stored. Every other key keeps its previous slot and status.DELETE(k), line 22 sets only present[k] to false. Key k is now absent. Every other key keeps its previous slot and status.CONTAINS(k), line 26 reads present[k] without changing the table. The maintained rule states that the marker represents whether k is stored, so the returned value is correct.Each valid operation preserves the rule after it runs.
The operation loop terminates because it processes one operation per iteration and the input operation sequence is finite. When it ends, every CONTAINS(k) result was read from the slot that represents exactly that key, after all preceding inserts and deletes updated that slot. The returned membership results are correct.
For an out-of-range key, lines 13–15 reject the operation before any array access. The declared direct-address universe contains only keys from 0 through maxKey; no table slot represents any other key.
A hash table needs an additional correctness condition. If collisions are possible, a lookup at h(k) must check key equality, and insertion must follow a declared collision policy. Without those requirements, an occupied hash index cannot prove that the requested key is present or guarantee that every colliding key remains stored.
For one valid INSERT, DELETE, or CONTAINS operation:
No search across the table occurs. Each operation therefore takes O(1) time.
For q requested operations, the main loop runs q times. Its total processing time is O(q).
Initialization is separate:
0 through maxKey.maxKey + 1, which is the universe size U.Initialization takes O(U) time.
The table has one boolean slot for every allowable key.
1U = maxKey + 1The table uses O(U) space, even if no keys are stored.
For the edge case with universe 0 through 0, U = 1, so one direct-address slot is sufficient. Key 0 uses that single slot.
For the sparse case with universe 0 through 999999 and no stored keys, the representation still allocates 1,000,000 slots.
The result sequence uses space proportional to the number of operations, O(q). Excluding returned results, the direct-address table is the main auxiliary storage: O(U).
For a hash table with capacity m:
O(1) when the hash computation is constant time.m slots, so that primary array uses O(m) space.The complete time and space cost of hash-table operations depends on the collision strategy. The primary array alone does not specify how colliding keys are found or stored.
Incorrect assumption: “Allocate only up to the largest ID seen so far.”
Suppose the first operation is:
1INSERT(2)The implementation allocates slots 0 through 2.
Later, the input contains:
1INSERT(1000000)Wrong state or outcome: The array is too small for direct indexing, or the program attempts an impractically large resize based only on a newly observed ID.
Correction: Use direct addressing only when the complete key universe is known and manageable. If IDs may later be much larger, use hashing instead of treating the currently largest observed key as the universe boundary.
Incorrect line or policy:
1hashTable[h(k)] ← kwith no collision handling.
Use capacity m = 5:
1INSERT(2)
2INSERT(7)The indices are:
1h(2) = 2 mod 5 = 2
2h(7) = 7 mod 5 = 2After the first insert, index 2 contains 2. After the second insert, the incorrect code overwrites it with 7.
Wrong state: Key 2 is lost.
| Hash index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Stored key after incorrect inserts | empty | empty | 7 | empty | empty |
Correction: State and implement a collision policy before claiming that the table can store both keys. A lookup must validate the key instead of merely observing that index 2 is occupied.
Incorrect line:
1return trueafter accessing a valid slot, without checking its marker.
Use an empty direct-address table for keys 0 through 9:
1CONTAINS(9)Slot 9 exists because 9 belongs to the universe, but it has not been marked present.
Wrong output: The implementation reports that 9 is stored.
Correction: Store and inspect a presence marker:
1return present[9]In the empty table, present[9] is false, so the correct membership result is false.
Executable objective: Given a declared key universe and a list of insert, delete, and contains operations, implement a direct-address presence table that returns correct membership results and rejects out-of-range keys.
Your implementation will be tested against this contract:
k only as index k after verifying that k is in range.INSERT(k) marks k present.DELETE(k) marks k absent.CONTAINS(k) returns the current marker for k.1def run_direct_address_table(max_key, operations):
2 present = [False] * (max_key + 1) # one slot per allowed key
3 results = []
4 for kind, k in operations:
5 if k < 0 or k > max_key: # reject before indexing
6 results.append("REJECTED")
7 elif kind == "INSERT":
8 present[k] = True
9 results.append("APPLIED")
10 elif kind == "DELETE":
11 present[k] = False
12 results.append("APPLIED")
13 elif kind == "CONTAINS":
14 results.append("true" if present[k] else "false")
15 else:
16 results.append("REJECTED")
17 return results
18
19ops = [("INSERT", 2), ("INSERT", 9), ("CONTAINS", 2), ("CONTAINS", 9), ("CONTAINS", 10)]
20print("[" + ", ".join(run_direct_address_table(9, ops)) + "]")
21
22m = 5
23print("direct slots: 10, hash slots:", m)
24print(", ".join(f"h({k})={k % m}" for k in (2, 9, 7)))1import java.util.ArrayList;
2import java.util.List;
3
4public class Main {
5 static List<String> runDirectAddressTable(int maxKey, String[] kinds, int[] keys) {
6 boolean[] present = new boolean[maxKey + 1]; // one slot per allowed key
7 List<String> results = new ArrayList<>();
8 for (int i = 0; i < kinds.length; i++) {
9 int k = keys[i];
10 if (k < 0 || k > maxKey) { // reject before indexing
11 results.add("REJECTED");
12 } else if (kinds[i].equals("INSERT")) {
13 present[k] = true;
14 results.add("APPLIED");
15 } else if (kinds[i].equals("DELETE")) {
16 present[k] = false;
17 results.add("APPLIED");
18 } else if (kinds[i].equals("CONTAINS")) {
19 results.add(present[k] ? "true" : "false");
20 } else {
21 results.add("REJECTED");
22 }
23 }
24 return results;
25 }
26
27 public static void main(String[] args) {
28 String[] kinds = {"INSERT", "INSERT", "CONTAINS", "CONTAINS", "CONTAINS"};
29 int[] keys = {2, 9, 2, 9, 10};
30 System.out.println("[" + String.join(", ", runDirectAddressTable(9, kinds, keys)) + "]");
31
32 int m = 5;
33 System.out.println("direct slots: 10, hash slots: " + m);
34 System.out.println("h(2)=" + 2 % m + ", h(9)=" + 9 % m + ", h(7)=" + 7 % m);
35 }
36}1#include <iostream>
2#include <string>
3#include <utility>
4#include <vector>
5using namespace std;
6
7vector<string> runDirectAddressTable(int maxKey, const vector<pair<string, int>>& operations) {
8 vector<bool> present(maxKey + 1, false); // one slot per allowed key
9 vector<string> results;
10 for (const auto& [kind, k] : operations) {
11 if (k < 0 || k > maxKey) { // reject before indexing
12 results.push_back("REJECTED");
13 } else if (kind == "INSERT") {
14 present[k] = true;
15 results.push_back("APPLIED");
16 } else if (kind == "DELETE") {
17 present[k] = false;
18 results.push_back("APPLIED");
19 } else if (kind == "CONTAINS") {
20 results.push_back(present[k] ? "true" : "false");
21 } else {
22 results.push_back("REJECTED");
23 }
24 }
25 return results;
26}
27
28int main() {
29 vector<pair<string, int>> ops = {{"INSERT", 2}, {"INSERT", 9}, {"CONTAINS", 2}, {"CONTAINS", 9}, {"CONTAINS", 10}};
30 vector<string> res = runDirectAddressTable(9, ops);
31 cout << "[";
32 for (size_t i = 0; i < res.size(); i++) cout << (i ? ", " : "") << res[i];
33 cout << "]" << endl;
34
35 int m = 5;
36 cout << "direct slots: 10, hash slots: " << m << endl;
37 cout << "h(2)=" << 2 % m << ", h(9)=" << 9 % m << ", h(7)=" << 7 % m << endl;
38}1function runDirectAddressTable(maxKey, operations) {
2 const present = new Array(maxKey + 1).fill(false); // one slot per allowed key
3 const results = [];
4 for (const [kind, k] of operations) {
5 if (k < 0 || k > maxKey) { // reject before indexing
6 results.push('REJECTED');
7 } else if (kind === 'INSERT') {
8 present[k] = true;
9 results.push('APPLIED');
10 } else if (kind === 'DELETE') {
11 present[k] = false;
12 results.push('APPLIED');
13 } else if (kind === 'CONTAINS') {
14 results.push(present[k] ? 'true' : 'false');
15 } else {
16 results.push('REJECTED');
17 }
18 }
19 return results;
20}
21
22const ops = [['INSERT', 2], ['INSERT', 9], ['CONTAINS', 2], ['CONTAINS', 9], ['CONTAINS', 10]];
23console.log(`[${runDirectAddressTable(9, ops).join(', ')}]`);
24
25const m = 5;
26console.log(`direct slots: 10, hash slots: ${m}`);
27console.log(`h(2)=${2 % m}, h(9)=${9 % m}, h(7)=${7 % m}`);A hash table answers "is this key stored, and what belongs to it?" without scanning every entry. It computes an index from the key and reads that slot. Typical uses are sets, maps, frequency counts and caches.
A program that maps user IDs to profiles. Each lookup turns the ID into an array index and reads that slot, with no search. A web cache keyed by URL works the same way.
In Java, use HashMap. Hashtable is a legacy class that synchronizes every method and rejects null keys and values. HashMap is unsynchronized and allows one null key. For thread-safe maps, use ConcurrentHashMap.
No. The abstract data type is the map (or set), with put, get and remove. A hash table is one data structure that implements it. A balanced tree is another.
It allocates one slot per possible key, even when you store two keys. For IDs 0 through 999999, an empty table still holds 1,000,000 slots. It also needs every key to be a safe array index.