Hashing - A Searching Technique

Hashing is a Searching Technique. Using hashing, we can search and insert elements in O(1) time.

Why are we using Hashing?

Hashing is a technique to retrieve information in a secure and quick way. In hashing, we define a method to store and retrieve the information in the system. Suppose we have an array of elements with a limited range, we store these elements in the array in such a way that we can search/find the element in O(1) time when it is required.

Direct Addressing Table (DAT)

Direct addressing table is the simple and trivial hashing technique.
In Direct Addressing Table, the key itself is its address/index in the array.
In Direct Addressing Table, we do not do any calculation to find the index of elements.

Example: Suppose, if we have elements [9, 3, 5, 1, 8, 0] which we want to store in a hash table, then the hash table would look like this...

Drawbacks of Direct Addressing Table

Even though the number of keys (elements) is very less, and one of the keys is very large, suppose 2^1000, we need a hash table of size 2^1000, which means for less number of keys we need a very large table (more space) to store all the elements. This approach will drastically waste memory.

To tackle the above drawback, the Hash Function is introduced.

What is Hash Function?

The hash function is a function, which does some calculation and maps elements to fixed-size values. The values returned by a hash function are called hash values. The values are usually used as an index for elements to store in a fixed-size table (Hash Table).

There are various methods to calculate the hash values or indexes. Some of the Hash function types are given below.