Hashing is a process of converting data into a fixed-length string of characters, which is typically a hexadecimal or binary representation. This fixed-length string is commonly known as a "hash value" or "hash code."
Components of hash
It consists of key components,
Key: It refers to the text that we want to hash.
Hash function: A hash function (H(x)) is a mathematical algorithm that takes the key as input and produces a fixed-length hash value as output
H(x)= x mod 7
where x is the key that we want to hash.
In this example , hash function we have taken 7 because we limit the hashtable size to 7. We can also modify the value as per our needs.
Hash Table: A Hash table is a data structure that maps keys to values using a hash function. Hash stores the data in an array where each data value has its unique index.
Why do we need hash?
In programming to insert, search, and delete data we have data structures like,
Array
In the array, the time complexity for insertion ,deletion and search takes O(n). But if we can reduce the time to O(log n) by search an element in a sorted order by binary search but then insertion and deletion becomes costly.
Linked Lists
This also takes linear time complexity.
Binary Search Tree
This takes logarithmic time in insertion ,deletion ,and search.
Hash
This takes constant time for every operations.
So this will increase the efficiency of the program and retrieve information in no time.
Collision
Collision is a situation in which where two keys having same hash values.
For example,
H(x)= x mod 7
H(13)= 13 mod 7 => 6
H(20)= 20 mod 7 => 6
So the program don't know where to store the second hash value.
This will lead to collision.
Collision Handling Techniques
Handling hash collisions is essential in hash tables, where each key needs to be mapped to a unique location within the table. Several techniques are commonly used to address hash collisions.
Chaining
This make each cell of the hash table point to a linked list of records that have the same hash function value. Chaining requires additional memory outside the table.
For example,
We have some elements like 14,21,49,50. Our hash function is
H(x) = x mod 7
H(14) = 14 mod 7 => 0
H(21) = 21 mod 7 => 0
H(49) = 49 mod 7 => 0
In 0th position of the hash table the values are stored like,
14 -> 21 -> 49
From this we clearly see that there is a collision that three key have the same hash value so the value can be stored using linked lists to store the series of values having same hash value.
Open Addressing
All elements are stored in the hash table itself. Each table entry contains either a record or NIL.
This is of three types,
Linear probing
Quadratic probing
Double probing
For example,
We have the same elements 14,21,49,50. Our hash function is
H(x) = x mod 7
H(14) = 14 mod 7 => 0
H(21) = 21 mod 7 => 0
Here the value of 14 is stored in 0th position and 21 can be stored in 1th position.
Top comments (0)