Hash Table with Chaining

Hash table is a data structure that combines an array with a linked list. It takes the random access ability of an array and combines it with dynamism of linked list.

If implemented well we are basically taking all the advantages of both the data structure to get insertion,deletion and search in constant time.

Hash table is a combination of two things:

1. Hash function: it returns a positive integer that is called hash code.
2. An Array: it is capable of storing data of the type we want to store

The basic idea of hash table is we take our data and run that data through the hash function, so the data is processed and return a number (called hash code) and with that number we just store the data we want to store in the data structure.

But how can we define our hash function? There is no one particular way to define a hash function. There are lot of good and bad hash function. And as we’re trying to get the operation close to constant time we’ll have to implement good hash function.

A good hash function should have:

• Use only the data being hashed -> we don’t want to incorporate anything else other than the data
• Use all the data being hashed -> we want to use all of the data