Hash table

[azurepwq]

Hash Table

Table of Contents

1. Hash Table
   1. Key Concepts of Hash Table
   2. How Hash Tables Work
      1. Insertion
      2. Retrieval
   3. Hash Collisions
   4. Collision Resolution Techniques
      1. Chaining (Linked Lists)
      2. Open Addressing
         1. Linear Probing
         2. Quadratic Probing
         3. Double Hashing
2. JavaScript Implementation of a Hash Table with Chaining
   1. Node Class
   2. HashTable Class
   3. Usage Example
   4. Explanation
3. JavaScript Implementation of a Hash Table with Linear Probing
   1. HashTable Class
   2. Usage Example
   3. Explanation

---

Hash Table

A hash table (also known as a hash map) is a data structure that stores key-value pairs. It provides an efficient way to quickly retrieve, insert, and delete items using a hash function.

Key Concepts of Hash Table

1. Hash Function: A function that takes an input (or "key") and returns an integer, known as a hash code. The hash code is then used to index into an array, where the actual data is stored.

2. Buckets: The array elements where the data is stored. Each bucket can store one or more key-value pairs.

How Hash Tables Work

1. Insertion:

   • When a new key-value pair is inserted, the hash function computes the hash code of the key.
   • The hash code is used to determine the index in the array (bucket).
   • The key-value pair is stored in the bucket.

2. Retrieval:

   • To retrieve a value, the hash function computes the hash code of the key.
   • The hash code is used to find the bucket.
   • The key-value pairs in the bucket are searched to find the matching key.

Hash Collisions

A hash collision occurs when two different keys produce the same hash code, and thus, are assigned to the same bucket. Collisions are an inevitable part of hash tables because a finite array is used to store potentially infinite keys.

Collision Resolution Techniques

1. Chaining (Linked Lists): Each bucket contains a linked list of key-value pairs. When a collision occurs, the new key-value pair is added to the list in the appropriate bucket.

2. Open Addressing: Instead of linked lists, open addressing techniques find another bucket in the array to store the collided key-value pair. Common methods include:

   • Linear Probing: If a collision occurs, check the next bucket (index + 1). Continue checking subsequent buckets until an empty bucket is found.
   • Quadratic Probing: Similar to linear probing but uses a quadratic function to determine the next bucket.
   • Double Hashing: Uses a second hash function to determine the next bucket.

JavaScript Implementation of a Hash Table with Chaining

Node Class

class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

HashTable Class

class HashTable {
    constructor(size) {
        this.size = size;
        this.table = new Array(size);
    }

    // Simple hash function
    hashFunction(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i) * i) % this.size;
        }
        return hash;
    }

    // Insert key-value pair
    insert(key, value) {
        const index = this.hashFunction(key);
        const newNode = new Node(key, value);

        if (!this.table[index]) {
            this.table[index] = newNode;
        } else {
            let current = this.table[index];
            while (current.next && current.key !== key) {
                current = current.next;
            }
            if (current.key === key) {
                current.value = value; // Update value if key already exists
            } else {
                current.next = newNode; // Add new node at the end
            }
        }
    }

    // Find value by key
    find(key) {
        const index = this.hashFunction(key);
        let current = this.table[index];

        while (current) {
            if (current.key === key) {
                return current.value;
            }
            current = current.next;
        }
        return null; // Key not found
    }
}

Usage Example

const hashTable = new HashTable(10);

hashTable.insert("apple", 1);
hashTable.insert("banana", 2);
hashTable.insert("grape", 3);
hashTable.insert("cherry", 4);
hashTable.insert("banana", 5); // Update value for "banana"

console.log(hashTable.find("banana")); // Output: 5
console.log(hashTable.find("grape"));   // Output: 3
console.log(hashTable.find("pear"));    // Output: null

Explanation

1. Hash Function: The hashFunction method computes an index based on the key. It sums the character codes of the key characters, multiplies them by their positions, and then takes the modulo of the hash table size to get a valid index.

2. Insert Method:

   • Compute the index using the hash function.
   • If the bucket at the computed index is empty, create a new node and place it there.
   • If the bucket is not empty, traverse the linked list at that index to find if the key already exists.
   • If the key exists, update its value. If not, add the new node to the end of the linked list.

3. Find Method:

   • Compute the index using the hash function.
   • Traverse the linked list at that index to find the node with the matching key.
   • Return the value if the key is found, or return null if the key is not found.

This example demonstrates the basics of a hash table with collision resolution using chaining. It can be extended with more sophisticated features and optimizations, such as dynamic resizing of the hash table, more efficient hash functions, and handling deletions.

JavaScript Implementation of a Hash Table with Linear Probing

HashTable Class

class HashTable {
    constructor(size) {
        this.size = size;
        this.table = new Array(size);
        this.keys = new Array(size); // To keep track of keys for deletion
    }

    // Simple hash function
    hashFunction(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i) * i) % this.size;
        }
        return hash;
    }

    // Insert key-value pair
    insert(key, value) {
        let index = this.hashFunction(key);

        while (this.table[index] !== undefined && this.keys[index] !== key) {
            index = (index + 1) % this.size; // Linear probing
        }

        this.table[index] = value;
        this.keys[index] = key;
    }

    // Find value by key
    find(key) {
        let index = this.hashFunction(key);

        while (this.table[index] !== undefined) {
            if (this.keys[index] === key) {
                return this.table[index];
            }
            index = (index + 1) % this.size;
        }

        return null; // Key not found
    }

    // Delete key-value pair
    delete(key) {
        let index = this.hashFunction(key);

        while (this.table[index] !== undefined) {
            if (this.keys[index] === key) {
                this.table[index] = undefined;
                this.keys[index] = undefined;
                return true;
            }
            index = (index + 1) % this.size;
        }

        return false; // Key not found
    }
}

Usage Example

const hashTable = new HashTable(10);

hashTable.insert("apple", 1);
hashTable.insert("banana", 2);
hashTable.insert("grape", 3);
hashTable.insert("cherry", 4);
hashTable.insert("banana", 5); // Update value for "banana"

console.log(hashTable.find("banana")); // Output: 5
console.log(hashTable.find("grape"));   // Output: 3
console.log(hashTable.find("pear"));    // Output: null

hashTable.delete("banana");
console.log(hashTable.find("banana")); // Output: null

Explanation

1. Hash Function: The hashFunction method computes an index based on the key. It sums the character codes of the key characters, multipl

ies them by their positions, and then takes the modulo of the hash table size to get a valid index.

2. Insert Method:

   • Compute the index using the hash function.
   • If the slot at the computed index is empty or contains a key that matches the key being inserted, place the value in that slot.
   • If a collision occurs (i.e., the slot is occupied by a different key), use linear probing to find the next empty slot.

3. Find Method:

   • Compute the index using the hash function.
   • Traverse the array starting from the computed index to find the slot containing the matching key, using linear probing.
   • Return the value if the key is found, or return null if the key is not found.

4. Delete Method:

   • Compute the index using the hash function.
   • Traverse the array starting from the computed index to find the slot containing the matching key, using linear probing.
   • Set the slot to undefined if the key is found.
   • Return true if the key is found and deleted, or false if the key is not found.

This implementation demonstrates the basic concept of a hash table with open addressing using linear probing. You can extend this with more advanced features like dynamic resizing and other probing methods (quadratic probing, double hashing) to improve performance and handle clustering issues.

[azurepwq]

This was generated by chat-gpt4o and was summarized by me.

[azurepwq]

To be added:

1. Loading factor
2. Dynamic expansion/scale up