Hashing turns a key into an array index with a hash function, so that search, insert and delete all run in O(1) on average. It is the engine behind every dictionary, set, cache and database index you will ever use.

Universe of keys → Hash function h(key) → Index 0 … m-1 → Hash table slot

Operation	Average	Worst case	Why
`search(key)`	O(1)	O(n)	Compute `h(key)`, look in that slot. Worst case: every key collided into the same slot.
`insert(key)`	O(1)	O(n)	Same slot computation; the worst case is a full probe sequence or a long chain.
`delete(key)`	O(1)	O(n)	Find the key as in search, then unlink / mark it.

What hashing is good for — and what it is not

Direct address table

Suppose there are at most 1000 keys and every key is an integer between 0 and 999. The simplest O(1) structure is a boolean (or value) array of size 1000 where the key is the index: table[key] = true inserts, table[key] searches, table[key] = false deletes.

A direct address table for keys 0–9

key:    0     1     2     3     4     5     6     7     8     9
      ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
      │  T  │  F  │  F  │  T  │  F  │  F  │  F  │  T  │  F  │  F  │
      └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
after insert(0), insert(3), insert(7) — the key is the index, no hash function at all

Python

table = [False] * 10          # keys 0..9, the key itself is the index

def insert(k): table[k] = True
def delete(k): table[k] = False
def search(k): return table[k]

for k in (0, 3, 7):
    insert(k)
print("search 3:", "true" if search(3) else "false")
print("search 5:", "true" if search(5) else "false")
delete(3)
print("after delete 3 → search 3:", "true" if search(3) else "false")

C++

#include <iostream>
using namespace std;

bool table[10] = {false};     // keys 0..9, the key itself is the index

void insertKey(int k) { table[k] = true; }
void deleteKey(int k) { table[k] = false; }
bool search(int k) { return table[k]; }

int main() {
    for (int k : {0, 3, 7}) insertKey(k);
    cout << "search 3: " << (search(3) ? "true" : "false") << "\n";
    cout << "search 5: " << (search(5) ? "true" : "false") << "\n";
    deleteKey(3);
    cout << "after delete 3 → search 3: " << (search(3) ? "true" : "false") << "\n";
}

Java

public class Main {
    static boolean[] table = new boolean[10];   // keys 0..9, the key itself is the index

    static void insert(int k) { table[k] = true; }
    static void delete(int k) { table[k] = false; }
    static boolean search(int k) { return table[k]; }

    public static void main(String[] args) {
        for (int k : new int[]{0, 3, 7}) insert(k);
        System.out.println("search 3: " + search(3));
        System.out.println("search 5: " + search(5));
        delete(3);
        System.out.println("after delete 3 → search 3: " + search(3));
    }
}

JavaScript

const table = new Array(10).fill(false);   // keys 0..9, the key itself is the index

const insert = (k) => { table[k] = true; };
const del = (k) => { table[k] = false; };
const search = (k) => table[k];

for (const k of [0, 3, 7]) insert(k);
console.log("search 3:", search(3));
console.log("search 5:", search(5));
del(3);
console.log("after delete 3 → search 3:", search(3));

Output

search 3: true
search 5: false
after delete 3 → search 3: false

Time O(1) per operation · Space O(size of key universe)

Hash functions

A hash function h converts a key into a slot index. A good one has four properties:

Deterministic — the same key must always map to the same slot, or we could never find it again.
In range — produces values in 0 … m-1 where m is the table size.
Fast — O(1) for integers and O(len) for a string of length len.
Uniform — spreads keys evenly across the slots, so that chains and probe sequences stay short.

Key type	Typical hash function	Note
Integer	`h(key) = key % m`	Choose `m` prime and not close to a power of 2, so patterns in the keys (even numbers, multiples of 10) do not pile up in a few slots.
String	Weighted (polynomial) sum: `h = (h · 31 + c) % m` over the characters	Plain sum of character codes is bad: `"abc"`, `"bca"`, `"cab"` would all collide. The weight makes position matter.
Any	Universal hashing: pick `h` at random from a family of functions at start-up	No fixed input can be adversarially chosen to collide, because the attacker does not know which function was picked.

Python

def string_hash(s, m):
    h = 0
    for ch in s:
        h = (h * 31 + ord(ch)) % m    # weighted sum: position matters
    return h

M = 97                                # a prime table size
for s in ["abc", "cab", "bca", "hash"]:
    print(s, "→", string_hash(s, M))

C++

#include <iostream>
#include <string>
using namespace std;

int stringHash(const string& s, int m) {
    long long h = 0;
    for (char ch : s)
        h = (h * 31 + ch) % m;        // weighted sum: position matters
    return (int)h;
}

int main() {
    const int M = 97;                 // a prime table size
    for (string s : {"abc", "cab", "bca", "hash"})
        cout << s << " → " << stringHash(s, M) << "\n";
}

Java

public class Main {
    static int stringHash(String s, int m) {
        long h = 0;
        for (char ch : s.toCharArray())
            h = (h * 31 + ch) % m;    // weighted sum: position matters
        return (int) h;
    }

    public static void main(String[] args) {
        final int M = 97;             // a prime table size
        for (String s : new String[]{"abc", "cab", "bca", "hash"})
            System.out.println(s + " → " + stringHash(s, M));
    }
}

JavaScript

function stringHash(s, m) {
    let h = 0;
    for (const ch of s)
        h = (h * 31 + ch.charCodeAt(0)) % m;   // weighted sum: position matters
    return h;
}

const M = 97;                                  // a prime table size
for (const s of ["abc", "cab", "bca", "hash"])
    console.log(s, "→", stringHash(s, M));

Output

abc → 33
cab → 80
bca → 53
hash → 67

Time O(len) per string · Space O(1)

Collisions and how to handle them

Chaining

The table is an array of m list heads. insert appends to the list at h(key), search and delete walk that one list only. With h(key) = key % 7 and the keys 50, 21, 58, 17, 15, 49, 56, 22, 23, 25:

Chaining with m = 7: every slot owns the chain of keys that hashed to it

slot
 0  │ 21 │──▶│ 49 │──▶│ 56 │          21 % 7 = 0, 49 % 7 = 0, 56 % 7 = 0
 1  │ 50 │──▶│ 15 │──▶│ 22 │          50 % 7 = 1, 15 % 7 = 1, 22 % 7 = 1
 2  │ 58 │──▶│ 23 │                   58 % 7 = 2, 23 % 7 = 2
 3  │ 17 │
 4  │ 25 │
 5  │    │
 6  │    │
hash table = array of linked-list heads

Performance. Let m be the number of slots and n the number of keys. The load factor α = n / m is the expected chain length under uniform hashing, so:

expected search / delete time = O(1 + α) — O(1) to hash, O(α) to walk the chain

Keeping α bounded by a constant (Java's HashMap rehashes at α = 0.75) makes every operation O(1) on average. Chains can be stored in any of these:

Chain structure	Pros	Cons
Linked list	O(1) insert at head, no resizing	Poor cache locality, one pointer per key
Dynamic array (`vector`, `ArrayList`, Python `list`)	Cache friendly, simple	Delete from the middle shifts elements (chains are short, so it hardly matters)
Self-balancing BST (AVL, Red-Black)	Worst case per chain drops to O(log n) — Java 8+ `HashMap` switches a bucket to a tree when it grows past 8 entries	Heavier nodes, more code

Python

class ChainedHash:
    def __init__(self, buckets):
        self.buckets = buckets
        self.table = [[] for _ in range(buckets)]   # one list per slot

    def _h(self, key):
        return key % self.buckets

    def insert(self, key):
        self.table[self._h(key)].append(key)        # O(1): append to the chain

    def delete(self, key):
        chain = self.table[self._h(key)]
        if key in chain:
            chain.remove(key)                       # O(chain length)

    def search(self, key):
        return key in self.table[self._h(key)]      # walk one chain only

    def show(self):
        for i, chain in enumerate(self.table):
            print(f"{i}:", *chain)

h = ChainedHash(7)
for k in (70, 71, 9, 56, 72):
    h.insert(k)
h.show()
h.delete(56)
print("after delete 56")
h.show()
print("search 9:", "true" if h.search(9) else "false")
print("search 93:", "true" if h.search(93) else "false")

C++

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;

class ChainedHash {
    int buckets;
    vector<list<int>> table;                        // one linked list per slot
    int h(int key) const { return key % buckets; }
public:
    ChainedHash(int b) : buckets(b), table(b) {}
    void insert(int key) { table[h(key)].push_back(key); }       // O(1)
    void remove(int key) { table[h(key)].remove(key); }          // O(chain length)
    bool search(int key) const {
        const list<int>& chain = table[h(key)];
        return find(chain.begin(), chain.end(), key) != chain.end();
    }
    void show() const {
        for (int i = 0; i < buckets; i++) {
            cout << i << ":";
            for (int k : table[i]) cout << " " << k;
            cout << "\n";
        }
    }
};

int main() {
    ChainedHash h(7);
    for (int k : {70, 71, 9, 56, 72}) h.insert(k);
    h.show();
    h.remove(56);
    cout << "after delete 56\n";
    h.show();
    cout << "search 9: " << (h.search(9) ? "true" : "false") << "\n";
    cout << "search 93: " << (h.search(93) ? "true" : "false") << "\n";
}

Java

import java.util.LinkedList;

public class Main {
    static class ChainedHash {
        int buckets;
        LinkedList<Integer>[] table;                 // one linked list per slot

        @SuppressWarnings("unchecked")
        ChainedHash(int b) {
            buckets = b;
            table = new LinkedList[b];
            for (int i = 0; i < b; i++) table[i] = new LinkedList<>();
        }
        int h(int key) { return key % buckets; }
        void insert(int key) { table[h(key)].add(key); }                 // O(1)
        void delete(int key) { table[h(key)].remove(Integer.valueOf(key)); }   // O(chain length)
        boolean search(int key) { return table[h(key)].contains(key); }
        void show() {
            for (int i = 0; i < buckets; i++) {
                StringBuilder sb = new StringBuilder(i + ":");
                for (int k : table[i]) sb.append(" ").append(k);
                System.out.println(sb);
            }
        }
    }

    public static void main(String[] args) {
        ChainedHash h = new ChainedHash(7);
        for (int k : new int[]{70, 71, 9, 56, 72}) h.insert(k);
        h.show();
        h.delete(56);
        System.out.println("after delete 56");
        h.show();
        System.out.println("search 9: " + h.search(9));
        System.out.println("search 93: " + h.search(93));
    }
}

JavaScript

class ChainedHash {
    constructor(buckets) {
        this.buckets = buckets;
        this.table = Array.from({ length: buckets }, () => []);   // one list per slot
    }
    h(key) { return key % this.buckets; }
    insert(key) { this.table[this.h(key)].push(key); }            // O(1)
    delete(key) {
        const chain = this.table[this.h(key)];
        const at = chain.indexOf(key);
        if (at !== -1) chain.splice(at, 1);                       // O(chain length)
    }
    search(key) { return this.table[this.h(key)].includes(key); }
    show() {
        this.table.forEach((chain, i) => console.log(`${i}:` + chain.map(k => " " + k).join("")));
    }
}

const h = new ChainedHash(7);
for (const k of [70, 71, 9, 56, 72]) h.insert(k);
h.show();
h.delete(56);
console.log("after delete 56");
h.show();
console.log("search 9:", h.search(9));
console.log("search 93:", h.search(93));

Output

0: 70 56
1: 71
2: 9 72
3:
4:
5:
6:
after delete 56
0: 70
1: 71
2: 9 72
3:
4:
5:
6:
search 9: true
search 93: false

Time O(1 + α) average, O(n) worst · Space O(n + m)

Load factor and rehashing

The load factor grows with every insert and drops when the table is resized

empty table, 10 slots         [_, _, _, _, _, _, _, _, _, _]                        α = 0.0
after 5 insertions            [x, x, x, x, x, _, _, _, _, _]                        α = 0.5
after 10 insertions           [x, x, x, x, x, x, x, x, x, x]                        α = 1.0  (full)
rehash to 20 slots, insert    [x, x, x, x, x, x, x, x, x, x, x, _, _, _, _, _, _, _, _, _]   α = 0.55

Rehashing: when α crosses a threshold (typically 0.75 for chaining, 0.5 for open addressing), allocate a new table about twice as large and re-insert every key with the new h — the slot of a key depends on m, so the old positions are useless. One rehash costs O(n), but it happens only after O(n) cheap inserts, so insertion stays amortised O(1).

Scheme	Expected successful search	Expected unsuccessful search / insert	Must keep
Chaining	O(1 + α)	O(1 + α)	`α` bounded by a constant (any value works, even `α > 1`)
Open addressing	about `1/α · ln(1/(1-α))`	about `1 / (1 - α)`	`α < 1`, in practice `α ≤ 0.5 … 0.7`

Open addressing — linear probing

In open addressing there are no chains: every key lives in the array itself, so the number of slots must be >= the number of keys. On a collision we probe — try other slots in a fixed sequence until an empty one appears. Because all data is in one contiguous array, this is very cache friendly.

linear probing: hash(key, i) = (h(key) + i) % m for i = 0, 1, 2, …

With m = 7, h(key) = key % 7 and the keys 50, 51, 49, 16, 56, 15, 19:

Linear probing: each collision slides to the next free slot (wrapping around at the end)

key   h(key)   placed at                    0 │ 49 │
 50     1      1                            1 │ 50 │
 51     2      2                            2 │ 51 │
 49     0      0                            3 │ 16 │  ← 2 taken, moved to 3
 16     2      3   (2 taken)                4 │ 56 │  ← 0,1,2,3 taken, moved to 4
 56     0      4   (0,1,2,3 taken)          5 │ 15 │  ← 1,2,3,4 taken, moved to 5
 15     1      5   (1,2,3,4 taken)          6 │ 19 │  ← 5 taken, moved to 6
 19     5      6   (5 taken)

Quadratic probing and double hashing

Both break clusters by making the probe sequence depend on something other than +1:

Scheme	Probe sequence	Clustering	Guarantee
Linear probing	`(h(key) + i) % m`	Primary clustering	Always finds a free slot if one exists
Quadratic probing	`(h(key) + i²) % m`	Secondary clustering (keys with the same `h` still share a sequence)	Guaranteed to find a free slot only if `m` is prime and `α < 0.5`
Double hashing	`(h1(key) + i · h2(key)) % m`	None — different keys with the same `h1` almost always get different step sizes	Finds a free slot if one exists when `h2(key)` is relatively prime to `m` (e.g. `m` prime and `h2(key) = 1 + key % (m-1)`)

Double hashing distributes keys more uniformly than linear and quadratic probing and is the closest practical approximation to the uniform hashing assumption behind the 1 / (1 - α) analysis. The insert routine from the notes:

Reject a full table
If n == m return an error — open addressing cannot store more keys than slots.
Compute the start and the step
probe = h1(key), offset = h2(key).
Walk the sequence
While table[probe] is occupied: probe = (probe + offset) % m.
Store
table[probe] = key.

Python

M = 7
table = [None] * M

def h1(key): return key % M
def h2(key): return 1 + key % (M - 1)        # 1..6, all relatively prime to 7

def double_hashing_insert(key):
    probe, offset = h1(key), h2(key)
    while table[probe] is not None:
        probe = (probe + offset) % M          # jump by the key's own step size
    table[probe] = key
    print(f"insert {key}: h1={h1(key)} → slot {probe}")

for k in (50, 51, 49, 16, 56, 15, 19):
    double_hashing_insert(k)
print("table:", *table)

C++

#include <iostream>
using namespace std;

const int M = 7;
int table_[M];
bool used[M] = {false};

int h1(int key) { return key % M; }
int h2(int key) { return 1 + key % (M - 1); }   // 1..6, all relatively prime to 7

void doubleHashingInsert(int key) {
    int probe = h1(key), offset = h2(key);
    while (used[probe])
        probe = (probe + offset) % M;            // jump by the key's own step size
    table_[probe] = key; used[probe] = true;
    cout << "insert " << key << ": h1=" << h1(key) << " → slot " << probe << "\n";
}

int main() {
    for (int k : {50, 51, 49, 16, 56, 15, 19}) doubleHashingInsert(k);
    cout << "table:";
    for (int i = 0; i < M; i++) cout << " " << table_[i];
    cout << "\n";
}

Java

public class Main {
    static final int M = 7;
    static Integer[] table = new Integer[M];

    static int h1(int key) { return key % M; }
    static int h2(int key) { return 1 + key % (M - 1); }   // 1..6, all relatively prime to 7

    static void doubleHashingInsert(int key) {
        int probe = h1(key), offset = h2(key);
        while (table[probe] != null)
            probe = (probe + offset) % M;                  // jump by the key's own step size
        table[probe] = key;
        System.out.println("insert " + key + ": h1=" + h1(key) + " → slot " + probe);
    }

    public static void main(String[] args) {
        for (int k : new int[]{50, 51, 49, 16, 56, 15, 19}) doubleHashingInsert(k);
        StringBuilder sb = new StringBuilder("table:");
        for (Integer v : table) sb.append(" ").append(v);
        System.out.println(sb);
    }
}

JavaScript

const M = 7;
const table = new Array(M).fill(null);

const h1 = (key) => key % M;
const h2 = (key) => 1 + key % (M - 1);          // 1..6, all relatively prime to 7

function doubleHashingInsert(key) {
    let probe = h1(key);
    const offset = h2(key);
    while (table[probe] !== null)
        probe = (probe + offset) % M;            // jump by the key's own step size
    table[probe] = key;
    console.log(`insert ${key}: h1=${h1(key)} → slot ${probe}`);
}

for (const k of [50, 51, 49, 16, 56, 15, 19]) doubleHashingInsert(k);
console.log("table:", table.join(" "));

Output

insert 50: h1=1 → slot 1
insert 51: h1=2 → slot 2
insert 49: h1=0 → slot 0
insert 16: h1=2 → slot 5
insert 56: h1=0 → slot 3
insert 15: h1=1 → slot 6
insert 19: h1=5 → slot 4
table: 49 50 51 56 19 16 15

Time O(1 / (1 - α)) expected per insert · Space O(m)

Implementation of open addressing

A complete linear-probing table with the DELETED marker. Empty slots are -1, deleted slots -2; keys are assumed non-negative. insert refuses duplicates and reuses deleted slots; search skips deleted slots and stops at an empty one.

Python

EMPTY, DELETED = -1, -2

class OpenHash:
    def __init__(self, capacity):
        self.cap = capacity
        self.table = [EMPTY] * capacity
        self.size = 0

    def _h(self, key):
        return key % self.cap

    def search(self, key):
        h = i = self._h(key)
        while self.table[i] != EMPTY:            # a DELETED slot does NOT stop the search
            if self.table[i] == key:
                return True
            i = (i + 1) % self.cap
            if i == h:                           # wrapped all the way round
                return False
        return False

    def insert(self, key):
        if self.size == self.cap or self.search(key):
            return False
        h = i = self._h(key)
        while self.table[i] not in (EMPTY, DELETED):   # a DELETED slot can be reused
            i = (i + 1) % self.cap
            if i == h:
                return False
        self.table[i] = key
        self.size += 1
        return True

    def delete(self, key):
        h = i = self._h(key)
        while self.table[i] != EMPTY:
            if self.table[i] == key:
                self.table[i] = DELETED          # mark, never empty the slot
                self.size -= 1
                return True
            i = (i + 1) % self.cap
            if i == h:
                return False
        return False

    def show(self):
        print(*["_" if v == EMPTY else "x" if v == DELETED else v for v in self.table])

def b(x): return "true" if x else "false"

t = OpenHash(7)
for k in (70, 71, 9, 56, 72):
    t.insert(k)
t.show()
print("search 9:", b(t.search(9)))
print("delete 9:", b(t.delete(9)))
t.show()
print("search 9:", b(t.search(9)))
print("search 56:", b(t.search(56)))
print("insert 56 again:", b(t.insert(56)))

C++

#include <iostream>
#include <vector>
using namespace std;

const int EMPTY = -1, DELETED = -2;

class OpenHash {
    int cap, size = 0;
    vector<int> table;
    int h(int key) const { return key % cap; }
public:
    OpenHash(int c) : cap(c), table(c, EMPTY) {}

    bool search(int key) const {
        int start = h(key), i = start;
        while (table[i] != EMPTY) {              // a DELETED slot does NOT stop the search
            if (table[i] == key) return true;
            i = (i + 1) % cap;
            if (i == start) return false;        // wrapped all the way round
        }
        return false;
    }
    bool insert(int key) {
        if (size == cap || search(key)) return false;
        int start = h(key), i = start;
        while (table[i] != EMPTY && table[i] != DELETED) {   // a DELETED slot can be reused
            i = (i + 1) % cap;
            if (i == start) return false;
        }
        table[i] = key; size++;
        return true;
    }
    bool remove(int key) {
        int start = h(key), i = start;
        while (table[i] != EMPTY) {
            if (table[i] == key) { table[i] = DELETED; size--; return true; }   // mark, never empty
            i = (i + 1) % cap;
            if (i == start) return false;
        }
        return false;
    }
    void show() const {
        for (int i = 0; i < cap; i++) {
            if (i) cout << " ";
            if (table[i] == EMPTY) cout << "_"; else if (table[i] == DELETED) cout << "x"; else cout << table[i];
        }
        cout << "\n";
    }
};

const char* b(bool x) { return x ? "true" : "false"; }

int main() {
    OpenHash t(7);
    for (int k : {70, 71, 9, 56, 72}) t.insert(k);
    t.show();
    cout << "search 9: " << b(t.search(9)) << "\n";
    cout << "delete 9: " << b(t.remove(9)) << "\n";
    t.show();
    cout << "search 9: " << b(t.search(9)) << "\n";
    cout << "search 56: " << b(t.search(56)) << "\n";
    cout << "insert 56 again: " << b(t.insert(56)) << "\n";
}

Java

public class Main {
    static final int EMPTY = -1, DELETED = -2;

    static class OpenHash {
        int cap, size = 0;
        int[] table;
        OpenHash(int c) { cap = c; table = new int[c]; java.util.Arrays.fill(table, EMPTY); }
        int h(int key) { return key % cap; }

        boolean search(int key) {
            int start = h(key), i = start;
            while (table[i] != EMPTY) {              // a DELETED slot does NOT stop the search
                if (table[i] == key) return true;
                i = (i + 1) % cap;
                if (i == start) return false;        // wrapped all the way round
            }
            return false;
        }
        boolean insert(int key) {
            if (size == cap || search(key)) return false;
            int start = h(key), i = start;
            while (table[i] != EMPTY && table[i] != DELETED) {   // a DELETED slot can be reused
                i = (i + 1) % cap;
                if (i == start) return false;
            }
            table[i] = key; size++;
            return true;
        }
        boolean delete(int key) {
            int start = h(key), i = start;
            while (table[i] != EMPTY) {
                if (table[i] == key) { table[i] = DELETED; size--; return true; }   // mark, never empty
                i = (i + 1) % cap;
                if (i == start) return false;
            }
            return false;
        }
        void show() {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < cap; i++) {
                if (i > 0) sb.append(" ");
                sb.append(table[i] == EMPTY ? "_" : table[i] == DELETED ? "x" : String.valueOf(table[i]));
            }
            System.out.println(sb);
        }
    }

    public static void main(String[] args) {
        OpenHash t = new OpenHash(7);
        for (int k : new int[]{70, 71, 9, 56, 72}) t.insert(k);
        t.show();
        System.out.println("search 9: " + t.search(9));
        System.out.println("delete 9: " + t.delete(9));
        t.show();
        System.out.println("search 9: " + t.search(9));
        System.out.println("search 56: " + t.search(56));
        System.out.println("insert 56 again: " + t.insert(56));
    }
}

JavaScript

const EMPTY = -1, DELETED = -2;

class OpenHash {
    constructor(capacity) {
        this.cap = capacity;
        this.table = new Array(capacity).fill(EMPTY);
        this.size = 0;
    }
    h(key) { return key % this.cap; }

    search(key) {
        const start = this.h(key);
        let i = start;
        while (this.table[i] !== EMPTY) {            // a DELETED slot does NOT stop the search
            if (this.table[i] === key) return true;
            i = (i + 1) % this.cap;
            if (i === start) return false;           // wrapped all the way round
        }
        return false;
    }
    insert(key) {
        if (this.size === this.cap || this.search(key)) return false;
        const start = this.h(key);
        let i = start;
        while (this.table[i] !== EMPTY && this.table[i] !== DELETED) {   // a DELETED slot can be reused
            i = (i + 1) % this.cap;
            if (i === start) return false;
        }
        this.table[i] = key; this.size++;
        return true;
    }
    delete(key) {
        const start = this.h(key);
        let i = start;
        while (this.table[i] !== EMPTY) {
            if (this.table[i] === key) { this.table[i] = DELETED; this.size--; return true; }   // mark, never empty
            i = (i + 1) % this.cap;
            if (i === start) return false;
        }
        return false;
    }
    show() {
        console.log(this.table.map(v => v === EMPTY ? "_" : v === DELETED ? "x" : v).join(" "));
    }
}

const t = new OpenHash(7);
for (const k of [70, 71, 9, 56, 72]) t.insert(k);
t.show();
console.log("search 9:", t.search(9));
console.log("delete 9:", t.delete(9));
t.show();
console.log("search 9:", t.search(9));
console.log("search 56:", t.search(56));
console.log("insert 56 again:", t.insert(56));

Output

70 71 9 56 72 _ _
search 9: true
delete 9: true
70 71 x 56 72 _ _
search 9: false
search 56: true
insert 56 again: false

Time O(1) average, O(n) worst · Space O(m)

Chaining vs open addressing

	Chaining	Open addressing
Table full?	Never — chains simply grow	Yes; resizing becomes mandatory
Sensitivity to hash function	Low — a poor function only lengthens chains	High — clustering needs extra care
Cache performance	Poor: chain nodes are scattered in memory	Good: everything is in one array
Extra space	One link pointer per key	Empty slots must be kept (`α` well below 1) to achieve the same performance
Deletion	Unlink from the chain	Needs the DELETED marker
Unsuccessful search cost	`1 + α`	`1 / (1 - α)`

Problem: frequencies of array elements

Naive approach — for every element, skip it if it appeared earlier (so each value is printed once), otherwise count its later occurrences. Two nested passes make it O(n²) with O(1) extra space.

Python

def count_freq(arr):
    n = len(arr)
    for i in range(n):
        if any(arr[j] == arr[i] for j in range(i)):   # already counted
            continue
        count = 1
        for j in range(i + 1, n):
            if arr[j] == arr[i]:
                count += 1
        print(arr[i], count)

count_freq([10, 12, 10, 15, 10, 20, 12, 12])

Output

Time O(n²) · Space O(1)

Python

def count_freq(arr):
    freq = {}
    for x in arr:
        freq[x] = freq.get(x, 0) + 1      # O(1) average per element
    for x in sorted(freq):                # sort only for a deterministic printout
        print(x, freq[x])

count_freq([10, 12, 10, 15, 10, 20, 12, 12])

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

void countFreq(const vector<int>& arr) {
    unordered_map<int, int> freq;
    for (int x : arr) freq[x]++;          // O(1) average per element
    vector<int> keys;
    for (auto& kv : freq) keys.push_back(kv.first);
    sort(keys.begin(), keys.end());       // sort only for a deterministic printout
    for (int k : keys) cout << k << " " << freq[k] << "\n";
}

int main() {
    countFreq({10, 12, 10, 15, 10, 20, 12, 12});
}

Java

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class Main {
    static void countFreq(int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : arr) freq.merge(x, 1, Integer::sum);   // O(1) average per element
        for (int k : new TreeSet<>(freq.keySet()))          // sort only for a deterministic printout
            System.out.println(k + " " + freq.get(k));
    }

    public static void main(String[] args) {
        countFreq(new int[]{10, 12, 10, 15, 10, 20, 12, 12});
    }
}

JavaScript

function countFreq(arr) {
    const freq = new Map();
    for (const x of arr) freq.set(x, (freq.get(x) ?? 0) + 1);   // O(1) average per element
    const keys = [...freq.keys()].sort((a, b) => a - b);        // sort only for a deterministic printout
    for (const k of keys) console.log(k, freq.get(k));
}

countFreq([10, 12, 10, 15, 10, 20, 12, 12]);

Output

Time O(n) average (O(n log n) with the final sort) · Space O(n)

Interview Q&A

Why is a hash table O(1) only on average?

What is the load factor and what happens when it gets too high?

Why can't you just empty a slot when deleting from an open-addressing table?

Chaining or open addressing — which would you choose?

Why should the table size be prime for modulo hashing?