Hashing Functions with Example
Characteristics of a Good Hash Function
- A good hash function avoids collisions.
- Moreover, A good hash function tends to spread keys evenly in the array.
- A good hash function is easy to compute.
Different Hashing Functions with Example
- Midsquare Methods
- Folding Method
- Digit Analysis
- Length-Dependent Method
- Algebraic Coding
- Multiplicative Hashing
- In this method, we use the modular arithmetic system to divide the key value by some integer divisor m (maybe table size).
- It gives us the location value, where the element can be placed.
- We can write, L = (K mod m) + 1
- where L => location in table/file K => key value m => table size/number of slots in file
- Suppose, k = 23, m = 10 then
- L = (23 mod 10) + 1= 3 + 1=4, The key whose value is 23 is placed in 4th location.
- In this case, we square the value of a key and take the number of digits required to form an address, from the middle position of squared value.
- Suppose a key value is 16, then its square is 256. Now if we want the address of two digits, then you select the address as 56 (i.e. two digits starting from the middle of 256).
- Most machines have a small number of primitive data types for which there are arithmetic instructions.
- Frequently key to users will not fit easily into one of these data types
- Moreover, It is not possible to discard the portion of the key that does not fit into such an arithmetic data type
- The solution is to combine the various parts of the key in such a way that all parts of the key effect for the final result such an operation is termed folding of the key.
- That is the key actually partitioned into the number of parts, each part having the same length as that of the required address.
- Also, Add the value of each part, ignoring the final carry to get the required address.
- So, This is done in two ways :
- Fold-shifting: Here actual values of each part of the key are added.
- Suppose, the key: 12345678, and the required address is of two digits, Then break the key into 12, 34, 56, 78.
- Moreover, Add these, we get 12 + 34 + 56 + 78: 180, ignore first 1 we get 80 as location
- Fold-boundary: Here the reversed values of outer parts of the key are added. Suppose, the key is: 12345678, and the required address two digits,
- Also, Then break the key into 21, 34, 56, 87.
- Add these, we get 21 + 34 + 56 + 87 : 198, ignore first 1 we get 98 as location
- This hashing function is a distribution-dependent.
- Here we make a statistical analysis of digits of the key and select those digits (of fixed position) which occur quite frequently.
- Then reverse or shifts the digits to get the address.
- For example, if the key is: 9861234. Moreover, If the statistical analysis has revealed the fact that the third and fifth position digits occur quite frequently, then we choose the digits in these positions from the key. So we get, 62. Reversing it we get 26 to the address.
- In this type of hashing function, we use the length of the key along with some portion of the key j to produce the address, directly.
- Also, In the indirect method, the length of the key along with some portion of the key used to obtain intermediate value.
- Here n-bit key value represented as a polynomial.
- The divisor polynomial then constructed based on the address range required.
- Moreover, The modular division of key-polynomial by divisor polynomial, to get the address-polynomial.
- Let f(x) = polynomial of n bit key = a1 + a2x + ……. + anxn-1
- d(x) = divisor polynomial = x1 + d1 + d2x + …. + d1x1-1
- then the required address polynomial will be f(x) mod d(x)
- This method is based on obtaining an address of a key, based on the multiplication value.
- Also, If k is the non-negative key, and a constant c, (0<c<1), compute kc mod 1, which is a fractional part of kc.
- Multiply this fractional part by m and take a floor value to get the address
- 0<h (k)<m