HASHING TECHNIQUE:

This technique is used for storing and retrieving the data from the database.

It is also known as mapping technique because, we try to save larger value at smaller values of index.

Hash Table:

Hash table is used to store data in a particular way. It is similar to array.

Hash Function:

Hash function is the function by which we calculate the index number, where we have to store a particular
data.

Need for Hash data structure:

Every day, the data on the internet is increasing multifold and it is always a struggle to
store this data efficiently. In day-to-day programming, this amount of data might not be that
big, but still, it needs to be stored, accessed, and processed easily and efficiently. A very
common data structure that is used for such a purpose is the Array data structure.

Now the question arises if Array was already there, what was the need for a new data
structure! The answer to this is in the word “efficiency“. Though storing in Array takes
O(1) time, searching in it takes at least O(log n) time. This time appears to be small, but for
a large data set, it can cause a lot of problems and this, in turn, makes the Array data
structure inefficient.

This is how Hashing data structure came into play. With the introduction of the Hash data
structure, it is now possible to easily store data in constant time and retrieve them in
constant time as well.

Components of Hashing
There are majorly three components of hashing:

1. Key: A Key can be anything string or integer which is fed as input in the
hash function.

2. Hash Function: The technique that determines an index or location for

storage of an item in a data structure.
 3. Hash Table: Hash table is a data structure that maps keys to values using
a special function called a hash function. Hash stores the data in an
associative manner in an array where each data value has its own unique
index.

Types of Hash functions:

There are many hash functions that use numeric or alphanumeric keys. Following
are the different hashing functions:

1. Division Method:

This is the most simple and easiest method to generate a hash value. The hash
function divides the value k by M and then uses the remainder obtained.

Formula:
 2. Mid Square Method:

The mid-square method is a very good hashing method. It involves two steps
to compute the hash value-
1. Square the value of the key k i.e. k 2
2. Extract the middle r digits as the hash value.

Formula:

The value of r can be decided based on the size of the table.

 Example:
Suppose the hash table has 100 memory locations. So r = 2 because two digits are
required to map the key to the memory location.

3. Folding Method:

It breaks up a key value into precise segments that are added to form a hash
value.

Explanation:
Example 1: The task is to fold the key 123456789 into a Hash Table of ten spaces (0
through 9).

 It is given that the key, say X is 123456789 and the table size (i.e., M =
10).
 Since it can break X into three parts in any order. Let’s divide it evenly.
 Therefore, a = 123, b = 456, c = 789.
 Now, H(x) = (a + b + c) mod M i.e., H(123456789) =(123 + 456 + 789)
mod 10 = 1368 mod 10 = 8.
 Hence, 123456789 is inserted into the table at address 8.

Collision Resolution:

When the two different values have the same value, then the problem occurs
between the two values, known as a collision. In the above example, the value is
stored at index 6. If the key value is 26, then the index would be:

h(26) = 26%10 = 6

Therefore, two values are stored at the same index, i.e., 6, and this leads to the
collision problem. To resolve these collisions, we have some techniques known as
collision resolution techniques.

These are:

1. Open Hashing
2. Closed Hashing

Open Hashing

In Open Hashing, one of the methods used to resolve the collision is known as a
chaining method.

In open hashing, each hash table slot, also known as a bucket, contains a linked list
of elements that hash to the same slot.
The term chaining is used to describe the process because the linked list is used,
which is like a chain of elements.
Closed Hashing:

Like open hashing, closed hashing is also a technique used for collision resolution in
hash tables. Unlike open hashing, where collisions are resolved by chaining elements
in separate chains, closed hashing aims to store all elements directly within the hash
table itself without the use of additional data structures like linked lists.

In closed hashing, when a collision occurs, and a hash slot is already occupied, the
algorithm probes for the next available slot in the hash table until an empty slot is
found.

Linear Probing

Linear probing is one of the forms of open addressing. As we know that each cell in
the hash table contains a key-value pair, so when the collision occurs by mapping a
new key to the cell already occupied by another key, then linear probing technique
searches for the closest free locations and adds a new key to that empty cell. In this
case, searching is performed sequentially, starting from the position where the
collision occurs till the empty cell is not found.

Let's understand the linear probing through an example.

Consider the above example for the linear probing:

A = 3, 2, 9, 6, 11, 13, 7, 12 where m = 10, and h(k) = 2k+3

The key values 3, 2, 9, 6 are stored at the indexes 9, 7, 1, 5 respectively. The

calculated index value of 11 is 5 which is already occupied by another key value, i.e.,
6. When linear probing is applied, the nearest empty cell to the index 5 is 6;
therefore, the value 11 will be added at the index 6.

The next key value is 13. The index value associated with this key value is 9 when
hash function is applied. The cell is already filled at index 9. When linear probing is
applied, the nearest empty cell to the index 9 is 0; therefore, the value 13 will be
added at the index 0.
Quadratic Probing:

Let hash(x) be the slot index computed using the hash function.

 If the slot hash(x) % S is full, then we try (hash(x) + 1*1) % S.

 If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S.
 If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S.
 This process is repeated for all the values of i until an empty slot is found

For example: Let us consider a simple hash function as “key mod 7” and sequence
of keys as 50, 700, 76, 85, 92, 73, 101
Double Hashing: