How to Implement a Hash Map
Tags: javascript, computerscience, tutorial, beginners
Published: 2020-08-25 22:17:11

---
title: How to Implement a Hash Map
published: true
description: Arrays are amazing for looking up elements, 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?
tags: javascript, computerscience, tutorial, beginners
cover_image: https://storage.googleapis.com/algodailyrandomassets/curriculum/hash-maps/implement-a-hash-map-2.png
canonical_url: https://algodaily.com/challenges/implement-a-hash-map
---

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` `Object`s  and `{}` notation), but we don't want to use that for this exercise.

_This lesson was originally published at [https://algodaily.com](https://algodaily.com/challenges/implement-a-hash-map), where I maintain a technical interview course and write think-pieces for ambitious developers._

<img src="https://storage.googleapis.com/algodailyrandomassets/curriculum/hash-maps/implement-a-hash-map-1.png" class="img-fluid" />

**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 `Object`s don't guarantee order. In addition, `Object`s have default keys due to their prototype, and `Map`s don't come with default keys. [Here's a good breakdown](https://medium.com/front-end-weekly/es6-map-vs-object-what-and-when-b80621932373) of the two. For the purpose of this exercise, let's assume the same functionality for both._

For the two methods you'll define:

1. `get(key: string)` should be given a key, and return the value for that key.
2. `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.

```js
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:

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



---



{% youtube 0pzYAOLZgqg %}

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.

<img src="https://storage.googleapis.com/algodailyrandomassets/curriculum/hash-maps/implement-a-hash-map-2.png" class="img-fluid" />

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`](/lessons/binary-search-technique) 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.



```js
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:





```js
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?









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



**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:

1. take the `key` passed
2. run it through the hash function, and
3. 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.



```js
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.





```js
  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.





```js
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.

```js
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](https://algodaily.com/challenges/implement-a-hash-map), where I maintain a technical interview course and write think-pieces for ambitious developers._