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.
![Hashing](https://www.tutorialandexample.com/wp-content/uploads/2020/10/image-112.png)
- 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
![Hashing](https://www.tutorialandexample.com/wp-content/uploads/2020/10/image-113.png)
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 = 962 = 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.