Hash Tables

Hashing is an efficient way to sort key values in memory. Hashing is used to get the values associated with the key very fast. Some examples of hash tables are:

• Employee ID, which is used to extract all the records of an employee.

• Stock ID, which is used to get the transaction of stock during the day/week/month.

• Book ISBN number, which is used to extract author, pages, price, and other relevant information.

As we can see in the above examples, keys can go to a large number, and each are unique. The value associated with the key needs to be extracted fast. Hash tables do this work.

In general, the key can be of any type. They need not be a sequential integer. To handle this, a hash function is used that takes a key and converts it to a more efficient key. This new key can be stored in a sorted way and information is extracted in O(1) time. The hash function suggests which index to go for any key. Values returned by the hash function are known as hash codes, hash sums, or hashes.

It could be possible that different keys map to the same hash. In that scenario, we would use the collision resolution technique.

Consider this hash function:

hash(key):
{
return key%1000
}

Now, hash codes for these keys will be as follows:

• $1458562->ha$

...