Hashing Methods

These are the hashing methods:

1. Direct method
2. Modulo-division
3. Midsquare
4. Digit extraction
5. Rotation
6. Folding

Direct Method

In direct hashing the key is the address without any algorithmic manipulation.
Direct hashing is limited, but it can be very powerful because it guarantees that there are no synonyms and therefore no collision.

Example :

Modulo-division Method

• This is also known as division remainder method.
• This algorithm works with any list size, but a list size that is a prime number produces fewer collisions than other list sizes.
• The formula to calculate the address is:
  Address = key MODULO listsize + 1
  Where listsize is the number of elements in the arrary.

Example:
Given data
Keys are : 137456 214562 140145
137456 % 19 +1 = 11
214562 % 19 + 1 = 15
140145 % 19 + 1 = 2

Digit-extraction Method

• Using digit extraction selected digits are extracted from the key and used as the address.

Example:

• Using six-digit employee number to hash to a three digit address (000-999), we could select the first, third, and fourth digits( from the left) and use them as the address.

The keys are:
379452 -> 394
121267 -> 112
378845 -> 388

Folding Method
Two folding methods are used they are:

1. Fold shift
2. Fold boundary

     1. Fold Shift

• 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.

     2. Fold boundary

• In fold boundary the left and right numbers are folded on a fixed boundary between them. The two outside values are thus reversed.

Midsquare Method

• In midsquare hashing the key is squared and the address is selected from the middle of the square number.
• Limitation is the size of the key.

Example:
9452² = 89340304: address is 3403

Rotation Method

• Rotation method is generally not used by itself but rather is incorporated in combination with other hashing methods.
• It is most useful when keys are assigned serially.