Open Addressing

In Open Addressing, all elements are stored in the hash table itself. Each table entry contains either a record or NIL. When searching for an element, we one by one examine the table slots until the desired element is found or it is clear that the element is not in the table.

Operations

• Insert(k): Keep probing until an empty slot is found. Once an empty slot is found, insert k.
• Search(k): Keep probing until the slot's key matches k or an empty slot is reached.
• Delete(k): The delete operation is interesting. If we simply delete a key and make the slot NIL, then the search may fail for elements that were inserted after it and collided. So, slots of deleted keys are marked specially as "deleted". The insert operation can insert an item in a "deleted" slot, but the search operation doesn't stop at a "deleted" slot.

Types of Open Addressing

Open Addressing is done in the following ways:

1. Linear Probing: We linearly probe for the next slot. hash(k, i) = (h1(k) + i) % m
2. Quadratic Probing: We probe with quadratic intervals. hash(k, i) = (h1(k) + c1*i + c2*i²) % m
3. Double Hashing: We use another hash function to calculate the probing interval. hash(k, i) = (h1(k) + i * h2(k)) % m

Linear Probing Example

Consider inserting the keys [50, 700, 76, 85, 92, 73, 101] into a Hash Table of size 7, using the hash function h(k) = k % 7.

1. Insert 50: 50 % 7 = 1. Insert at index 1.
2. Insert 700: 700 % 7 = 0. Insert at index 0.
3. Insert 76: 76 % 7 = 6. Insert at index 6.
4. Insert 85: 85 % 7 = 1. Collision at 1! Probe next: (1 + 1) % 7 = 2. Insert at index 2.
5. Insert 92: 92 % 7 = 1. Collision at 1 and 2! Probe next: (2 + 1) % 7 = 3. Insert at index 3.
6. Insert 73: 73 % 7 = 3. Collision at 3! Probe next: (3 + 1) % 7 = 4. Insert at index 4.
7. Insert 101: 101 % 7 = 3. Collision at 3 and 4! Probe next: (4 + 1) % 7 = 5. Insert at index 5.

Implementation of Open Addressing (Linear Probing)

The task is to design a general Hash Table data structure with Collision cases handled using Linear Probing, supporting Insert(), Find(), and Delete() functions.

Approach

The problem can be solved by using a modulus Hash Function and an array of structures as a Hash Table, where each array element will store the (key, value) pair.

Implementation

class HashNode {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
}
 
const capacity = 20;
let size = 0;
let arr = new Array(capacity).fill(null);
let dummy = new HashNode(-1, -1);
 
function insert(key, value) {
    let temp = new HashNode(key, value);
    let hashIndex = key % capacity;
 
    // Linear probing
    while (arr[hashIndex] !== null && arr[hashIndex].key !== key && arr[hashIndex].key !== -1) {
        hashIndex = (hashIndex + 1) % capacity;
    }
 
    if (arr[hashIndex] === null || arr[hashIndex].key === -1) {
        size++;
    }
    arr[hashIndex] = temp;
}
 
function deleteNode(key) {
    let hashIndex = key % capacity;
 
    while (arr[hashIndex] !== null) {
        if (arr[hashIndex].key === key) {
            arr[hashIndex] = dummy; // Mark as deleted
            size--;
            return true;
        }
        hashIndex = (hashIndex + 1) % capacity;
    }
    return false;
}
 
function find(key) {
    let hashIndex = key % capacity;
 
    while (arr[hashIndex] !== null) {
        if (arr[hashIndex].key === key) {
            return arr[hashIndex].value;
        }
        hashIndex = (hashIndex + 1) % capacity;
    }
    return -1;
}
 
// Example Execution
insert(1, 5);    // Index 1
insert(2, 15);   // Index 2
insert(3, 20);   // Index 3
insert(4, 7);    // Index 4
 
console.log("Value of Key 4 = " + find(4));
 
if (deleteNode(4)) {
    console.log("Node value of key 4 is deleted successfully");
} else {
    console.log("Key does not exist");
}
 
if (find(4) === -1) {
    console.log("Key 4 does not exist");
}

Output:

Value of Key 4 = 7
Node value of key 4 is deleted successfully
Key 4 does not exist

Complexity

• Time Complexity: O(capacity) for each operation in the absolute worst case (if the table is completely full and we have to probe every element). On average, it is O(1).
• Auxiliary Space: O(capacity) to store the hash table array.