7. Connecting the dots — Big O and Hash Table Data Structure

In JavaScript, objects are stored as key value pairs. This is an example of inbuilt hash table in the language itself. If you want to customize hash table and create your own you can. Hash tables can be implemented as a linear or non-linear data structure. Most of the time, they are implemented as a linear data structure.

Before we start with hash table, let us understand the question below

what is an associative array, hashing and collision?

Associative arrays are JS objects which stores objects as unique user defined keys. When object mapping happens like this it called “Hashing”. Hashing always returns key-value pairs.

Hashing

Collision is when two items are mapped to the same spot in the memory.

Collisions mapping to the same spot in memory

Handling Collisions:

Collisions can be handled by the following ways

Linear Probing:

When we try to add a key to the array which is already occupied, we keep probing the hash table until an empty slot is found. Once an empty slot is found, the key is inserted into that slot. Linear probing is a type of open addressing.

Linear probing where items are placed when an empty slot is found

Separate chaining:

We can store the items separately to avoid collision using chaining with either arrays or linked list.

Separate chaining using arrays and linked list

Let us see how to implement code for separate chaining using Arrays for creating a constructor, hash function which calculates the index of a key in the table, set(key,value), getting the item based on key and finally returning all the keys in the hash table.

Output:

Output of the above code

Finally, finding by a key or value and inserting an item in a Hash table takes Big O(1). The performance of a hash table depends upon hash function, size of the table and the choice of collision handling method.

With this article, we covered JavaScript data structures series. Here are the rest of the articles in this series if you would like to read.

Other related articles:

Big O Notation-what is this thing?

1. Connecting the dots — Big O and Array Data Structure
2. Connecting the dots — Big O and Linked List Data Structure
3. Connecting the dots — Big O and Trees Data Structure
4. Connecting the dots — Big O and Stacks Data Structure
5. Connecting the dots — Big O and Queue Data Structure
6. Connecting the dots — Big O and Graph Data Structure
7. This article: Connecting the dots — Big O and Hash Table Data Structure

Hope you liked the JavaScript Data Structure series. I will be coming up with new articles soon. Stay tuned.

Thanks for reading this article and please follow me and give a 👏.

References:

Wikipedia, Grokking Algorithms, Big O cheatsheet , Interview.io