GAZAR

Principal Engineer | Mentor

Open Addressing Algorithm In Hash Tables

Open Addressing Algorithm In Hash Tables

In open addressing, when a collision occurs (i.e., when two keys hash to the same index), the algorithm probes the hash table for an alternative location to store the key-value pair. There are different probing techniques, such as linear probing, quadratic probing, and double hashing, each with its own way of determining the next probe location.

class HashTable {
    constructor(size = 10) {
        this.size = size;
        this.table = Array.from({ length: size });
    }

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

    insert(key, value) {
        let index = this._hash(key);
        while (this.table[index] !== undefined) {
            index = (index + 1) % this.size; // Linear probing
        }
        this.table[index] = { key, value };
    }

    get(key) {
        let index = this._hash(key);
        while (this.table[index] !== undefined) {
            if (this.table[index].key === key) {
                return this.table[index].value;
            }
            index = (index + 1) % this.size; // Linear probing
        }
        return undefined;
    }

    remove(key) {
        let index = this._hash(key);
        while (this.table[index] !== undefined) {
            if (this.table[index].key === key) {
                this.table[index] = undefined;
                return;
            }
            index = (index + 1) % this.size; // Linear probing
        }
    }
}

// Example usage:
const hashTable = new HashTable();
hashTable.insert('apple', 'red');
hashTable.insert('banana', 'yellow');
hashTable.insert('orange', 'orange');

console.log('Value for key "banana":', hashTable.get('banana')); // Output: "yellow"

hashTable.remove('banana');
console.log('Value for key "banana":', hashTable.get('banana')); // Output: undefined

Open addressing is a collision resolution technique used in hash tables to handle collisions by probing for alternative locations. By implementing open addressing in JavaScript hash tables, developers can create efficient data structures for storing and retrieving key-value pairs with minimal overhead.

Comments