Different types of hash function:
1. Division Method
The hash function depends upon the remainder of divisor.
Typically divisor is table size.
If the record 43, 65 , 77 , 90 are to be inserted in a table of size 10
Then the hash function= record % table-size,
H(43) = 43 % 10 = 3
H(65) = 65 % 10 = 5
H(77) = 77 %10 = 7
H(90) = 90 %10 = 0
0 1 2 3 4 5 6 7 8 9
90 | 43 | 65 | 77 |
(hash-table)
Multiplicative hash function
Step-1 The multiplicative hash function works in following way
Multiply the key (say k) by a constant 'A' where 0<A<1,
then extract the fraction part of kA
Step-2 Multiply this fraction part by m and tak the floor.
The above steps can be formulated as
H(k) = [m {kA}].
Donald Knuth suggested to take A=0.61803398987.
Lets see one example
Key= 107 suppose m=50 and A=0.61803398987.
H(k) = [50 { 107 * 0.61803398987 }]
= [50 * { 66.12 } ]
= [50*0.12]
= 6
That means, 107 will be placed at position 6 .
Extraction
In this method some digit are extracted from the key to form address location in the hash table.
For example suppose 876902 is to be placed in hash table of size 1000.
And hash function says extract second, third and fifth digit from left
Then the address location is 760.
Mid square
This method works in following steps
Square the key
Extract middle part of the square. This will indicate he location of key in hash table.
Let key = 2119
(2119)2 = 44,90,161
For hash table of size 1000
H(key)= 901.
Folding
There are 2 folding technique
i) Fold shift
ii) Fold boundary
Fold shift : In this method , the key is divided into separate part whose size matches with the hash
table size. Then the left part and right part are shift with the middle part
For example : key= 345987132 is to hashed in table size 1000
345 | 987 | 132
Left middle right
H(key) = 345
+ 987
+ 132
______________
1 464
1 will be discarded and the H(key) = 464
Fold Boundary : in this method , the key is divided into separate part whose size matches with the
hash table size. Then the left part and right part are reversed and shifted
with the middle part
For example : key= 345987132 is to hashed in table size 1000
345 | 987 | 132
Left middle right
H(key) = 543 (reversed)
+ 987
+ 231 (reversed)
______________
1 761
1 will be discarded and the H(key) = 761.
Comments