Understanding HashMaps & simple implementation in JavaScript

Photo by Shahadat Rahman on Unsplash

What is a HashMap?

A HashMap is a data structure that provides a way to store key-value pairs and allows for efficient retrieval of values based on their associated keys. It is commonly used because of its average-case constant time complexity for insertions, deletions, and lookups, making it a very efficient choice for many applications.

HashMaps are implemented using an array and a hash function. The hash function converts a key into an index in the array, where the value associated with the key is stored. If multiple keys hash to the same index, a technique called chaining (using linked lists) or open addressing (finding another open spot in the array) is used to resolve the collisions.

Lets understand the HashMaps concept irrespective of a non-technical person:

Imagine you have a big box with many small compartments inside it, like a mail sorting box at a post office. Each compartment is labeled with a number.

1. Keys and Values:

• In a HashMap, you store information (values) by associating it with a unique identifier (key). Think of the key as the name of the person and the value as the mail or item they are expecting.

2. Hash Function:

• When you want to store or retrieve an item, you use a special function (hash function) that takes the key (person’s name) and converts it into a compartment number. This function helps you quickly find the right compartment in the big box.

How HashMaps work:

1. Storing Information:

• When you get a new mail (key-value pair), you use the hash function to figure out which compartment to put it in. For example, the name “Alice” might go to compartment number 5.

2. Retrieving Information:

• When Alice comes to check her mail, you use the same hash function on her name to find out which compartment to look in. You go straight to compartment number 5 and give her the mail.

3. Collisions:

• Sometimes, two different people (keys) might be assigned to the same compartment number by the hash function. This is like two people getting their mail sent to the same compartment.

There are two main ways to handle this issue:

1. Chaining:

• Think of this as having a mini mail organizer inside each compartment. If two people’s mail ends up in the same compartment, you just keep them both in that mini organizer.
• Example: If Alice and Bob both have mail in compartment 5, you have two slots inside compartment 5, one for Alice’s mail and one for Bob’s mail.

2. Open Addressing:

• Instead of putting both items in the same compartment, you look for the next empty compartment to put the second item.
• Example: If compartment 5 is full because Alice’s mail is there, you put Bob’s mail in the next available compartment, like compartment 6.

Key Characteristics of HashMaps

1. Key-Value Pair Storage: Each entry in a HashMap consists of a key and a value.
2. Fast Access: HashMaps provide average O(1) time complexity for operations like get, set, and delete.
3. Hash Function: A function that maps keys to indices in an array.
4. Collision Handling: Techniques to handle cases where multiple keys map to the same index.

Implementing a HashMap in JavaScript

Here’s a simple implementation of a HashMap in JavaScript:

class HashMap {
  constructor() {
    this.map = {}; // Object to hold the key-value pairs
  }

  // Hash function to convert a key into a valid index
  _hash(key) {
    if (typeof key === 'number') {
      return key;
    }
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash << 5) - hash + key.charCodeAt(i);
      hash |= 0; // Convert to 32-bit integer
    }
    return hash;
  }

  // Method to set a key-value pair
  set(key, value) {
    const hashedKey = this._hash(key);
    if (!this.map[hashedKey]) {
      this.map[hashedKey] = [];
    }
    // Check if the key already exists, if so, update the value
    for (let i = 0; i < this.map[hashedKey].length; i++) {
      if (this.map[hashedKey][i][0] === key) {
        this.map[hashedKey][i][1] = value;
        return;
      }
    }
    this.map[hashedKey].push([key, value]);
  }

  // Method to get the value associated with a key
  get(key) {
    const hashedKey = this._hash(key);
    const bucket = this.map[hashedKey];
    if (bucket) {
      for (let i = 0; i < bucket.length; i++) {
        if (bucket[i][0] === key) {
          return bucket[i][1];
        }
      }
    }
    return undefined; // Return undefined if the key does not exist
  }

  // Method to remove a key-value pair
  delete(key) {
    const hashedKey = this._hash(key);
    const bucket = this.map[hashedKey];
    if (bucket) {
      for (let i = 0; i < bucket.length; i++) {
        if (bucket[i][0] === key) {
          bucket.splice(i, 1);
          if (bucket.length === 0) {
            delete this.map[hashedKey];
          }
          return true;
        }
      }
    }
    return false;
  }

  // Method to check if a key exists in the map
  has(key) {
    const hashedKey = this._hash(key);
    const bucket = this.map[hashedKey];
    if (bucket) {
      for (let i = 0; i < bucket.length; i++) {
        if (bucket[i][0] === key) {
          return true;
        }
      }
    }
    return false;
  }

  // Method to get all the keys in the map
  keys() {
    const keysArray = [];
    for (const hashedKey in this.map) {
      for (const pair of this.map[hashedKey]) {
        keysArray.push(pair[0]);
      }
    }
    return keysArray;
  }

  // Method to get all the values in the map
  values() {
    const valuesArray = [];
    for (const hashedKey in this.map) {
      for (const pair of this.map[hashedKey]) {
        valuesArray.push(pair[1]);
      }
    }
    return valuesArray;
  }

  // Method to get the number of key-value pairs in the map
  size() {
    let size = 0;
    for (const hashedKey in this.map) {
      size += this.map[hashedKey].length;
    }
    return size;
  }

  // Method to clear the map
  clear() {
    this.map = {};
  }
}

// Example usage
const hashMap = new HashMap();
hashMap.set('name', 'John Doe');
hashMap.set('age', 30);
console.log(hashMap.get('name')); // Output: John Doe
console.log(hashMap.has('age')); // Output: true
console.log(hashMap.size()); // Output: 2
hashMap.delete('age');
console.log(hashMap.has('age')); // Output: false
hashMap.clear();
console.log(hashMap.size()); // Output: 0

Explanation

1. Constructor: Initializes an empty object to hold the key-value pairs.
2. _hash(key): A private method that generates a hash code for a given key.
3. set(key, value): Adds a key-value pair to the map. If the key already exists, it updates the value.
4. get(key): Retrieves the value associated with a given key. Returns undefined if the key does not exist.
5. delete(key): Removes a key-value pair from the map. Returns true if the pair was removed, false otherwise.
6. has(key): Checks if a key exists in the map. Returns true if it exists, false otherwise.
7. keys(): Returns an array of all keys in the map.
8. values(): Returns an array of all values in the map.
9. size(): Returns the number of key-value pairs in the map.
10. clear(): Removes all key-value pairs from the map.

This implementation provides a basic HashMap in JavaScript, demonstrating the essential operations and their efficient handling.