Hashing Technique

It is a searching technique .Let’s first start with why and how hashing technique came into consideration.

We had mainly 2 Searching techniques and they were :

1. Linear Search : With Time Complexity of O(n)
2. Non-Linear Search : With time complexity of O(logn)

(note: I will explain Time & Space Complexity in another Document.)

So, Linear search was taking a lot of time but then we found Non-linear way, which was good. In this case the time taken was small but there was a problem and the problem was “what if, we have a lot of values as now the small small time became a big time” .

So, the thought came what if the have the Time complexity O(1) — wow , great idea, but :( how to achieve it ?

This was the time when Hashing technique came in picture.

In general Hashing means conclusion or outcome but in Computer Science Hashing function means to convert one value into another.

We will go step by step progress — have patience to get a better understanding.

Stage 1.
If we have a list of elements and an array to store them then

Oh no , problem : a lot of empty place and what if I have a big integer value then do I need to create that big array ?

Stage 2.

Now let’s use hash table having hash index where h(x) = x

Again , it looks like stage1.

But don’t worry as the function can be divided into 2 type:

1. 1–1 (as shown in above figure)
2. Many -1

Stage 3.

let’s go for many to one type . Here our h(x)= x % size of hash table.

so, if size is 10 then it will look like :

Stage 4.

To solve the problem of collision we divided into :

1. Open hashing

• Chaining : here when 2 or more elements points at the same index then a linkedList is used at hash index

2. Closed hashing

• Linear probing : here no linkedList is used but if collision then that element will go to next empty index of the table which mean our hash function will be h(x)= [h(x) + f(i)] % size where f(i)= i
• Quadratic probing : it came in picture as while using linear probing as elements were in adjacent index , it looked very messy . So, in oder to avoid the clustering , the hash function became h(x)= [h(x) + f(i)] % size where f(i)= i²

You know now we achieved the time complexity as O(1)

Remember from stage 1 to stage 3 ,the time complexity improved but not O(1) but we did it in Closed hashing of stage 4.