HashMap in Javascript — Plain Object Vs Map.Prototype

Before jumping to the comparison of Plain object and Map.Prototype lets first talk about definition and application of Hashmap.

Hashmap is one of the most commonly used data structure. The main application of hashmap is to find and retrieve data quickly (in O(1)or constant time). Hashmap contains data in the form of key, value pairs and useually must contains these three methods

1. Get — to retrieve the value against key in O(1) time
2. Put or Set — to set the value against key in O(1) time
3. Has or ContainsKey — to check if key exist in hashMap in O(1) time

Application of HashMap

If we want to chek if a character exists in a string and also needs to know the frequency (number of occurence) of any character than HashMap can be an ideal choice. We can iterate through string and create a HashMap with each unique character as key and character’s frequency as value.

For String S="HELLO WORLD", the HashMap M will look like this:
                 Key →  Value           
                 H   →    1                 
                 E   →    1
       M    =    L   →    3
                 O   →    2
                 W   →    1
                 D   →    1
Methods:
M.get('H') will return 1 in constant time
M.has('D') will return true in constant time
M.put('A', 1) will add A → 1 in hashmap in constant time

HashMap in Javascript:
Approach #1 — Using Plain Object

The simplest way to build hashmap in javascript is to use plain object like

let map = {};
// to set value 
map['H'] = 1;
// to get value
let frequencyOfH = map['H'];
// to check if key exist
if(map['H']){
    console.log('Map contains H');
}
// Or 
if('H' in map){
   console.log('Map contains H');
}

Problems with using Plain Object as HashMap:

There are two main problems that can occure if we use plain object as HashMap

Problem#1 — Derived Properties

Every object in javascript is derived from Object.Prototype so there are some properties that are present by default even in the plain empty object

//For example
let m = {}
console.log("Is toString present in m ?", "toString" in m)
// → Is toString present in m ? true

We never defined toString property in our object m but its present in Object.Prototype and Javascript first looks for property in object (in our example m) and then if property does not exist in object then it looks for the same property in the prototype of object (ie: Object.Prototype).

Solution:
Above problem can be solved by creating object from null like instead of
let m={}we can dolet m = Object.create(null) so that we are sure that our created object is absolutely empty.

Problem#2 — Non primitive data types as keys are not supported

Sometimes keys of hashmap can be in type that is either not a string or not easily convertable to string ( AKA non primitive data types for example objects). In those casses we can’t use plain object as hashmap.

/*
For example 
if our key is object key and our HashMap is object map
*/
let key1 = { 'a': 123 };
let map = {};
// if we put key object as key in our map object like
map[key1] = 'hello world';
/*
Our object will look like this
{[object Object]: "hello world"}
*/
// Now if we put another key, key2 like
let key2 = { 'b': 456};
map[key2] = 'abc';
/*
 Our object will look like this
 {[object Object]: "abc"}
*/
/*
Since in Javascript conversion from object to string will always result in [object Object] hence we cannot uniquely identify    objects and hence we cannot use them as a unique key in our     hashmap.
*/

Solution:
One possible workarround to above problem can be using JSON.stringify to convert object into string. Because that way object with different content will genrate different string but still there is a possibility that two different object may contain same content. In those casses even using JSON.stringify will not help

Approach #2 — Using Map Prototype

Due to the two major problems with using plain object as hashmap javascript also offers a dedicate Map prototype to create HashMaps

/*
For example if we implement character frequency example using Map it will be like this
*/
let str = "HELLO WORLD";
let freqMap = new Map();

for(let s of str){
    if(s === ' ')
        continue;  //skip the empty string
    //if character already exists in freqMap
    if(freqMap.has(s)){
        //increment the frequency count
        freqMap.set(s, freqMap.get(s)+1);

    }
    else{ //if character does not exists in freqMap

        //initialize character in freqMap with 1 as freq
        freqMap.set(s, 1);
    }
}
console.log(freqMap);
/*
0: {"H" => 1}
1: {"E" => 1}
2: {"L" => 3}
3: {"O" => 2}
4: {"W" => 1}
5: {"R" => 1}
6: {"D" => 1}
*/

Non primitive data types as keys

Using Map we can also use non primitive data types as keys.

/*
For example we can set our object key1 in our Map m
*/
let m = new Map();
let key1 = {'abc':1};
m.set(key1, 'hello world');
let resp = m.get(key1);
console.log(resp);
// hello world
console.log(m);
/*
0: {Object => "hello world"}
    key: {abc: 1}
    value: "hello world"
*/
/*
Notice Map m is using key1 as it is (ie: {abc: 1}) and not converting it to [object Object] so that every object can be uniquely identified
*/

Caveat:

Using Non primitive data types as keys in Map effects the worst case time comlexity of getand hasoperation. With primitive data type Map's worst case time comlexity of get and hasoperation is constantand O(1)but using non primitive data types as keys will make worst case time complexity of get and has linear or O(N)

Solution— Instead of Map use WeakMap to get constant O(1) worst case time complexity with non primitive data types as key