Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.

Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the size of the data. Hash Table uses an array as a storage medium and uses hash technique to generate an index where an element is to be inserted or is to be located from.

Hash function

A hash function is any function that can be used to map a data set of an arbitrary size to a data set of a fixed size, which falls into the hash table. The values returned by a hash function are called hash values, hash codes, hash sums, or simply hashes.

Different Hashing Functions:

• Division Method: It is the most simple method of hashing an integer x. This method divides x by M and then uses the remainder obtained. In this case, the hash function can be given as h(x) = x mod M.

  The division method is quite good for just about any value of M and since it requires only a single division operation, the method works very fast. However, extra care should be taken to select a suitable value for M.

• Multiplication Method:

  This method has following steps:

  Step 1: Choose a constant A such that 0 < A < 1.

  Step 2: Multiply the key k by A.

  Step 3: Extract the fractional part of kA.

  Step 4: Multiply the result of Step 3 by the size of hash table (m).

  Hence, the hash function can be given as:

  h(k) = I m (kA mod 1) ˚

  where (kA mod 1) gives the fractional part of kA and m is the total number of indices in the hash table.

• Mid-Square Method:

  The mid-square method is a good hash function which works in two steps:

  Step 1: Square the value of the key. That is, find k2.

  Step 2: Extract the middle r digits of the result obtained in Step 1.

  The algorithm works well because most or all digits of the key value contribute to the result. This is because all the digits in the original key value contribute to produce the middle digits of the squared value.

  Therefore, the result is not dominated by the distribution of the bottom digit or the top digit of the original key value. In the mid-square method, the same r digits must be chosen from all the keys. Therefore, the hash function can be given as: h(k) = s where s is obtained by selecting r digits from k2.

• Folding Method: The folding method works in the following two steps:

  Step 1: Divide the key value into a number of parts. That is, divide k into parts k1, k2, ..., kn, where each part has the same number of digits except the last part which may have lesser digits than the other parts.

  Step 2: Add the individual parts. That is, obtain the sum of k1 + k2 + ... + kn. The hash value is produced by ignoring the last carry, if any.

Note that the number of digits in each part of the key will vary depending upon the size of the hash table. For example, if the hash table has a size of 1000, then there are 1000 locations in the hash table.

To address these 1000 locations, we need at least three digits; therefore, each part of the key must have three digits except the last part which may have lesser digits.