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.

- Division Modulo Method
- Mid Square Method
- Digit Extraction Method
- Folding Method

We will continue our discussion on the above-mentioned hashing methods. Stay motivated and keep learning with DigitalBitHub.