Hash Table is a data structure that maps keys to values. You can then retrieve a certain value by using its key.
The way Hash Table Work?
• It takes a Key and then runs it through a Hash Function.
• A Hash Function maps strings to numbers and these numbers
correspond to indices in an Array.
How to implement a Hash Table in JavaScript?
We will talk about 3 ways to implement a Hash Table in JS:
1. Using Object data type.
2. Using a Map Object.
3. Implement your own Hash Table.
1️⃣Using Object data type - simplest implementation
There are some downsides to this approach:
1. The Object comes with its own properties and methods. The problem here is JS doesn't block an attempt to overwrite these methods, which may cause an error.
2. The keys are limited to String or Symbol data type.
3. The size of Object is not tracked, you need to manually determine it.
2️⃣Using Map object
The Map object is created to implement Hash Table without downsides that appeared on basic Object.
Unlike Object:
• Maphave sizeproperty to track its contents.
• Keys can be any data type.
• You can't overwrite built-in properties/methods.
• You must use the set() and get() methods to define and retrieve data.
3️⃣Implement your own Hash Table
You'll probably never have to implement Hash Table yourself, But writing your own Hash Table implementation is one of the most common JS interview questions.
Alright, all method work as expected. Let's try another insertion:
😨!! When I call table.get('name'); it should retrieve ['name', 'Amr'], So why is it not working as expected!?
• hash() function uses ASCII code to convert key to an index. So if the keys are the same set of letters (name == mane) the index will be the same. And this will cause overwriting the previous value with the new one.
• This is called Collision and needs to be handled in our implementation.
How to Handle Collision?
Collision occurs when hash() function generate the same index for different keys.
There are 2 main ways to handle collision:
1. Separate Chaining
2. Open Addressing
Here we'll just learn Separate Chaining..
⏩ Handle Collision - Separate Chaining
If multiple keys map to the same index, start a new Array at this index.
Now, Let's improve our set() method to avoid collision:
Also, update get() method
and remove() method:
Now, as a bonus let's add a display() method:
Conclusion
You have learned what Hash Table is and different ways to implement it in JavaScript.
You've also learned how to implement your own Hash Table class as well as how to Handle Collisions.
You'll commonly use a Hash Table because of its fast search, insertion, and delete operations:
Main Resources
• Grokking Algorithms Book
• https://www.codecademy.com/resources/docs/javascript/hashtables
• https://www.youtube.com/watch?v=y3CcHKEM8r8
Top comments (0)