Hashing in Datastructures

Описание: Hashing in the data structure is a technique that is used to quickly identify a specific value within a given array. It works by creating a unique hash code for each element in the array and then stores the hash code in lieu of the actual element.

Types of Hashing
1. Division Method
The division method is the simplest and easiest method used to generate a hash value. In this hash function, the value of k is divided by M and uses the remainder as obtained.

Formula - h(K) = k mod M

(where k = key value and M = the size of the hash table)
2. Folding Method
There are two steps in this method -

The key-value k should be divided into a specific number of parts, such as k1, k2, k3,..., kn, each having the very same number of digits aside from the final component, which may have fewer digits than the remaining parts.
Add each component separately. The last carry, if any, is disregarded to determine the hash value.
Formula - k = k1, k2, k3, k4, ….., kn

s = k1+ k2 + k3 + k4 +….+ kn

h(K)= s

(Where, s = addition of the parts of key k)

Collision resolution technique:
1. Open hashing / separate chaining / closed addressing
2. Closed hashing / open addressing
2.1 Linear Probing
2.2 Quadratic Probing
2.3 Double Hashing