DEV Community

Cover image for Hash tables explained in Javascript
Oğuzhan Olguncu
Oğuzhan Olguncu

Posted on • Updated on • Originally published at ogzhanolguncu.com

Hash tables explained in Javascript

Hash tables are incredibly powerful and versatile beasts. They let you store your data in a key-value format similar to the plain javascript object. But for a hash table to be effective it should have unique keys. You might think this as a phone book, each name corresponds to a phone number, so you know exactly where to look.

   Adam    --> +3435232323
   Ben     --> +2323231313
   Cambell --> +4566464534
Enter fullscreen mode Exit fullscreen mode

If you type Adam in your phone it immediately returns +3435232323 with zero down-time. Because the hash table search has O(1) complexity just like delete and insertion.

Another example of this might be storing movies in alphabetical order. As you can imagine two different movie names might start with the same letter. So, you also need to run through these movies until finding the right one. Let's suppose we are looking for The Abyss.

A
B
C
.
.
.

T ---> The Lord of the Rings
       The Godfather
       The Abyss  // Found it.
Enter fullscreen mode Exit fullscreen mode

It first ran through alphabetically then ran through movies to find the right one.

But If you have two Adam on your phone with different phone numbers or two The Abyss on your movie list, now you got collision problem, meaning two keys are identical. This should be avoided in all cases.

The reason behind unique keys are to decrease time of our get(), set(), delete() and avoid collision. Let's implement unique table using Map.

const hashTable = new Map([
  ['Adam', +12345],
  ['Ben', +12346],
  ['Cambell ', +123457],
])
hashTable.get("Cambell") // +123457

hashTable.delete("Cambell") // Deletes Cambell from list
[['Adam', +12345], ['Ben', +12346]]

hashTable.set("Cambell", +123457) // Adds Cambell to list 
[['Adam', +12345], ['Ben', +12346], ['Cambell ', +123457]]
Enter fullscreen mode Exit fullscreen mode

To prevent collision Map has useful method called has() which retuns true if Map has the searched element. I advise you to use has() before setting up new values to avoid collision.

const hashTable = new Map([
  ['Adam', +12345],
  ['Ben', +12346],
  ['Cambell ', +123457],
])
hashTable.has("Cambell") // true
Enter fullscreen mode Exit fullscreen mode

To override one of the values you can use set() again.

const hashTable = new Map([
  ['Adam', +12345],
  ['Ben', +12346],
  ['Cambell ', +123457],
])
hashTable.set("Cambell", +12345678)
[['Adam', +12345], ['Ben', +12346], ['Cambell ', +12345678]]
Enter fullscreen mode Exit fullscreen mode

Now let's suppose you've saved Adam-1 and Adam-2 under name Adam. Usually this operation takes O(n) because you need to iterate over Adam array, but in our case we are using Map this means get() operation has constant time with O(1) complexity. It's little tricky to work with it, but let's see.

const hashTable = new Map([
  ['Adam',[['Adam-1', +1234],['Adam-2', +1235]]],
  ['Ben', +12346],
  ['Cambell', +123457],
])
new Map( hashTable.get('Adam') ).get('Adam-2') // +1234
Enter fullscreen mode Exit fullscreen mode

First, we use get() as usual then create new Map from returned value, now we can again use get() for nested children.

Thanks for reading.

Top comments (0)