Day 79: Hash Tables - Harshil Chovatiya

Day 79: Hash Tables

Brief:

Day 79 focuses on hash tables, a versatile data structure used for efficient data storage and retrieval. Hash tables offer constant-time average-case performance for insertion, deletion, and search operations, making them invaluable in a wide range of applications. We'll delve into their design principles, collision resolution techniques, implementation, and solve problems to solidify our understanding.

Topics Covered:

1. Hash Function:

   Definition: A hash function maps keys to indexes in the hash table, distributing elements evenly across available slots.
   Properties: Deterministic (same input produces the same output), fast computation, and uniform distribution.

2. Collision Resolution Techniques:

   Separate Chaining: Colliding elements are stored in linked lists at the same index.
   Open Addressing: Colliding elements are placed in alternative slots within the same table.

3. Implementation of Hash Tables:

   Design considerations: Load factor, resizing, and rehashing.
   Operations: Insertion, deletion, and search.

4. Applications and Problems:

   Implementing associative arrays: Mapping keys to values for efficient retrieval.
   Symbol tables: Storing and looking up symbols in compilers and interpreters.
   Caching: Storing frequently accessed data for quick access.

In-Depth Examples:

Hash Table Implementation using Separate Chaining (JavaScript):

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

    _hash(key) {
        return key % this.size;
    }

    insert(key, value) {
        const index = this._hash(key);
        this.table[index].push({ key, value });
    }

    get(key) {
        const index = this._hash(key);
        for (const pair of this.table[index]) {
            if (pair.key === key) {
                return pair.value;
            }
        }
        return null;
    }
}
            
        

Collision Resolution with Open Addressing (Linear Probing - JavaScript):

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

    _hash(key) {
        return key % this.size;
    }

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

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

Problem: Checking Anagrams using Hash Table (JavaScript):

            
            
function isAnagram(str1, str2) {
    if (str1.length !== str2.length) {
        return false;
    }
    const charCount = {};
    for (const char of str1) {
        charCount[char] = (charCount[char] || 0) + 1;
    }
    for (const char of str2) {
        if (!charCount[char]) {
            return false;
        }
        charCount[char]--;
    }
    return true;
}
            
        

Conclusion:

Day 79 has provided a comprehensive understanding of hash tables, their design principles, collision resolution techniques, and applications. Hash tables offer efficient data storage and retrieval capabilities, making them indispensable in various scenarios requiring fast access to stored information. As we continue our journey, let's explore more advanced techniques and applications of hash tables to enhance our problem-solving skills and optimize our algorithms.

Social Media