How to Implement a Hash Map

#javascript #computerscience #tutorial #beginners

Arrays are amazing for looking up elements at specific indices as all elements in memory are contiguous, allowing for O(1) or constant time lookups. But often we don't, or can't, perform lookups via indices. Hash maps and hash tables are a way around this, enabling us to lookup via keys instead.

Can you implement the Map class from scratch? Only two methods are necessary-- get and set. Many programming languages have a built-in hash or dictionary primitive (like Javascript Objects and {} notation), but we don't want to use that for this exercise.

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

Note: Regular Javascript objects and the Map class are both simple key-value hash tables/associative arrays, with a few key differences:

A Map object can iterate through its elements in insertion order, whereas JavaScript's Objects don't guarantee order. In addition, Objects have default keys due to their prototype, and Maps don't come with default keys. Here's a good breakdown of the two. For the purpose of this exercise, let's assume the same functionality for both.

For the two methods you'll define:

get(key: string) should be given a key, and return the value for that key.
set(key: string, val: string) should take a key and a value as parameters, and store the pair.

Additionally, we've supplied the below hashing function hashStr. It tries to avoid collision, but is not perfect. It takes in a string value and returns an integer.

function hashStr(str) {
    let finalHash = 0;
    for (let i = 0; i < str.length; i++) {
        const charCode = str.charCodeAt(i);
        finalHash += charCode;
    }
    return finalHash;
}

console.log(hashStr('testKey'))

Let's call our new class the Hashmap class, and use it like such:

const m = new Hashmap();
m.set('name', 'Jake');
console.log(m.get('name'));

Let's begin by revisiting how a general hash table works, the theory being what our Hashmap data structure will be based off. As we've noted, in many programming languages, there is a Hashmap class that's based off a legacy Hashtable. Let's step through our suggested implementation of this code.

So we know that hash tables work by storing data in buckets. To access those buckets, we'll need a way to convert a key to an bucket number. (The buckets can be modeled using both arrays and binary search trees, but to keep things simple and maximize speed, we'll stick with using arrays.)

Using keys decouples us from having to know where the data is in the array. Our data structure thus needs a hash function, provided in this case as hashStr, to calculate an index into buckets where the wanted value is stored. We're essentially mapping the key to an array index via our hashStr hash function.

hashStr('r')
// 114

// array = [  _  ,  X  ,  _  ,  _ ]
// index     113   114   115   116

As you can see, all hashStr does is take the key provided in set(), and computes a location for us. We'll thus need another data structure for the actual storage and buckets that the values are placed. Of course, you already know it's an array!

Fill In

The slots or buckets of a hash table are usually stored in an _______ and its indices.

Solution: Array

A good start to writing the class is to initialize it with just the storage array:

class Hashmap {
  constructor() {
    this._storage = [];
  }
}

We'll use the returned index of hashStr to decide where the entered value should go in this._storage.

A word on a collisions: collisions are when a hash function returns the same index for more than one key and are out of the scope of this question. However, there are ways to handle such issues using additional data structures.

Multiple Choice

Which of the following is a solution for collisions in a hash table implementation?

There is no good solution for collisions, the hash function must be unique
Use separate chaining, often with a linked list, where the index of the array consists of a chain of values
Use a trie to store values at every index
Concatenate all the values as one single string at that bucket

Solution: Use separate chaining, often with a linked list, where the index of the array consists of a chain of values

At this point, we have our building blocks, so let's go ahead and implement the set method. The method will:

take the key passed
run it through the hash function, and
set the value in our storage at that particular index

Notice the way we're storing it as well: each index in this._storage (this._storage[idx]) is itself an array, thereby primitively solving for the collision problem.

set(key, val) {
  let idx = this.hashStr(key);

  if (!this._storage[idx]) {
    this._storage[idx] = [];
  }

  this._storage[idx].push([key, val]);
}

The set method now seems pretty straightforward, right?

It's the same concept with our get method. What we're doing there is also running the passed key through the hashStr method, but instead of setting, we'll go to the resulting index and retrieve the value.

  for (let keyVal of this._storage[idx]) {
    if (keyVal[0] === key) {
      return keyVal[1];
    }
  }

One caveat we should note is that it's possible to pass a key that doesn't exist (or has not been set), so we should handle that by returning undefined if that's the case.

get(key) {
  let idx = this.hashStr(key);

  if (!this._storage[idx]) {
    return undefined;
  }

  for (let keyVal of this._storage[idx]) {
    if (keyVal[0] === key) {
      return keyVal[1];
    }
  }
}

That should about do it! Let's try it out.

class Hashmap {
  constructor() {
    this._storage = [];
  }

  hashStr(str) {
    let finalHash = 0;
    for (let i = 0; i < str.length; i++) {
      const charCode = str.charCodeAt(i);
      finalHash += charCode;
    }
    return finalHash;
  }

  set(key, val) {
    let idx = this.hashStr(key);

    if (!this._storage[idx]) {
      this._storage[idx] = [];
    }

    this._storage[idx].push([key, val]);
  }

  get(key) {
    let idx = this.hashStr(key);

    if (!this._storage[idx]) {
      return undefined;
    }

    for (let keyVal of this._storage[idx]) {
      if (keyVal[0] === key) {
        return keyVal[1];
      }
    }
  }
}

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.