DS with JS — Hash Tables— I

Data Structures with JavaScript — Chapter Four — Hash tables — I

Gaurav Mehla
Apr 21, 2018 · 6 min read

Hash tables is a data structure in which every value is associated with a key and we can find that key using hash function.

⚠️ Read more about the basics of Hashing and Hash tables. Click here

Prerequisites

Before proceeding further, make sure you have gone through both of these posts first because we will use Linked-Lists in

  1. DS with JS — Linked Lists
  2. DS with JS — Linked Lists — II

❗️All the code snippets you will see below are just Pseudo code. If you want to see working code — click here

Lets’ begin!!

Core

⚜️ The list

  1. Put
  2. Remove
  3. Search
  4. Size
  5. IsEmpty
Initial Hash table

🔅 Put

(  ) 
key .computeHash( item )
!.table[key] this.table[key] item ;
Put Operation

🔅 Remove

(  ) 
key .computeHash( item )
.table[key]
Remove Operation

🔅 Search & Size

(  ) 
key .computeHash( item )
this.table[key] item
()
counter 0;
( i0, len .table.length; i len; i) {
( .table[i] ) { counter }
}
counter;

❗️The technique which I am using to find out size is very time consuming. This is one way but the better one will be to use a counter for size. Just increment that counter whenever we put an item in Hash table and decrement it when we delete an item. Just return that counter in the size function so that we do not have to iterate over whole Hash Table very time we call it ( Some geek pointed this on reddit thread… thank you) and

I am still using this because you can use this piece of code for a lot of other things i.e you can use this to traverse over whole Hash Table and implement a function ( may be by some reason you want every value to be in a lowercase or uppercase) over each item which will help you do a lot of other things when you are practicing this. So, this code is just to show that this is one way to do this but as I mentioned that this is not one of the best way to this sort of work. Use pointers instead.

Search & Size Operation

🔅 IsEmpty

() 
( i0, len .table.length; i len; i) {
( .table[i] ) { };
}

IsEmpty Operation

It’s just the beginning with hash tables…

Let us see the real issue with Hash Functions —

In the example above, I am using a very simple Hash Function which is —

(  ) 
H .findPrime( .table.length )
total 0;
( i 0; i string.length; i) {
total H total string.charCodeAt(i)
}
total table.length

⚠️ In the function above, I am using a prime number. I know a lot of you are scratching their heads that why I used this. Well, it is playing a great role here.

There are a lot of ways you can design your own Hash Functions but no matter how complex you make you Hash Function but there is always high possibility that they will face one issue and that is —

🤜 Hash Table Collisions 🤛

…means when Hash Function returns same hash for more than one values.

️⚠️ Click here to read more about Hash Table Collision…

There are various solutions to this problem —

but in this post, we will go through one of major of them — .

Hash Tables — Separate Chaining Method

In this method, the hash table will contain links to linked-lists and we will search and insert the item by iterating over these linked-lists.

Core

⚜️ The list

  1. Put
  2. Remove
  3. Contains
  4. Size
  5. IsEmpty
  6. Traverse

Lets write some lines of code now.. 🤓

Hash Table before all operations

🔅 Put

(  ) 
key .computeHash( item )
node Node(item)
( .table[key] ) {
node.next .table[key]
}
.table[key] node
Put Operation

🔅 Remove

(  ) 
key = .computeHash( item )
( .table[key] ) {
( .table[key].data item ) {
.table[key] .table[key].next
} {
current .table[key].next
prev .table[key]
( current ) {
( current.data item ) {
prev.next current.next
}
prev current
current current.next
}
}
}
Deletion in Separate Chaining Method — algs4.cs.princeton.edu
Remove Operation

🔅 Contains

( item ) 
( i0; ithis.table.length; i){
( .table[i] ) {
current .table[i];
( current ) {
( current.data item ) {
;
}
current current.next;
}
}
}
;
Contains Opeartion

🔅 Size & IsEmpty

(  ) 
counter 0
( i0; i.table.length; i){
( .table[i] ) {
current = .table[i]
( current ) {
counter
current current.next
}
}
}
counter
()
.size() 1
Size & IsEmpty Operation

🔅 Traverse

(  ) 
( i0; i.table.length; i){
( .table[i] ) {
current = .table[i];
( current ) {
fn( current );
current current.next;
}
}
}
Traverse Operation

Practice

Last most important thing..

That’s It

About this post

This post is the fourth instalment to its series “”. If you haven’t gone through them click here. The rest of the hashing will be covered in the next post.

There will be more in this series. Next will be on .

Happy Coding !!

🎧 Listening to The Wolf & The Moon… Excellent music.. Soulful…

If you like this article, please give it some claps 👏 and share it! If you do not like this post or have any type of questions regarding anything that i mentioned in this post. Feel free to ask me. Just post an issue in my “by clicking here.

For more like this, follow me on Medium or Twitter. To ask a Question visit this link. More about me on my website.

_devblogs

Stories for Full-Stack Web developers which help them in…

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store