# Hashing

**Hashing**: Hashing is a process in which a large amount of data is mapped to a small table with the help of hashing function. It is a searching technique.

### Hash table

We can understand the hash table better based on the following points:

- In a data structure, the hash table is used to store key-value pairs.
- The data items are stored in an array format in it, where each data value has its unique index value.
- It is a collection of stored data items that you can easily search later.
- In this, the hash function is used to compute the index of the array, from which you can find your desired value.
- It has a list of the array where each list is called a
**bucket**. - It contains the value based on the key.
- The hash table is used to implement the map interface and extend the dictionary class.
- The hash table is a synchronized table, and it contains unique elements only.

- The figure above shows the hash table whose size is n = 10. Each position of the hash table is called a slot. This hash table has not contained any item, so each slot is empty.

### Basic operations

There is the following type of basic operation in the hash table:

- Search operation
- Delete operation
- Insert operation

**Search operation:** The search operation is used to search a particular value in a hash table.

**Delete operation: **The delete operation is used to delete a particular value in a hash table.

**Insert operation: **The Insert operation is used to add particular value in a hash table.

### Hash function

The hash function is a type of function that is applied to a key from which an integer is obtained. This integer is used as the address of the hash table. This integer is called a **hash key**.

**Type of hash functions**

There are various types of hash functions in the data structure:

- Mid Square Hash Function
- Division Hash Function

### Division hash function

In this function, the hash function depends on the remainder of the division. If the list size is a prime number, there is less collision.

The formula of division hash function is h(k) = k mod n

Where** k** is **key**, and **n** is **list size**.

**For example:** Suppose we have this record (101, 103, 107, 109), and the table size is 10.

**Solution:** Record is (101, 103, 107, 109)

Table size is 10.

Put value in the formula h(k) = k mod n

1 = 101 mod 10

3 = 103 mod 10

7 = 107 mod 10

9 = 109 mod 10

### Mid square hash function

In this function, firstly hash function key is squared, and then the middle part of the square is selected as the index.

**For example:** Suppose we have this record 96.

96 = 96^{2 }= 9216 // middle part of the square is index address

The address of index is 21

### Characteristics of a good hash function

To get a good hashing mechanism, we need a good hash function. Therefore, we describe below the characteristic of a good hash function:

- The hash function should generate different hash values ??for the same type of string.
- A good hash function reduces the chance of collisions.
- It should be easy to compute.
- The hash function is perfect when it uses all input data.
- The hash function should generate such keys that are easy to distribute.