Implementing Hashmap data structure in JavaScript
Nov 25, 2023
•5 min read
Lets start from the most obvious question in this context;
What are data structures in programming?
In computer science, a data structure is a format to organize, manage and store data in a way that allows efficient access and modification.
Data structures are the most basic concept of any programming language that help us play with data. We store data in different data types based on the data and what we want to do with it.
For instance, if you want to store user form input, you would like to store it as an object as key value pairs, with keys being input name and value being the user input. If you want to store list of choices by user, i don't know about you, but I would store it as an array.
Different datastructures store data in a different way, work on that data in its own way, and expose data in a unique manner too. Lets have a look at Hashmap data structure.
Queue Data Structure:
Hash maps are a common data structure used to store key-value pairs for efficient retrieval. A value stored in a hash map is retrieved using the key under which it was stored. Hashmaps in JavaScript are implemented using underlying Array or Object datastructures. Basically, every value is stored against a key in case of Object, and indice if we implement it using Array.
We calculate the keys or indices using a special function called hash function.
Hashmap (Object):
In a hashmap, same values can be mapped to different keys, but a hashmap cannot contain duplicate keys. This is one of the basic principles of hashmap data structure. Have a look at an examples:
1// correct implementation
2{
3 a: 1,
4 b: 2,
5 c: 1
6}
7
8// incorrect implementation
9{
10 a: 1,
11 b: 2,
12 a: 1
13}Hashmap (Array):
We will be looking at hashmaps coded using Array data structures.
Array hashmap looks like this;
1[
2 0: ["key-1", "value-1"],
3 1: ["key-2", "value-2"],
4 2: ["key-3", "value-3"]
5]
6Now lets look at the implementation.
Lets start by creating a JavaScript ES6 Class. We will define a constructor function to initialize and array that will hold the data.
1class HashMap {
2 constructor(size) {
3 // initiates an array of length size
4 // populating undefined as value
5 this.map = new Array(size)
6 this.size = 0;
7 }
8}Hashmap methods:
We are gonna need to add some methods to our class, to add, retrieve, delete data, etc.
Hash function (_hash):
Hash function has one noble purpose to convert the key in to an array index.
We can recieve key of any datatype, so first of all we convert the key into string.
Then we simple add up the Unicode value of each charactor of string. That gives us our hash. We will later use this method inside other methods.
1class HashMap {
2 constructor(size) {
3 this.map = new Array(size).fill(null);
4 this.size = 0;
5 }
6
7 _hash(key) {
8 // initalize a str variable
9 let string = "";
10
11 // we convert key to string datatype.
12 if (typeof key === "string") string = key;
13 if (typeof key === "number") string = String(key);
14 if (typeof key === "function") string = key.toString();
15 if (typeof key === "object" && key !== null) string = JSON.stringify(key);
16
17 // initalize a hash a variable
18 let hash = 0;
19
20 for (let i in string) {
21 // add a charCode of every charactor of key string
22 hash += string.charCodeAt(i);
23 }
24
25 // apply modulas operator to ensure value is less than size
26 return hash % this.map.length;
27 }
28
29}Add Data (set):
Set method adds the data to the hashmap under specific indice calculated using _hash method.
1class HashMmap {
2 // ...
3
4 set(key, value) {
5 // calculate hash of the key
6 let hash = this._hash(key);
7
8 // set key value pair at specific index
9 this.map[hash] = [key, value];
10
11 // increment size property by 1
12 this.size++;
13
14 return [key, value];
15 }
16}Retrieve Data (get):
Get method will help us retrieve data we want using a key.
1class HashMmap {
2 // ...
3
4 get(key) {
5 // calculate hash of key
6 let hash = this._hash(key);
7
8 // return data at hash or undefined otherwise
9 return this.map[hash];;
10 }
11}Deletion (remove):
Next, we create a remove method to remove data of specific key.
1class HashMmap {
2 // ...
3
4 remove(key) {
5 // calculate hash of key
6 let hash = this._hash(key);
7
8 if (this.map[hash]) {
9 // data is defined at index
10 this.map[hash] = undefined;
11
12 // decrease size property by 1
13 this.size--;
14
15 return true;
16 }
17
18 // data not found
19 return false;
20 }
21}Testing (Collision resolution):
Now, its time to test this thing and see if it actually works. Lets create instance of Hashmap class, and try using different methods.
1const l = console.log;
2
3let hashmap = new HashMap(100);
4hashmap.set("Spain", "Madrid");
5hashmap.set("France", "Paris");
6hashmap.set("Potugal", "Lisbon");
7
8l(hashmap.get("Spain")); // ['Spain', 'Madrid']
9l(hashmap.get("France")); // ['France', 'Paris']
10l(hashmap.get("Potugal")); // ['Potugal', 'Lisbon']
11
12hashmap.remove("France");
13l(hashmap.get("France")); // undefined
14
15hashmap.set("ǻ", "some conflicting key");
16
17l(hashmap.get("ǻ")); // ['ǻ', 'some conflicting key']
18l(hashmap.get("Spain")); // ['ǻ', 'some conflicting key']Hope you spotted the problem. On last line, it is returning a value for key ǻ.
Apparently, key Spain was overwritten by key ǻ. Let me tell you why.
The problem lies in _hash function.
Problem (Collision):
When the addition of Unicode values of key string characters is same for different keys, the later key will overwrite the existing key. As Unicode value of strings Spain and ǻ is same, 507. That generates the same hash code for both values. This is called collision in hashmap. When two or more key hashes collide.
Solution (Collision resolution):
Let modify our methods to handle duplicate key hashes. We store keys with same hash, at same index, but inside next array. Lets have a look.
set:
1set(key, value) {
2 // calculate hash of the key
3 let hash = this._hash(key);
4
5 // check conflicts
6
7 if (!this.map[hash]) {
8 // no duplicates
9 // set key value pair at specific index
10 // nest key value pair inside array
11 this.map[hash] = [[key, value]];
12
13 // increment size property by 1
14 this.size++;
15
16 return [key, value];
17 }
18
19 // hash is duplicate
20
21 // loop through all values at this hash
22 // see if array item exists with same key
23 // then you would want to update value instead
24
25 for (let i = 0; i < this.map[hash].length; i++) {
26 if (this.map[hash][i][0] === key) {
27 // key is duplicate too (hash is already duplucate)
28 // in this case: update value
29 this.map[hash][i][1] = value;
30 return;
31 }
32 }
33
34 // no duplicate key found, push a new key/value pair to this hash
35 this.map[hash].push([key, value]);
36 return;
37 }get:
1get(key) {
2 // calculate hash of key
3 let hash = this._hash(key);
4
5 // data at hash
6 let temp = this.map[hash];
7
8 if (!temp) {
9 return undefined;
10 }
11
12 if (temp && Array.isArray(temp) && temp.length === 1) {
13 // no duplicate entries against this hash
14 return temp[0];
15 } else if (temp.length > 1) {
16 // duplicate entries against this hash
17 // itterate over all and find correct key/value pair
18
19 for (let i = 0; i < temp.length; i++) {
20 if (temp[i][0] === key) {
21 return temp[i];
22 }
23 }
24 }
25 }remove:
1get(key) {
2 // calculate hash of key
3 let hash = this._hash(key);
4
5 // data at hash
6 let temp = this.map[hash];
7
8 if (temp && Array.isArray(temp) && temp.length === 1) {
9 // no duplicate entries against this hash
10 return temp[0];
11 } else if (temp.length > 1) {
12 // duplicate entries against this hash
13 // itterate over all and find correct key/value pair
14
15 for (let i = 0; i < temp.length; i++) {
16 if (temp[i][0] === key) {
17 return temp[i][1];
18 }
19 }
20 }
21 return undefined;
22 }Complete implementation:
1class HashMap {
2 constructor(size) {
3 // initiates an array of length size
4 // populating undefined as value
5 this.map = new Array(size);
6 this.size = 0;
7 }
8
9 _hash(key) {
10 // initalize a str variable
11 let string = "";
12
13 // we convert key to string datatype.
14 if (typeof key === "string") string = key;
15 if (typeof key === "number") string = String(key);
16 if (typeof key === "function") string = key.toString();
17 if (typeof key === "object" && key !== null) string = JSON.stringify(key);
18
19 // initalize a hash a variable
20 let hash = 0;
21
22 for (let i in string) {
23 // add a charCode of every charactor of key string
24 hash += string.charCodeAt(i);
25 }
26 // apply modulas operator to ensure value is less than size
27 return hash % this.map.length;
28 }
29
30 set(key, value) {
31 // calculate hash of the key
32 let hash = this._hash(key);
33
34 // check conflicts
35
36 if (!this.map[hash]) {
37 // no duplicates
38 // set key value pair at specific index
39 // nest key value pair inside array
40 this.map[hash] = [[key, value]];
41
42 // increment size property by 1
43 this.size++;
44
45 return [key, value];
46 }
47
48 // hash is duplicate
49
50 // loop through all values at this hash
51 // see if array item exists with same key
52 // then you would want to update value instead
53
54 for (let i = 0; i < this.map[hash].length; i++) {
55 if (this.map[hash][i][0] === key) {
56 // key is duplicate too (hash is already duplucate)
57 // in this case: update value
58 this.map[hash][i][1] = value;
59 return;
60 }
61 }
62
63 // no duplicate key found, push a new key/value pair to this hash
64 this.map[hash].push([key, value]);
65 return;
66 }
67
68 get(key) {
69 // calculate hash of key
70 let hash = this._hash(key);
71
72 // data at hash
73 let temp = this.map[hash];
74
75 if (!temp) {
76 return undefined;
77 }
78
79 if (temp && Array.isArray(temp) && temp.length === 1) {
80 // no duplicate entries against this hash
81 return temp[0];
82 } else if (temp.length > 1) {
83 // duplicate entries against this hash
84 // itterate over all and find correct key/value pair
85
86 for (let i = 0; i < temp.length; i++) {
87 if (temp[i][0] === key) {
88 return temp[i];
89 }
90 }
91 }
92 }
93
94 remove(key) {
95 // calculate hash of key
96 let hash = this._hash(key);
97
98 // data at hash
99 let temp = this.map[hash];
100
101 if (temp && Array.isArray(temp) && temp.length === 1) {
102 // no duplicate entries against this hash
103 // rest hash
104 this.map[hash] = undefined;
105
106 this.size--;
107 return true;
108 } else if (temp.length > 1) {
109 // duplicate entries against this hash
110 // itterate over all and find correct key/value pair
111
112 for (let i = 0; i < temp.length; i++) {
113 if (temp[i][0] === key) {
114 // filter out entries
115 this.map[hash] = this.map[hash].filter((p) => p[0] !== key);
116 }
117 }
118
119 this.size--;
120 return true;
121 }
122
123 return false;
124 }
125}
126
127const l = console.log;
128
129let hashmap = new HashMap(100);
130hashmap.set("Spain", "Madrid");
131hashmap.set("France", "Paris");
132hashmap.set("Potugal", "Lisbon");
133
134l(hashmap.get("Spain")); // ['Spain', 'Madrid']
135l(hashmap.get("France")); // ['France', 'Paris']
136l(hashmap.get("Potugal")); // ['Potugal', 'Lisbon']
137
138hashmap.remove("France");
139l(hashmap.get("France")); // undefined
140
141hashmap.set("ǻ", "some conflicting key");
142
143l(hashmap.get("ǻ")); // ['ǻ', 'some conflicting key']
144l(hashmap.get("Spain")); // ['ǻ', 'some conflicting key']
145See you in the next one.