Hashing is an approach to convert a larger key into a smaller integer value within a given limited range.
Here the key is a larger value that we need to store And the integer value is an address in the hash table where the key will be store.
To find integer address from key-value we have hashing function to calculate.
- Hashing technique is an efficient searching technique that minimizes the number of comparisons while performing the search.
- With the help of hashing, searching can be performed in a constant time O(1).
- It doesn’t depend upon the size of data, in all cases worst, best, and an average search performed in O(1).
- It is better than Linear search and binary search both where time complexity is O(n) and O(logn) respectively.
What is hash function?
- A hash function maps key value to a small integer value.
- A hash function takes a key as an input and after applying some logic returns a small integer value which is known as the hash value.
- This hash value represents the original key value.
- This hash value of the key is used as an index to store the key into the hash table.
Note: Here Key is a value that is taken as input. This key can be a string or integer.
What is hash value?
- Hash value is generated by the hash function.
- Hash value denotes where the key should store in the hash table.
- We can say that Hash value is the index value for the key.
What is hash table?
- Hash table in data structure is a data structure that stores key-value pairs.
- Hash table uses a hash function to compute an index to store key-value pairs.
- Each index of the hash table is known as slots.
Let’s see an example to understand hashing and hash table.
- The above figure shows a hash table and the size of the above hash table is 10.
- It means this hash table has 10 slots which are denoted by {0, 1,2,3,4,5,6,7,8,9}.
Now we have to insert value {12,56,33,65,71} into hashtable. So to calculate slot/index value to store items we will use hashing concept.
Where hash function will calculate this index value which is also known as the hash value.
Formula to calculate index / hash value
index/hash value = Key value % size of array
After computing hash values we can insert each value into the hash table.
Like if we have to insert 12 then
index/hash value = 12%10 = 2
So 12 will be inserted at index 2 of the hash table shown above.
Load factor
In the above example, only 5 slots are filled and the rest is empty in a hash table which is referred to as the load factor.
Load factor is denoted by lambda 𝜆
Formula to calculate load factor (𝜆) is
load factor(𝜆) = No. of items/table size.
= 5/10
Types of Hashing
- Open Hashing (Closed Addressing)
- Closed Hashing (Open Addressing)
This technique is used to minimize collision that occurs during hashing.
It is similar to collision resolution techniques.
[wpusb]