Open Addressing Algorithm In Hash Tables

Hash tables are fast — O(1) average lookups. But what happens when two keys hash to the same slot?

One approach: chaining — store a linked list at each slot. The other: open addressing — find another empty slot within the table itself. No external data structures. Everything lives inside the array.

How open addressing works

When a collision happens, you probe for the next available slot. Three common strategies:

Linear probing: Check the next slot. Then the next. Simple but causes clustering — collided keys clump together.

Quadratic probing: Check slot + 1², + 2², + 3²... Reduces clustering but can miss slots.

Double hashing: Use a second hash function to determine the probe step. Best distribution, most complex.

The code (linear probing)

class HashTable {
    constructor(size = 10) {
        this.size = size;
        this.keys = new Array(size).fill(null);
        this.values = new Array(size).fill(null);
        this.count = 0;
    }

    hash(key) {
        let total = 0;
        for (let i = 0; i < key.length; i++) {
            total = (total + key.charCodeAt(i)) % this.size;
        }
        return total;
    }

    set(key, value) {
        if (this.count >= this.size) return false;
        let index = this.hash(key);

        while (this.keys[index] !== null && this.keys[index] !== key) {
            index = (index + 1) % this.size;
        }

        this.keys[index] = key;
        this.values[index] = value;
        this.count++;
        return true;
    }

    get(key) {
        let index = this.hash(key);
        let attempts = 0;

        while (this.keys[index] !== null && attempts < this.size) {
            if (this.keys[index] === key) return this.values[index];
            index = (index + 1) % this.size;
            attempts++;
        }

        return undefined;
    }
}

Complexity

• Time: O(1) average for insert and lookup. O(n) worst case when the table is nearly full.
• Space: O(n) — the table itself.

Trade-offs

Open addressing has better cache performance than chaining — everything is in a contiguous array. But it degrades badly as the load factor (items/slots) approaches 1. Most implementations resize the table when the load factor hits 0.7 or so.

Chaining handles high load factors more gracefully and makes deletion simpler. With open addressing, deleting an element is tricky — you can't just null out a slot without breaking probe chains. You typically use a "deleted" sentinel marker instead.