Hashing in data structure with its types

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.

hashing in data structure
  • 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.

hash table in data structure

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

  1. Open Hashing (Closed Addressing)
  2. Closed Hashing (Open Addressing)

This technique is used to minimize collision that occurs during hashing.

It is similar to collision resolution techniques.