Hash Tables

Hamza Javed

In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Why we use a hash table?

let’s say we have an array of 10 elements, and we need to find something from that array. It’s easy we can just iterate through the array and find the element. There’s nothing wrong with that approach. In fact, it’s a good approach if it’s a small array. But, What if we have an array of size thousand or hundred thousand then its iterating through a whole array and checking every single element is not a good approach. It becomes very time-consuming.

Now let’s imagine if you know the value of that index number where that element is at. we can just use the index number to find the element and it becomes so much faster because we don’t have to go through each element of the array. Finding an element of the array with its index number is independent of the array’s size and its position in an array.

But how would we know the index of each element of that an array or the index of what you looking for? One way to solve this is to use the value it-self as the index number of the array. So every index number is related to its value. But how would we do?

One way is to find the ASCII code value of the element and divide it to the size of the array and put that element on the remainder. So the remainder will be the index number of that value.

for example, if the value is “Tom” and the size of the array is 10

T + o + m /size of array => ( 84+111+109 ) / 10 => 304 /10 => 30.4 (remainder is 4)

so put Tom in index 4. Now we can access it faster. And if we need to find Tom in the array we can get the ASCII of Tom and mod (length of the array)

Tom = 30.4%10 => remainder is 4 => array[4] => Tom

This technique makes the search results so much faster. and if there are more values in that index we can use Tom as the key and the other values as its value.

Collision

Let’s say we populate an array using the above approach but keys have the same values or the land on the same index number. We can’t put two different values on the same index. When that happens its called collision.

Linear probing

To solve this we simply put the value on the next available index.

In that picture, Mia and Sue have the same index value so we put Sue on the next index which is occupied because of Zoe so its looks for the next empty index which is 6 and when it comes to finding it, we can do a linear search after the index number. One way to avoid it is to make a bigger array than needed. Like only 75% of the array is ever occupied. This approach is called Linear probing.

Chaining

The other way to deal with it is by chinging. We use a linked list to point to the next element of that array which lands on the same index

Each slot of the array contains a link to a singly-linked list containing key-value pairs with the same hash. New key-value pairs are added to the end of the list. Lookup algorithm searches through the list to find matching key. Initially, table slots contain nulls. List is being created, when a value with the certain hash is added for the first time.

Hamza Javed

Written by

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade