Hash Table
The Fastest technique for searching..
Why do we need hashing?
- Efficient Data Retrival
Speed: Hashing provides the fastest way to search for data stored in the hash table. It provides a hash function that determines an index where the particular piece of data is stored.
Large Datasets: The efficiency is more important when it comes to larger datasets, because it avoids traversing whole lists or arrays.
2. Data Storage and Organization
Hash Tables: Hashing is fundamental to hash tables, a data structure that maps keys to values.
Key value pairs: A Hash table stores data in the form of key-value pairs, where the key is used to locate the value in the table.
Structured Storage: Hashing helps organize data in a structured manner, making it easier to manage and access.
Hashing in data structures is crucial for efficient data retrieval and storage, particularly in hash tables, which allow us fast access to data using its key, very useful for large datasets
It is useful for searching and is much faster than other methods. It searches in less than logn time.
If keys are sorted, then we can use binary search, but when keys are not sorted, then we have to use a hashing method.
For hashing, insert the keys in an Array (hash table) at the corresponding index, like key 2 will be placed at index 2, index and key same, during searching you can access the value using the kay in constant time O(1).
Drawback: Huge memory is required because of the given key when it is larger than we need a larger array size space therefore if we take that extra large size array then we can’t use it completely therefore it gets wasted, because we are keeping the key at the same index as the key, so for a larger key, we have to have that index in an array as well.
To solve this problem, we will use a mathematical model, known as a hash function.
Ideal Hash Function
h(x) = x
We will pass our key to this hash function h(x), this will give us an index (x), at that index we are going to store our key, you can understand by looking at the figure below.
Here we have a key space which contains all our keys and the Hash Table (array).
Keys should be mapped on a hash table, just like domain and range; mapping is like a relationship or function.
One-one and many-one are called functions.
We are using a hash function, that hash function will give us an index, and that index we will store our key.
Drawbacks: Space is huge and wasted in ideal hashing; here, the hash function is responsible for the drawback.
Modulus Hash Function
h(x) = x % 10
This hash function will never give you a value/index greater than 9, because it is a modulus hash function, it will give you the value from 0 to 9, therefore we do not need a space of more than 10, here we have an edge for using less space and do not let is waste. So at that index, we will store our key.
Drawback: Let’s say we have a key 33, now pass it to the hash function, then we get 3. At index 3, there is already a key present; the collision occurred.
Solving the collision problem
There are a few techniques used to solve the collision problem
Open Hashing
We will consume extra space beyond this hash table we will take more space using method chaining.
Channing
It comes under open hashing, used for collision resolution.
Here, the hash table index contains a pointer to a node, and the key will be kept there. If a collision occurs, then the node will be extended by creating a new Node and the key will be placed there.
Here keys must be placed in sorted order in the nodes.
Search: pass the key to the modulus function, which will give us an index, then at that index we have a pointer to a node, go to the linked list and search there for the key.
Get Owais Ahmad’s stories in your inbox
Join Medium for free to get updates from this writer.
Loading factor: Number keys divided by size, it is represented by lambda
λ = n/size of hash table
Analysis of hashing is always based on the loading factor.
e.g => keys = 100, hash table = 10, λ= 100/10 = 10
It means that at each location, there are 10 keys.
Analysis:
a. Successful search, Average case
time = 1+ λ/2, 1 is for modulus function and λ/2 is for searching in the linkedlist
b. Average unsuccessful search
time = 1 + λ
Search: same as searching in a linked list and deleting.
Note! Choose a hash function that uniformly distributes the keys, and then we can use the loading factor λ for analysis.
2. Closed Hashing
We will only utilize the given hash table. If a collision occurs, then use the next free space in the hash table, which uses Open addressing. In open addressing, we have three techniques: Linear probing, Quadratic probing, and Double hashing.
Linear probing
It comes under closed hashing.
h(x)= ( h(x) + f(i) ) % 10 , where f(i) = i, 0,1…..n
Here, when a collision occurs, it tries to store the key in the next free space. The next free space will be checked using the above formula, as we checked free space to store key 33, we probe linearly until we get a free space.
Search: The same function will be used for searching. When a key is being searched, use the hash function to go to the index. If it is not equal to the key, go to the next location and continue until found. If the next location is empty, then stop searching. An empty place means the element is not there.
Analysis:
Average successful search
t = 1/λ ln(1/1-λ)
Average unsuccessful search
t = 1/1-λ
Drawbacks:
. Keeping half of the hash table vacant
. Primary clustering of keys, that is group of keys together at one place.
Quadratic probing
h`(h(x) + f(i) ) % 10, where f(i) = i²
The next position is found using the quadratic value. Here we will take the value of i in squares in every iteration.
Average successful search
loge^(1–λ)/λ
Average unsuccessful search
1/1-λ
Double hashing
In this collision resolution technique, we use two hash functions to compute 2 different values for a given key. The first function will be used to compute the initial hash value, and the second function is used to compute the step size for the probing sequence.
The advantage of double hashing is that it is one of the best forms of probing, it uniformly distributes records across the hash table.
Hashfunction 1: h1(x) = x % 10
Hash function 2: h2(x) =R — ( x % R ), R is a prime number, smaller than the size of the hash table.
h`(x) = ( h1(x) + i * h2(x) ) %10
Happy Learning! 😊
