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:

1. In a data structure, the hash table is used to store key-value pairs.
2. The data items are stored in an array format in it, where each data value has its unique index value.
3. It is a collection of stored data items that you can easily search later.
4. In this, the hash function is used to compute the index of the array, from which you can find your desired value.
5. It has a list of the array where each list is called a bucket.
6. It contains the value based on the key.
7. The hash table is used to implement the map interface and extend the dictionary class.
8. 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:

1. Search operation
2. Delete operation
3. 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:

1. Mid Square Hash Function
2. 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² = 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:

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