15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Linear probing is an open addressing method for hash collisions. If slot h(k) is taken, it tries (h(k) + i) mod m for i = 1, 2 and so on until it finds an empty slot. Operations take expected O(1) time at a controlled load factor and O(m) in the worst case. Runs of occupied slots form primary clusters.
| Probe sequence | (h(k) + i) mod m for i = 0, 1, ..., m - 1, wrapping past the last slot |
|---|---|
| Slot states | EMPTY, OCCUPIED(key), DELETED |
| Expected time | O(1) per operation at a controlled load factor |
| Worst case time | O(m), from a long cluster or a nearly full table |
| Space | O(m), with no linked nodes |
| Delete rule | write DELETED, never EMPTY, so later probes pass through |
Assumed knowledge:
In open addressing, every entry stays directly in the hash table’s primary array. There are no linked nodes for collisions.
Each slot has one of three states:
| Slot state | Meaning |
|---|---|
EMPTY | This slot has never held an entry. |
OCCUPIED(key) | This slot currently holds key. |
DELETED | A key used to be here, but was removed. |
We will use linear probing. If key k has home index h(k), its probe sequence is:
where:
m is the table capacity,i starts at 0,0.For this lesson:
Use a table with capacity m = 7.
Insert these keys in order:
1[10, 17, 24]Then:
24.17.24 again.All three inserted keys have the same home index:
1h(10) = 10 mod 7 = 3
2h(17) = 17 mod 7 = 3
3h(24) = 24 mod 7 = 3Start with every slot EMPTY.
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| State 0 | EMPTY | EMPTY | EMPTY | EMPTY | EMPTY | EMPTY | EMPTY |
Linear probing: 10, 17 and 24 all hash to slot 3, so they fill slots 3, 4 and 5 and form one cluster.
10 hashes to slot 3.
Slot 3 is EMPTY, so place 10 there.
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| State 1 | EMPTY | EMPTY | EMPTY | 10 | EMPTY | EMPTY | EMPTY |
17 also hashes to slot 3.
3: it holds 10, not 17.(3 + 1) mod 7 = 4.4 is EMPTY.17 at slot 4.| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| State 2 | EMPTY | EMPTY | EMPTY | 10 | 17 | EMPTY | EMPTY |
The collision has created a consecutive occupied run from slot 3 through slot 4.
24 also hashes to slot 3.
3: holds 10.4: holds 17.5: it is EMPTY.24 at slot 5.| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| State 3 | EMPTY | EMPTY | EMPTY | 10 | 17 | 24 | EMPTY |
A run of adjacent occupied positions is called primary clustering. Linear probing creates these runs because every collision moves to the next position.
Start at h(24) = 3.
3 holds 10, so keep probing.4 holds 17, so keep probing.5 holds 24, so the search succeeds.Probe number i | Index (3 + i) mod 7 | Slot contents | Decision |
|---|---|---|---|
| 0 | 3 | 10 | Not 24; continue. |
| 1 | 4 | 17 | Not 24; continue. |
| 2 | 5 | 24 | Found 24. |
Search for 17 from its home index, 3.
3 holds 10; continue.4 holds 17; change that slot to DELETED.Do not change it to EMPTY.
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| State 5 | EMPTY | EMPTY | EMPTY | 10 | DELETED | 24 | EMPTY |
Start again at h(24) = 3.
3 holds 10; continue.4 is DELETED; continue.5 holds 24; find it.Probe number i | Index (3 + i) mod 7 | Slot contents | Decision |
|---|---|---|---|
| 0 | 3 | 10 | Not 24; continue. |
| 1 | 4 | DELETED | Continue; this does not end a search. |
| 2 | 5 | 24 | Found 24. |
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| State 6 | EMPTY | EMPTY | EMPTY | 10 | DELETED | 24 | EMPTY |
In State 6, 24 is outside its home index 3, and searching from index 3 still reaches it.
The following property must remain true after every operation:
For every occupied key, searching from
h(key)by the same probe rule reaches that key before reaching anEMPTYslot. ADELETEDslot does not end the search.
This is the probe-sequence invariant.
An EMPTY slot means no insertion could have passed through that never-used slot. If a key had started earlier in the same probe sequence, it would have been placed there instead of continuing past it.
A DELETED slot means an entry may have passed through it before deletion. It cannot prove that a searched key is absent.
To search for key:
h(key).m slots.key, return found.EMPTY, return absent.DELETED or holds a different key, continue.m slots were probed, return absent.Searching must stop after m probes. A full table without the key would otherwise cycle forever.
Insertion must handle both collisions and deleted slots.
While probing:
DELETED slot seen.EMPTY slot appears:
DELETED slot if one exists;EMPTY slot.m positions are checked:
DELETED slot if one exists;Deletion searches using the same probe sequence.
If it finds the key, replace OCCUPIED(key) with DELETED.
The implementation uses a deleted marker rather than a cluster-repair procedure.
1Table:
2 capacity m > 0
3 slots[0 .. m - 1]
4
5Each slots[index] is exactly one of:
6 EMPTY
7 DELETED
8 OCCUPIED(integer key)
9
10hash(key, m):
11 Input: integer key and positive capacity m
12 Return: an index in [0, m - 1]
13 Contract for this lesson: return key mod mThe operations below mutate only the one table passed to them.
1contains(table, key):
2 Input: table and integer key
3 Return: true if key is stored; otherwise false
4 Mutation: does not modify table
5
61. start <- hash(key, table.m)
72. for i <- 0 to table.m - 1:
83. index <- (start + i) mod table.m
94. slot <- table.slots[index]
105. if slot is EMPTY:
116. return false
127. if slot is OCCUPIED(key):
138. return true
149. // slot is DELETED or contains a different key; continue probing
1510. return false1insert(table, key):
2 Input: table and integer key
3 Return: INSERTED, ALREADY_PRESENT, or FULL
4 Mutation: stores key in one slot only when returning INSERTED
5
61. start <- hash(key, table.m)
72. firstDeleted <- NONE
83. for i <- 0 to table.m - 1:
94. index <- (start + i) mod table.m
105. slot <- table.slots[index]
116. if slot is OCCUPIED(key):
127. return ALREADY_PRESENT
138. if slot is DELETED and firstDeleted is NONE:
149. firstDeleted <- index
1510. if slot is EMPTY:
1611. if firstDeleted is not NONE:
1712. table.slots[firstDeleted] <- OCCUPIED(key)
1813. else:
1914. table.slots[index] <- OCCUPIED(key)
2015. return INSERTED
2116. // every slot was probed
2217. if firstDeleted is not NONE:
2318. table.slots[firstDeleted] <- OCCUPIED(key)
2419. return INSERTED
2520. return FULL1remove(table, key):
2 Input: table and integer key
3 Return: REMOVED if key was present; otherwise ABSENT
4 Mutation: changes an occupied key slot to DELETED only when returning REMOVED
5
61. start <- hash(key, table.m)
72. for i <- 0 to table.m - 1:
83. index <- (start + i) mod table.m
94. slot <- table.slots[index]
105. if slot is EMPTY:
116. return ABSENT
127. if slot is OCCUPIED(key):
138. table.slots[index] <- DELETED
149. return REMOVED
1510. // slot is DELETED or contains a different key; continue probing
1611. return ABSENTUse the original table of capacity 7.
insert(table, 10)Initial slots:
1[EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY]start <- hash(10, 7) = 3.firstDeleted <- NONE.i = 0.index <- (3 + 0) mod 7 = 3.slot <- EMPTY.OCCUPIED(10).DELETED.EMPTY.firstDeleted is NONE.OCCUPIED(10) at slot 3.INSERTED.1[EMPTY, EMPTY, EMPTY, 10, EMPTY, EMPTY, EMPTY]insert(table, 17)start <- hash(17, 7) = 3.firstDeleted <- NONE.For i = 0:
index = 3.slot = OCCUPIED(10).OCCUPIED(17).For i = 1:
index <- (3 + 1) mod 7 = 4.slot = EMPTY.EMPTY slot.firstDeleted is still NONE.OCCUPIED(17) at slot 4.INSERTED.1[EMPTY, EMPTY, EMPTY, 10, 17, EMPTY, EMPTY]insert(table, 24)start <- hash(24, 7) = 3.firstDeleted <- NONE.For i = 0, line 4 selects index 3, containing 10. Continue.
For i = 1, line 4 selects index 4, containing 17. Continue.
For i = 2:
index <- (3 + 2) mod 7 = 5.slot = EMPTY.EMPTY.firstDeleted is NONE.OCCUPIED(24) at slot 5.INSERTED.1[EMPTY, EMPTY, EMPTY, 10, 17, 24, EMPTY]contains(table, 24)start <- 3.For i = 0:
index = 3.slot = 10.EMPTY.OCCUPIED(24).For i = 1:
index = 4.slot = 17.For i = 2:
index = 5.slot = 24.OCCUPIED(24).true.remove(table, 17)start <- 3.For i = 0, index 3 holds 10; continue.
For i = 1:
index = 4.slot = OCCUPIED(17).4 to DELETED.REMOVED.1[EMPTY, EMPTY, EMPTY, 10, DELETED, 24, EMPTY]contains(table, 24) after deletionstart <- 3.For i = 0, index 3 holds 10; continue.
For i = 1:
index = 4.slot = DELETED.EMPTY.OCCUPIED(24).For i = 2:
index = 5.slot = OCCUPIED(24).true.We show that insert, contains, and remove preserve the probe-sequence invariant.
In a new table, every slot is EMPTY. There are no occupied keys, so the invariant holds immediately.
For an operation, probing begins at hash(key, m), which is the first index in that key’s defined probe sequence.
Suppose insertion examines slots in order from the key’s home index.
ALREADY_PRESENT without changing the table. Every stored key remains reachable.DELETED, it remembers the location but continues searching. This prevents insertion of a duplicate when an equal key appears later in the probe sequence.EMPTY, no earlier insertion could have passed that never-used slot. Placing the key at the first remembered DELETED slot, or at this EMPTY slot when no deleted slot was remembered, places the new key on a path reachable from its home index.EMPTY slot occurs after m probes but a DELETED slot was remembered, putting the new key there also preserves reachability.EMPTY or DELETED slot exists after m probes, every slot is occupied, so insertion correctly reports FULL.Insertion retains each distinct occupied key and preserves the invariant.
remove follows the same probe sequence as search.
If it finds the key, it replaces OCCUPIED(key) with DELETED. Searches for keys farther along the same probe sequence continue through DELETED, so their paths remain intact. Deletion preserves the invariant.
If remove reaches EMPTY, the requested key cannot be later in that probe sequence. It returns ABSENT without changing the table.
contains checks slots in the key’s probe sequence.
OCCUPIED(key), returning true is correct.DELETED markers, as required by the invariant.EMPTY, the invariant means the key cannot occur later in this sequence. Returning false is correct.m slots without finding the key, every possible table index has been checked once, so returning false is correct.Search returns true exactly when the key is stored.
Each probe performs a constant amount of work:
If an operation probes p slots, it costs:
time and uses:
auxiliary space. The algorithms keep only a few variables such as start, i, index, and firstDeleted.
With a controlled load factor and suitable hash distribution, the expected number of probes is treated as bounded in this model. Insert, search, and delete therefore have expected:
time.
A long cluster, or a table that is nearly full, can force an operation to inspect as many as m slots:
worst-case time.
The array itself stores m slots:
table storage. Open addressing does not allocate a separate linked node for each entry.
A DELETED marker in slot 4 lets the search for 24 probe past it to slot 5. Clearing slot 4 to EMPTY would end the search early and miss 24.
EMPTYIncorrect line or assumption
1table.slots[index] <- EMPTYwhen deleting a key.
Exposing input
1m = 7
2insert 10, 17, 24
3remove 17
4contains 24After inserting:
1[EMPTY, EMPTY, EMPTY, 10, 17, 24, EMPTY]The incorrect deletion produces:
1[EMPTY, EMPTY, EMPTY, 10, EMPTY, 24, EMPTY]A search for 24 checks slot 3, then sees EMPTY at slot 4 and returns absent.
Wrong result
1contains(24) = falseeven though 24 remains at slot 5.
Correction
Write DELETED, not EMPTY, so search continues through slot 4.
Incorrect line or assumption
1if slot is OCCUPIED(differentKey):
2 return falseExposing input
1m = 7
2insert 10
3insert 17
4contains 17Both keys hash to index 3.
1[EMPTY, EMPTY, EMPTY, 10, 17, EMPTY, EMPTY]The incorrect search sees 10 at slot 3 and stops.
Wrong result
1contains(17) = falseCorrection
Continue through occupied nonmatching slots. Only EMPTY ends an unsuccessful search early.
Incorrect line or assumption
1index <- start + iwithout modulo m.
Exposing input
1m = 5
2a key hashes to 4
3another key also hashes to 4The first key uses slot 4. The next probe must move from 4 to 0.
Wrong result
The second probe tries index 5, which is outside indices 0 through 4.
Correction
Use:
1index <- (start + i) mod table.mFor m = 5, a key whose home index is 4 probes:
14, 0, 1, 2, 3Incorrect line or assumption
Insert immediately into the first DELETED slot.
Exposing situation
A deleted marker appears before an existing equal key in the same probe sequence.
Wrong state
The table can store the same key twice: once in the reused deleted slot and once farther along the sequence.
Correction
Remember the first deleted position, but continue probing until finding the equal key, an EMPTY slot, or completing m probes.
Incorrect line or assumption
Probe until finding EMPTY, with no limit on the number of probes.
Exposing input
1m = 3
2all 3 slots are OCCUPIED
3insert a new distinct keyWrong behavior
The probe sequence cycles forever.
Correction
Probe at most m positions. If no EMPTY or DELETED insertion position exists, return FULL.
Implement a fixed-capacity linear-probing integer set with:
1insert(key)
2contains(key)
3remove(key)Use EMPTY and DELETED slot states.
The tests will verify this contract:
DELETED marker,Reference material for the operation model and hashing context:
1EMPTY, DELETED = -1, -2 # keys are nonnegative, so these cannot clash
2
3class LinearProbingSet:
4 def __init__(self, m):
5 self.m = m
6 self.slots = [EMPTY] * m
7
8 def hash(self, key):
9 return key % self.m
10
11 def contains(self, key):
12 start = self.hash(key)
13 for i in range(self.m): # at most m probes
14 slot = self.slots[(start + i) % self.m]
15 if slot == EMPTY:
16 return False # only EMPTY ends a search early
17 if slot == key:
18 return True
19 return False
20
21 def insert(self, key):
22 start = self.hash(key)
23 first_deleted = None
24 for i in range(self.m):
25 index = (start + i) % self.m
26 slot = self.slots[index]
27 if slot == key:
28 return "ALREADY_PRESENT"
29 if slot == DELETED and first_deleted is None:
30 first_deleted = index # remember it, keep probing
31 if slot == EMPTY:
32 self.slots[first_deleted if first_deleted is not None else index] = key
33 return "INSERTED"
34 if first_deleted is not None:
35 self.slots[first_deleted] = key
36 return "INSERTED"
37 return "FULL"
38
39 def remove(self, key):
40 start = self.hash(key)
41 for i in range(self.m):
42 index = (start + i) % self.m
43 slot = self.slots[index]
44 if slot == EMPTY:
45 return "ABSENT"
46 if slot == key:
47 self.slots[index] = DELETED # not EMPTY: later probes must pass through
48 return "REMOVED"
49 return "ABSENT"
50
51 def show(self):
52 names = {EMPTY: "EMPTY", DELETED: "DELETED"}
53 return "[" + ", ".join(names.get(s, str(s)) for s in self.slots) + "]"
54
55t = LinearProbingSet(7)
56for k in (10, 17, 24):
57 print(f"insert {k}: {t.insert(k)}")
58print("table:", t.show())
59print("contains 24:", str(t.contains(24)).lower())
60print("remove 17:", t.remove(17))
61print("table:", t.show())
62print("contains 24:", str(t.contains(24)).lower())1public class Main {
2 static final int EMPTY = -1, DELETED = -2; // keys are nonnegative, so these cannot clash
3
4 static class LinearProbingSet {
5 final int m;
6 final int[] slots;
7
8 LinearProbingSet(int m) {
9 this.m = m;
10 this.slots = new int[m];
11 java.util.Arrays.fill(slots, EMPTY);
12 }
13
14 int hash(int key) { return key % m; }
15
16 boolean contains(int key) {
17 int start = hash(key);
18 for (int i = 0; i < m; i++) { // at most m probes
19 int slot = slots[(start + i) % m];
20 if (slot == EMPTY) return false; // only EMPTY ends a search early
21 if (slot == key) return true;
22 }
23 return false;
24 }
25
26 String insert(int key) {
27 int start = hash(key);
28 int firstDeleted = -1;
29 for (int i = 0; i < m; i++) {
30 int index = (start + i) % m;
31 int slot = slots[index];
32 if (slot == key) return "ALREADY_PRESENT";
33 if (slot == DELETED && firstDeleted == -1) firstDeleted = index; // remember it, keep probing
34 if (slot == EMPTY) {
35 slots[firstDeleted != -1 ? firstDeleted : index] = key;
36 return "INSERTED";
37 }
38 }
39 if (firstDeleted != -1) {
40 slots[firstDeleted] = key;
41 return "INSERTED";
42 }
43 return "FULL";
44 }
45
46 String remove(int key) {
47 int start = hash(key);
48 for (int i = 0; i < m; i++) {
49 int index = (start + i) % m;
50 int slot = slots[index];
51 if (slot == EMPTY) return "ABSENT";
52 if (slot == key) {
53 slots[index] = DELETED; // not EMPTY: later probes must pass through
54 return "REMOVED";
55 }
56 }
57 return "ABSENT";
58 }
59
60 String show() {
61 StringBuilder sb = new StringBuilder("[");
62 for (int i = 0; i < m; i++) {
63 if (i > 0) sb.append(", ");
64 sb.append(slots[i] == EMPTY ? "EMPTY" : slots[i] == DELETED ? "DELETED" : String.valueOf(slots[i]));
65 }
66 return sb.append("]").toString();
67 }
68 }
69
70 public static void main(String[] args) {
71 LinearProbingSet t = new LinearProbingSet(7);
72 for (int k : new int[]{10, 17, 24}) {
73 System.out.println("insert " + k + ": " + t.insert(k));
74 }
75 System.out.println("table: " + t.show());
76 System.out.println("contains 24: " + t.contains(24));
77 System.out.println("remove 17: " + t.remove(17));
78 System.out.println("table: " + t.show());
79 System.out.println("contains 24: " + t.contains(24));
80 }
81}1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6const int EMPTY = -1, DELETED = -2; // keys are nonnegative, so these cannot clash
7
8struct LinearProbingSet {
9 int m;
10 vector<int> slots;
11
12 explicit LinearProbingSet(int m) : m(m), slots(m, EMPTY) {}
13
14 int hash(int key) const { return key % m; }
15
16 bool contains(int key) const {
17 int start = hash(key);
18 for (int i = 0; i < m; i++) { // at most m probes
19 int slot = slots[(start + i) % m];
20 if (slot == EMPTY) return false; // only EMPTY ends a search early
21 if (slot == key) return true;
22 }
23 return false;
24 }
25
26 string insert(int key) {
27 int start = hash(key);
28 int firstDeleted = -1;
29 for (int i = 0; i < m; i++) {
30 int index = (start + i) % m;
31 int slot = slots[index];
32 if (slot == key) return "ALREADY_PRESENT";
33 if (slot == DELETED && firstDeleted == -1) firstDeleted = index; // remember it, keep probing
34 if (slot == EMPTY) {
35 slots[firstDeleted != -1 ? firstDeleted : index] = key;
36 return "INSERTED";
37 }
38 }
39 if (firstDeleted != -1) {
40 slots[firstDeleted] = key;
41 return "INSERTED";
42 }
43 return "FULL";
44 }
45
46 string remove(int key) {
47 int start = hash(key);
48 for (int i = 0; i < m; i++) {
49 int index = (start + i) % m;
50 int slot = slots[index];
51 if (slot == EMPTY) return "ABSENT";
52 if (slot == key) {
53 slots[index] = DELETED; // not EMPTY: later probes must pass through
54 return "REMOVED";
55 }
56 }
57 return "ABSENT";
58 }
59
60 string show() const {
61 string out = "[";
62 for (int i = 0; i < m; i++) {
63 if (i > 0) out += ", ";
64 out += slots[i] == EMPTY ? "EMPTY" : slots[i] == DELETED ? "DELETED" : to_string(slots[i]);
65 }
66 return out + "]";
67 }
68};
69
70int main() {
71 LinearProbingSet t(7);
72 for (int k : {10, 17, 24}) {
73 cout << "insert " << k << ": " << t.insert(k) << endl;
74 }
75 cout << "table: " << t.show() << endl;
76 cout << "contains 24: " << (t.contains(24) ? "true" : "false") << endl;
77 cout << "remove 17: " << t.remove(17) << endl;
78 cout << "table: " << t.show() << endl;
79 cout << "contains 24: " << (t.contains(24) ? "true" : "false") << endl;
80}1const EMPTY = -1, DELETED = -2; // keys are nonnegative, so these cannot clash
2
3class LinearProbingSet {
4 constructor(m) {
5 this.m = m;
6 this.slots = new Array(m).fill(EMPTY);
7 }
8
9 hash(key) { return key % this.m; }
10
11 contains(key) {
12 const start = this.hash(key);
13 for (let i = 0; i < this.m; i++) { // at most m probes
14 const slot = this.slots[(start + i) % this.m];
15 if (slot === EMPTY) return false; // only EMPTY ends a search early
16 if (slot === key) return true;
17 }
18 return false;
19 }
20
21 insert(key) {
22 const start = this.hash(key);
23 let firstDeleted = -1;
24 for (let i = 0; i < this.m; i++) {
25 const index = (start + i) % this.m;
26 const slot = this.slots[index];
27 if (slot === key) return 'ALREADY_PRESENT';
28 if (slot === DELETED && firstDeleted === -1) firstDeleted = index; // remember it, keep probing
29 if (slot === EMPTY) {
30 this.slots[firstDeleted !== -1 ? firstDeleted : index] = key;
31 return 'INSERTED';
32 }
33 }
34 if (firstDeleted !== -1) {
35 this.slots[firstDeleted] = key;
36 return 'INSERTED';
37 }
38 return 'FULL';
39 }
40
41 remove(key) {
42 const start = this.hash(key);
43 for (let i = 0; i < this.m; i++) {
44 const index = (start + i) % this.m;
45 const slot = this.slots[index];
46 if (slot === EMPTY) return 'ABSENT';
47 if (slot === key) {
48 this.slots[index] = DELETED; // not EMPTY: later probes must pass through
49 return 'REMOVED';
50 }
51 }
52 return 'ABSENT';
53 }
54
55 show() {
56 return `[${this.slots.map((s) => (s === EMPTY ? 'EMPTY' : s === DELETED ? 'DELETED' : s)).join(', ')}]`;
57 }
58}
59
60const t = new LinearProbingSet(7);
61for (const k of [10, 17, 24]) console.log(`insert ${k}: ${t.insert(k)}`);
62console.log(`table: ${t.show()}`);
63console.log(`contains 24: ${t.contains(24)}`);
64console.log(`remove 17: ${t.remove(17)}`);
65console.log(`table: ${t.show()}`);
66console.log(`contains 24: ${t.contains(24)}`);In open addressing the three probe rules are linear probing (step of 1), quadratic probing (the step grows with i squared) and double hashing (the step comes from a second hash function). Chaining is the main alternative.
It jumps i squared slots instead of 1, which avoids long runs of adjacent occupied slots. It can still cause milder secondary clustering, and it may miss slots unless m and its constants are chosen well.
A different idea. In deep learning, a linear probe is a linear classifier trained on frozen model features to test what they encode. This page covers the hash table technique.
A search stops at the first EMPTY slot. After deleting 17 from [EMPTY, EMPTY, EMPTY, 10, 17, 24, EMPTY], an EMPTY at slot 4 makes contains(24) return false although 24 sits at slot 5.
Probing stops after m probes. If no EMPTY or DELETED slot appeared, insert returns FULL. Without that limit the loop cycles forever. Grow the table before it fills.