Implementing HashMaps in JavaScript

Welcome to another installment of our JavaScript Series! Today, we're diving deep into a fundamental and incredibly powerful data structure: the HashMap. Also known as a Hash Table, Dictionary, or Associative Array, HashMaps are essential for efficient data storage and retrieval. While JavaScript provides a built-in Map object, understanding the underlying mechanics by implementing one from scratch is invaluable for any developer.

By the end of this post, you'll have a solid grasp of how HashMaps work, why they're so efficient, and how to build your own custom version in JavaScript.

What is a HashMap?

At its core, a HashMap stores data in key-value pairs. Think of it like a dictionary where each unique "word" (the key) has a corresponding "definition" (the value). The magic of a HashMap lies in its ability to retrieve a value associated with a given key almost instantly, typically in O(1) average time complexity.

This near-constant time performance makes HashMaps ideal for scenarios requiring fast lookups, insertions, and deletions, such as:

• Caching mechanisms
• Storing user profiles by ID
• Symbol tables in compilers
• Frequency counters for words or characters

How Do HashMaps Work? The Core Concepts

The efficiency of a HashMap stems from two main components:

1. Hash Function

When you add a key-value pair to a HashMap, the key isn't stored directly. Instead, it's fed into a special function called a hash function. This function takes the key as input and outputs a numerical hash code (an index) that points to a specific location (or "bucket") in an underlying array where the value will be stored.

A good hash function should:

• Be deterministic (the same key always produces the same hash).
• Distribute keys evenly across the available buckets to minimize collisions.
• Be fast to compute.

2. Collision Resolution

It's inevitable that two different keys might produce the same hash code, leading to a "collision." When this happens, the HashMap needs a strategy to store both key-value pairs at the same bucket index. Common strategies include:

• Separate Chaining: Each bucket stores a list (or another data structure) of all key-value pairs that hash to that index. When a collision occurs, the new pair is simply added to the list at that bucket.
• Open Addressing: When a collision occurs, the HashMap probes for the next available empty slot in the array using various techniques (linear probing, quadratic probing, double hashing).

For our implementation, we'll use separate chaining because it's generally simpler to implement and debug, especially for learning purposes. Each bucket in our underlying array will hold an array of [key, value] pairs.

Implementing Our Custom HashMap in JavaScript

Let's start building our HashMap class.

1. Basic Structure and Constructor

We'll define a class with a default capacity for our storage array (buckets).

class HashMap {
    constructor(capacity = 16) {
        this.buckets = new Array(capacity).fill(null).map(() => []); // Initialize buckets as arrays
        this.size = 0; // Number of key-value pairs
    }
}

2. The Hash Function (_hash method)

This private helper method will convert a string key into an array index. A simple but effective hash function for strings often involves iterating through the characters and performing some arithmetic operations.

class HashMap {
    // ... constructor ...

    _hash(key) {
        let hashCode = 0;
        const primeNumber = 31; // A common prime used in hashing

        for (let i = 0; i < key.length; i++) {
            hashCode = (primeNumber * hashCode + key.charCodeAt(i)) % this.buckets.length;
        }

        return hashCode;
    }
}

Here, we use charCodeAt(i) to get the ASCII value of each character, multiply it by a prime number, add to the running hashCode, and then take the modulo of the buckets.length to ensure the index fits within our array boundaries.

3. Adding Key-Value Pairs (set method)

The set method will take a key and a value, hash the key to find the bucket index, and then store the [key, value] pair. If the key already exists in that bucket, we should update its value. If not, we add a new pair.

class HashMap {
    // ... constructor and _hash ...

    set(key, value) {
        const index = this._hash(key);
        const bucket = this.buckets[index];

        // Check if key already exists in the bucket
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket[i][1] = value; // Update existing value
                return;
            }
        }

        // Key does not exist, add new pair
        bucket.push([key, value]);
        this.size++;

        // Optional: Implement resizing if load factor is too high
        // If (this.size / this.buckets.length > 0.75) { this._resize(); }
    }
}

4. Retrieving Values (get method)

The get method also hashes the key to find the correct bucket. Then, it iterates through the pairs in that bucket to find the matching key and return its value.

class HashMap {
    // ... constructor, _hash, set ...

    get(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];

        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                return bucket[i][1]; // Found the value
            }
        }
        return undefined; // Key not found
    }
}

5. Checking for Key Existence (has method)

Similar to get, but just returns a boolean.

class HashMap {
    // ... all previous methods ...

    has(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];

        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                return true;
            }
        }
        return false;
    }
}

6. Deleting Key-Value Pairs (delete method)

To delete, we find the bucket, locate the key, and then remove that specific key-value pair from the bucket's array.

class HashMap {
    // ... all previous methods ...

    delete(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];

        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket.splice(i, 1); // Remove the pair
                this.size--;
                return true;
            }
        }
        return false; // Key not found
    }
}

7. Iteration Methods (keys, values, entries)

These methods allow us to retrieve all keys, values, or key-value pairs (entries) stored in the HashMap.

class HashMap {
    // ... all previous methods ...

    keys() {
        const allKeys = [];
        for (const bucket of this.buckets) {
            for (const [key, value] of bucket) {
                allKeys.push(key);
            }
        }
        return allKeys;
    }

    values() {
        const allValues = [];
        for (const bucket of this.buckets) {
            for (const [key, value] of bucket) {
                allValues.push(value);
            }
        }
        return allValues;
    }

    entries() {
        const allEntries = [];
        for (const bucket of this.buckets) {
            for (const entry of bucket) { // entry is already [key, value]
                allEntries.push(entry);
            }
        }
        return allEntries;
    }

    clear() {
        this.buckets = new Array(this.buckets.length).fill(null).map(() => []);
        this.size = 0;
    }
}

Putting It All Together: Complete HashMap Class

class HashMap {
    constructor(capacity = 16) {
        this.buckets = new Array(capacity).fill(null).map(() => []);
        this.size = 0;
    }

    _hash(key) {
        let hashCode = 0;
        const primeNumber = 31;

        for (let i = 0; i < key.length; i++) {
            hashCode = (primeNumber * hashCode + key.charCodeAt(i)) % this.buckets.length;
        }
        return hashCode;
    }

    set(key, value) {
        const index = this._hash(key);
        const bucket = this.buckets[index];

        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket[i][1] = value;
                return;
            }
        }

        bucket.push([key, value]);
        this.size++;
    }

    get(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];

        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                return bucket[i][1];
            }
        }
        return undefined;
    }

    has(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];

        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                return true;
            }
        }
        return false;
    }

    delete(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];

        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket.splice(i, 1);
                this.size--;
                return true;
            }
        }
        return false;
    }

    keys() {
        const allKeys = [];
        for (const bucket of this.buckets) {
            for (const [key, value] of bucket) {
                allKeys.push(key);
            }
        }
        return allKeys;
    }

    values() {
        const allValues = [];
        for (const bucket of this.buckets) {
            for (const [key, value] of bucket) {
                allValues.push(value);
            }
        }
        return allValues;
    }

    entries() {
        const allEntries = [];
        for (const bucket of this.buckets) {
            for (const entry of bucket) {
                allEntries.push(entry);
            }
        }
        return allEntries;
    }

    clear() {
        this.buckets = new Array(this.buckets.length).fill(null).map(() => []);
        this.size = 0;
    }
}

Usage Examples

Let's see our custom HashMap in action:

const myMap = new HashMap();

myMap.set("name", "Alice");
myMap.set("age", 30);
myMap.set("city", "New York");
myMap.set("occupation", "Engineer");

console.log("Size:", myMap.size); // Output: Size: 4
console.log("Name:", myMap.get("name")); // Output: Name: Alice
console.log("Age:", myMap.get("age"));   // Output: Age: 30
console.log("Has city?", myMap.has("city")); // Output: Has city? true
console.log("Has country?", myMap.has("country")); // Output: Has country? false

myMap.set("name", "Alicia"); // Update an existing key
console.log("Updated Name:", myMap.get("name")); // Output: Updated Name: Alicia

myMap.delete("age");
console.log("Size after delete:", myMap.size); // Output: Size after delete: 3
console.log("Age after delete:", myMap.get("age")); // Output: Age after delete: undefined

console.log("All Keys:", myMap.keys()); // Output: [ 'name', 'city', 'occupation' ]
console.log("All Values:", myMap.values()); // Output: [ 'Alicia', 'New York', 'Engineer' ]
console.log("All Entries:", myMap.entries()); // Output: [ [ 'name', 'Alicia' ], [ 'city', 'New York' ], [ 'occupation', 'Engineer' ] ]

myMap.clear();
console.log("Size after clear:", myMap.size); // Output: Size after clear: 0

A Note on JavaScript's Built-in Map Object

It's important to remember that JavaScript already provides a highly optimized, built-in Map object. This native Map handles complexities like non-string keys (objects, functions, etc.), better hash functions, and dynamic resizing much more robustly than our simple custom implementation.

For most real-world applications, you should use the native Map. Our custom HashMap is primarily for understanding the fundamental principles and mechanics.

const nativeMap = new Map();

nativeMap.set("greeting", "Hello");
nativeMap.set(123, "Number Key");
const objKey = { id: 1 };
nativeMap.set(objKey, "Object Value");

console.log(nativeMap.get("greeting")); // Output: Hello
console.log(nativeMap.get(123));        // Output: Number Key
console.log(nativeMap.get(objKey));     // Output: Object Value

Conclusion

Implementing a HashMap from scratch is an excellent exercise for deepening your understanding of data structures. You've learned about the crucial role of hash functions, how collisions are resolved using separate chaining, and built a functional HashMap with core operations like set, get, has, and delete.

HashMaps are fundamental to efficient programming and are widely used across various domains. While JavaScript's native Map is the go-to for production, knowing how to build one yourself equips you with invaluable knowledge for tackling complex problems and optimizing your code.