Hashing· 20 min

Separate Chaining

Linked list per bucket — simple collision handling

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
chaining-hashtable.java
1class HashTable {
2    List<Entry>[] buckets;
3    @SuppressWarnings("unchecked")
4    HashTable(int cap) { buckets = new List[cap];
5        for (int i=0;i<cap;i++) buckets[i] = new ArrayList<>(); }
6    int hash(String key) {
7        int h = 0;
8        for (char c : key.toCharArray()) h = (h * 31 + c) % buckets.length;
9        return h;
10    }
11    void set(String key, int val) {
12        int i = hash(key);
13        for (Entry e : buckets[i]) if (e.key.equals(key)) { e.value = val; return; }
14        buckets[i].add(new Entry(key, val));
15    }
16    Integer get(String key) {
17        int i = hash(key);
18        for (Entry e : buckets[i]) if (e.key.equals(key)) return e.value;
19        return null;
20    }
21}
● Java

Separate Chaining

Each bucket holds a linked list of entries. On collision, the new entry is appended to the list. Simple, handles high load factors gracefully, but uses extra memory for list pointers.

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