Hashing· 20 min

Linear Probing

Open addressing — probe next slot on collision

Setup

Capacity: 7 · Size: 0 · Load: 0.00
Step 1 / 1

Current step

1 / 1

Enter a key and value above, then click Set to visualize the hash + insert.

Step log

Bucket array (capacity 7)
0
∅ empty
1
∅ empty
2
∅ empty
3
∅ empty
4
∅ empty
5
∅ empty
6
∅ empty
hash(key) = (h * 31 + charCode) mod 7
linear-probing-hashtable.java
1class HashTable {
2    Entry[] slots; int cap;
3    HashTable(int cap) { this.cap = cap; slots = new Entry[cap]; }
4    int hash(String key) {
5        int h = 0;
6        for (char c : key.toCharArray()) h = (h * 31 + c) % cap;
7        return h;
8    }
9    void set(String key, int val) {
10        int i = hash(key);
11        while (slots[i] != null && !slots[i].key.equals(key))
12            i = (i + 1) % cap;
13        slots[i] = new Entry(key, val);
14    }
15    Integer get(String key) {
16        int i = hash(key);
17        while (slots[i] != null && !slots[i].key.equals(key))
18            i = (i + 1) % cap;
19        return slots[i] == null ? null : slots[i].value;
20    }
21}
● Java

Linear Probing

All entries live in the bucket array itself. On collision, probe the next slot (i+1, i+2, ...) until an empty one is found. Cache-friendly (contiguous memory), but degrades badly above 70% load and requires careful deletion.

Avg lookup
O(1)
Worst lookup
O(n)
Avg insert
O(1)
Space
O(n)
17 / 46