You might have heard of hash maps or hash tables while programming. If you’ve only used Javascript, there is a chance this is the first time you’re hearing about them, as they are not a native object in this language.
However, there are multiple ways to implement them in your work, if that is what your project needs, and you can do it pretty easily at that too.
What are Hash Maps?
Hash Maps, also commonly called Hash Tables, are abstract data structures used to implement an associative array, which is a structure that binds keys to values. A Hash Map uses a hash function to generate an index into an array of slots where we can find the desired value. Ideally, a key will take us to a unique slot of value, but it happens very often that we have collisions, which presents us with another issue: That of avoiding these collisions by accommodating the values somehow into the data structure.
Other issues to take care of when implementing a Hash Map are having the functions created on it not depend on the number of data stored in a Hash Map, and also allowing arbitrary insertion or deletion of a key-value pair into the structure. Lastly, when done right, this structure can be even more efficient than search trees or other structures designed to store elements, which is why we will strive to do just that. Let’s see more about this below!
What are Hash Functions?
When explaining what Hash Maps are we also mentioned Hash Functions. But what are they exactly? A hashing function can be just about anything, as the way it is coded depends sorely on the situation it is to be used. However, there are some specifications that these functions must accomplish. Generally, they have to return a value based on a key you provide and the size of the array based on which the hashmap is implemented. Also, it is important to note that the result should be always the same for a given key.
One of the situations in which hashmaps are mot commonly used are contact lists. Let’s say you have a contact list consisting of 260 people. For each person you have their name and their number. The best way to organize this would be to sort your list based on numbers. As you may have already grasped, the names would serve as values and the numbers as keys. Since we have 260 ‘slots’ and 26 letters of the alphabet, we can consider every letter to have about 10 slots in their use each.
Let’s say you want to access the phone number of a person whose name starts with and E. Since this letter is the 5th one of the alphabet, and every letter has 10 slots available to use, in order to get to the first name that starts with an E, our hashing function would be one that takes you to (index-1)*10, where by index we have the number which corresponds to the letter in alphanumerical order. As you see, we just need an index to get to the desired entry, which makes the access time of the hashmap relatively low compared to linked lists implementations etc. Easy and convenient, right?
Handling Collisions
We did call hashmaps easy and convenient above, but that is until there are no entries with the same name. What do we do if there are more than one contacts whose name would start with the same letter? Say we know both Leah and Laura. Both would have the same index, so if we place Leah first in the hashmap, later when we want to place Laura, we will find that we have no more space because the slot is taken. There are several algorithms that take care of this small inconvenience. Let’s see the most efficient and most commonly used ones below.
Open Addressing collision handling
Collision handling using the Open Addressing Algorithm, or Closed Hashing is the simplest and most used method to take care of collisions. You might have noticed in the previous example that we gave each letter of the alphabet 10 slots to store their values, but only used one of them. The other ones will be used by this method to store the values that clash with other previously stored ones.
When you are adding an element, say “Whitney,” and you find that another element is already there, say “Will”, you would just proceed to the next element space (the one after “Will”). If that is filled, you go on to the next one, and so on, until you find an empty space to insert the new element.
However, since you modified the insertion algorithm, you also have to modify the hashing function because you have to have a way to ensure that you have found the element you were looking for and not some other one. The simplest way is to just compare keys until you find the right entry or reach the end of the list (which would mean that this entry is not in the list at all).
Moreover, it might happen that when trying to insert entries into your hashmap, you reach the end of the associative array. What you do is put in use the concept of circular arrays, which means that after running out of space in the end of the array, you start inserting entries in the beginning of it, until all the slots allocated are taken.
Separate Chaining collision handling
Another common method of handling collisions is Separate Chaining. It consists of a very simple principle: Every time a collision is encountered, you put the element into a linked list stored in the elements index. If you have only a single element with a particular hash value, then you have a single element list, which means no performance penalty. If you have a lot of elements hashing in the same value, you will have some sort of slowdown but the good news is this rarely is too problematic.
One nice thing about separate chaining is that having a bunch of values that hash “near” each other is less important. With open addressing, if you have a cluster of values that hash to nearly the same value, you’ll run out of open space in that part of the hash. With separate chaining, each element that has a different hash value will not impact the other elements.
Moreover, there are also other methods that deal with collisions, which are mostly hybrids of the previous too. The good thing is you can choose whichever is best for your application.
Implementation of a Hash Map
Now that we understand the basics of what Hash Maps are, we can very easily implement them in any language, including Javascript. First of all, let’s write the code for the constructor of the Hashtable class. Take a look at the code snippet below:
var hasOwnProperty = [].hasOwnProperty;
function Hashtable(obj) {
obj = arguments.length ? obj : {};
var hash = {}, key, keys = unenumerableKeys.slice(0), i = 0;
while(key = keys[i++]) {
!hasOwnProperty.call(obj, key)
? hash[key] = obj[key]
: keys.splice(i, 1);
}
for(key in obj) {
if(hasOwnProperty.call(obj, key)) {
keys.push(key);
hash[key] = obj[key];
}
}
var _ = {o : hash, k : keys};
this._ = function(k) {
return k === $ ? _ : undefined;
};
return this;
}
var p = Hashtable.prototype;
After defining the constructor of the new Hashtable object, you might notice that in the last line of the previous code snippet we have added a reference to make adding the methods to the object easier by prototyping them in the p object. Let’s get to it!
p.get = function(key) {
return this._($).o[key];
};
The code above is a method named get(), which would give us the item that corresponds to the specified key. Meanwhile, in the code below we have a method which we have called keys() that would give us an array of all the keys in the hash table.
p.keys = function() {
return this._($).k.slice(0);
};
Next, we will create a function that tells us whether or not a value exists within a hash map using a boolean value as a result. The code would go like below:
p.containsValue = p.contains = function(value) {
var _ = this._($), keys = _.k, obj = _.o, i = keys.length;
while(--i >= 0) {
if(obj[keys[i]] === value) {
return true;
}
}
return false;
};
Of course, we could do the same regarding keys, as it might happen that a key is not located in a hashmap. The code would look like this:
p.containsKey = function(key) {
var keys = this._($).k, i = keys.length;
while(--i >= 0) {
if(keys[i] == key) {
return true;
}
}
return false;
};
In much the same way, we can also get an array of all the values contained in the hashmap, like below:
p.elements = function() {
var elems = [],
_ = this._($),
keys = _.k,
i = 0,
len = keys.length,
obj = _.o;
while(i < len) {
elems.push(obj[keys[i++]]);
}
return elems;
};
Also, we could find how many items there are in our hash map, by using the code below:
p.size = function() {
return this._($).k.length;
};
The two following functions are maybe the most important in the implementation of a hash map. Let’s take a look at the code below:
p.remove = function(key) {
var _ = this._($), keys = _.k, obj = _.o, i = keys.length;
while(--i >= 0) {
if(keys[i] == key) {
var ret = obj[keys.splice(i, 1)[0]];
delete obj[key];
break;
}
}
return ret;
};
The first function is remove(), which removes the item at the specified key and then returns it as a result. Next up is the function put(), which inserts a key-value pair into the hashmap and returns the previous entries of it. We have divided the code into two pieces, as there are two possible cases that we might encounter: when we want to add just one value, or when we want to add multiple values. See below:
p.put = function(key, value) {
var _ = this._($), keys = _.k, obj = _.o;
if(arguments.length - 1) {
if(hasOwnProperty.call(obj, key)) {
ret = obj[key];
}
else {
keys.push(key);
}
obj[key] = value;
}
else {
var ret = {},
objNew = key,
newKeys = (new Hashtable(objNew)).keys(),
i = newKeys.length;
while(--i >= 0) {
_ = newKeys[i];
if(hasOwnProperty.call(obj, _)) {
ret[_] = obj[_];
}
else {
keys.push(_);
}
obj[_] = objNew[_];
}
}
return ret;
};
Another very useful function is the one showing us whether the hash table is empty or not. We could find that out using the code below:
p.isEmpty = function() {
return !this._($).k.length;
};
These are the most common functions created when implementing hash maps. However, a good hash table is one that is created according to the situation it is to be used in, so my advice is to not hesitate to experiment on this on your own.
Download the source code
This was an example of Hashmap Implementation in Javascript. Download the source code for this tutorial:
You can download the full source code of this example here : HashMaps
Too bad the download source link doesn’t work. In Chrome it reports a cross domain problem and blocks it.
Hello Michael, please try again the link is now fixed!