Hash Tables in JavaScript

Introduction
Hi I’m a software engineer who is working a lot with JavaScript in these days. This article is about what I learned and understand about hash table in general and it’s implementation in JavaScript.

What are Hash Tables?
Hash tables are data structures for storing key/value pairs. They also called dictionaries. They contain places called buckets or slots for keeping items. The number of these slots represents the length of our hash table. For example if we have a hash table of length 1000, it means it has 1000 slots/buckets to keep 1000 items.

Where we use them?
The run-time complexity of hash table’s actions are:
Insert: O(1)
Lookup: O(1)
Delete: O(1)
As you can see hash tables are very fast! They are used in compilers, code editors, dictionaries and lots of other places. Practically saying if you have some data with unique keys and you need a very fast look up, you should use hash tables (in some situations, the worst case scenario for insert and delete can be O(n) but since they rarely happen, we can stick with O(1)).
There are lots of famous interview questions that can be answered by hash tables. Like the first non-repetitive character in a string.

Where we can find them?
Most programming languages support hash tables under different names.
Java: HashMap
C# & Python: Dictionary
JavaScript: Object and Map !
Yes! both maps and objects are hash tables and I’m going to talk about them more in JavaScript.

How Hash Tables work
When I was learned about hash tables I found out that they use an array to store items. On that moment I had couple of question. The most important ones was:
What’s the point of using hash tables if they use Arrays for storing? We can simply use Arrays instead!

1. If they are using an Array, how the run-time complexity of a hash table is O(1)?! For example, to find (lookup) an item it needs to iterate over all items (like searching an item in an Array by value) which is a operation of O(n). But it’s not iterating over all items! Hash tables has a mechanism call Hash Function. As the name explains, it’s a function that returns an index by giving it a key. And it’s deterministic, which means every time that we give it the same input it will return the same value. So for inserting, deleting or searching we give it a key(our key for data) and it will always return the same index for each individual key. And then our hash table goes directly to that index of it’s array and it’s a operation of O(1)! Hash function in a hash table Imagine we have a list of students to store. Each has a unique student Id. So our key is student Id and our student object is the value. We passing this key/value pair to our hash table. It gets the key, pass it to hash function and hash function returns an index (for example 2). Then hash table stores the key/value pair in the given index (in our case 2). After that if we want to get that specific student, we just pass the student Id to hash table and our hash function gives us 2 as index again (because of it’s deterministic behavior).

Hash Tables in JavaScript
Before ECMAScript, when every thing in JavaScript world was less interested (imagine rock’n roll world without Jimi Hendrix, Zepplin or Pink Floyd!), people used objects for hash table scenarios. Because the key/value pair structure of objects and the fact that every key needs to be unique.
It’s great and solving most of the problems but it has it’s own down sides. For example:
The keys of an Object must be either a String or a Symbol. It’s not usable for some scenarios that we need other types (like objects) as keys.
An Object has a prototype, so it contains default keys that could collide with your own keys if you’re not careful.
The keys of an Object are not ordered (in case you need ordered lists).
The number of items in an Object must be determined manually. It can’t tell you the length of it’s keys or items (properties).
Iterating over an Object requires obtaining its keys in some fashion and iterating over them. You need to use Object.keys() first to retrieve keys and then start to iterating.
Not optimized for frequent additions and removals of key-value pairs. In case you have lots of adding or removing items (which usually you have!).
But after the Hendrix, sorry the ECMAScript, beside lots of other beauties and features, Maps was announced. A specific implementation of hash tables. It has lots of benefits instead of object, for using in hash table problems:
A Map does not contain any keys by default. It only contains what is explicitly put into it.
A Map’s keys can be any value (including functions, objects, or any primitive).
The keys in Map are ordered. Thus, when iterating over it, a Map object returns keys in order of insertion.
The number of items in a Map is easily retrieved from its size property.
A Map is an iterable, so it can be directly iterated.
Performs better in scenarios involving frequent additions and removals of key-value pairs.
Based on above information it’s recommended to use Maps if it’s supported in your project and your targeted browsers.

Set
There is another structure called Set which is similar to maps but contains just keys. Like maps, in sets keys are unique so a value in the Set may only occur once.
They are useful for solving lots of problems, for example if we need to remove duplicate items in a list , we can use sets.

At The End
I hope I could explain well what I learned about hash tables so far. I will be more that happy for any suggestion, correction and advice from anyone.