DEV Community

Ashutosh Sarangi
Ashutosh Sarangi

Posted on

Hash Map using Javascript

Introduction

  • A Hash Map, also known as a Hash Table, is a data structure that implements an associative array abstract data type, a structure that can map keys to values.
  • It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

  • The primary advantage of a Hash Map is its efficiency. Operations like inserting a new key-value pair, deleting a key-value pair, and looking up a value given a key are all very fast, often taking constant time on average.

Implementing a Simple Hash Map in JavaScript

let hashMap = {};
hashMap['key1'] = 'value1';
hashMap['key2'] = 'value2';
console.log(hashMap['key1']); // Outputs: value1
Enter fullscreen mode Exit fullscreen mode

Handling Collisions

  • Handling collisions is an important aspect of implementing a Hash Map. A collision occurs when two different keys produce the same hash. There are several strategies to handle collisions, but the two most common ones are separate chaining and linear probing.

Separate Chaining: In separate chaining, each slot in the hash table's array contains a linked list (or another data structure that can hold multiple items). When a collision occurs, the new key-value pair is added to the end of the linked list at the corresponding index.

Here's a simple implementation of a Hash Map using separate chaining in JavaScript:

class HashMap {
  constructor() {
    this.table = new Array(100).fill(null).map(() => []);
  }

  put(key, value) {
    const index = this.hash(key);
    const chain = this.table[index];
    const existingPair = chain.find(([existingKey]) => existingKey === key);

    if (existingPair) {
      existingPair[1] = value;
    } else {
      chain.push([key, value]);
    }
  }

  get(key) {
    const index = this.hash(key);
    const chain = this.table[index];
    const pair = chain.find(([existingKey]) => existingKey === key);

    if (pair) {
      return pair[1];
    }

    return null;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }
}
Enter fullscreen mode Exit fullscreen mode

Linear Probing: In linear probing, when a collision occurs, the hash map checks the next slot in the array (and continues to the next one if that's also full, and so on) until it finds an empty slot where it can store the new key-value pair.

Here's a simple implementation of a Hash Map using linear probing in JavaScript:

class HashMap {
  constructor() {
    this.table = new Array(100).fill(null);
  }

  put(key, value) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      index = (index + 1) % this.table.length;
    }
    this.table[index] = [key, value];
  }

  get(key) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      if (this.table[index][0] === key) {
        return this.table[index][1];
      }
      index = (index + 1) % this.table.length;
    }
    return null;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }
}
Enter fullscreen mode Exit fullscreen mode

In both examples, the hash method is a simple hash function that converts the key into an integer that is used as an index in the array. In a real-world scenario, you would likely use a more complex hash function to reduce the likelihood of collisions.

Top comments (11)

Collapse
 
peeleebee profile image
Phillip Anerine

I think it's interesting to learn how data structures work under the hood, but for practical code, Javascript (and almost all programming languages) already have this natively implemented with objects and Map, and you're not going to beat the performance and security of V8 with js code.

Collapse
 
ashutoshsarangi profile image
Ashutosh Sarangi

True, totally true,
It is just like we are writing sorting algorithm for our own practice. as Javascript's sorting algorithm even better in compare to QuickSort.

So Here I am not challenging to V8, as they are written in c++, 😊.

Hope you understand.

Collapse
 
alex_pacurar_8649cf09c1e9 profile image
Alex Pacurar

I fail to see the reasoning of using HashMaps in js. You obtain the same behaviour of having stored a value in relation to a string key by using the native objet key property implementation available in js.

const put = (map, key, val)=> {
map[key]= val;
};
const get = (map, key)=>{
return map[key];
};

This implementation must be optimal, because it doses not have 'hidden' iterations on the data structure.

But then again, I didn't compare the performances

Collapse
 
ashutoshsarangi profile image
Ashutosh Sarangi

Correct, The only scenarios where we can use Hashmap which I know is Least recently Used cache Algorithm. There we can use.

That combines HashMap + Double Linked list to achieve all the Operations.

But for simple use cases we can use simple JSON objects.

I hope this helps.

Collapse
 
syeo66 profile image
Red Ochsenbein (he/him)

And why not use javascripts native Map or even WeakMap for caching stuff?

Thread Thread
 
ashutoshsarangi profile image
Ashutosh Sarangi

True, we can do the same. Sorry I missed those earlier.

Collapse
 
abhinowww profile image
Abhinav Anand

Informative

Collapse
 
ashutoshsarangi profile image
Ashutosh Sarangi

Thank you Abhinav

Collapse
 
hbthepencil profile image
HB_the_Pencil

So, are these just like dictionaries in Python?

Collapse
 
peeleebee profile image
Phillip Anerine

Dictionaries are a native implementation of hash maps, and Javascript objects are too, so yes

Collapse
 
hbthepencil profile image
HB_the_Pencil

Oh, I see. Thank you!

Some comments may only be visible to logged-in visitors. Sign in to view all comments.