Hashing is the application of a function to the key value that results in mapping the range of possible key values into a smaller range of relative addresses.
Choosing a hash function The two principal criteria in selecting a hash function are that it should be easy and quick to compute, and that it should achieve an even distribution of the keys that actually occur across the range of indices.

Direct hashing:
the key is the address without any algorithmic manipulation. The data structure must therefore contain an element for every possible key. While the situations where direct hasing are limited, when it can be used it is very powerful becasue it guarantees that there are no collisions. Limitations: Large key value.
Mid-Square (middle of Square):

9452 * 9452 = 89340304 = 3403 As a variation on the midsqaure method, we can select a portion of the key, such as the middle three digits, and then use them rather than the whole key. This allows the method to be used when the key is too large to square. 379452:
379 * 379 = 143641 = 364
121267:
121 * 121 = 014641 = 464

Modulo-Division :

Also known as Division-remainder. Address = Key MOD Table size While this algorithm works with any table size, a list size that is a prime number produces fewer collisions than other list sizes.
Folding There are two folding methods that are used, fold shift and fold boundary.
In fold shift, the key value is divided into parts whose size matches the size of the required address. Then the left and right parts are shifted and added with the middle part. In fold boundary, the left and right numbers are folded on a fixed boundary between them and the center number.

a. Fold Shift Key: 123456789
123
456
789
---
1368 ( 1 is discarded)
b. Fold Boundary Key: 123456789
321 (digit reversed)
456
987 (digit reversed)
---
1764 ( 1 is discarded)

SHARE

About df