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:

Copy code
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;

Copy code
1[
2  0: ["key-1", "value-1"],
3  1: ["key-2", "value-2"],
4  2: ["key-3", "value-3"]
5]
6

Now 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.

Copy code
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.

Copy code
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.

Copy code
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.

Copy code
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.

Copy code
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.

Copy code
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:

Copy code
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:

Copy code
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:

Copy code
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:

Copy code
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']
145

See you in the next one.