The hash function is a function that uses the constant-time operation to store and retrieve the value from the hash table, which is applied on the keys as integers and this is used as the address for values in the hash table.In a hash table, a new index is processed using the keys. And, the element corresponding to that key is stored in the index. This process is called the hashing(hash function).

The types of hash functions are explained below:

In this method, the hash function is dependent upon the remainder of a division.

Example:- elements to be placed in a hash table are 42,78,89,64 and let’s take table size as 10.

The table representation can be seen as below:

In this method, the middle part of the squared element is taken as the index.

Element to be placed in the hash table are 210, 350, 99, 890 and the size of the table be 100.

210* 210 = 44100, index = 1 as the middle part of the result (44100) is 1.

350* 350 = 122500, index = 25 as the middle part of the result (122500) is 25.

99* 99 = 9801, index = 80 as the middle part of the result (9801) is 80.

890* 890 = 792100, index = 21 as the middle part of the result (792100) is 21.

In this method the element to be placed in the table uh is a sing hash key, which is obtained by dividing the elements into various parts and then combining the parts by performing some simple mathematical operations.

Elements to be placed are 23576623, 34687734.

In these types of hashing suppose we have numbers from 1- 100 and the size of hash table =10. Elements = 23, 12, 32

From the above example notice that both elements 12 and 32 point to 2nd place in the table, where it is not possible to write both at the same place such a problem is known as a collision. To avoid this kind of problem there are some techniques of hash functions that can be used.

When the hash function generates the same index for multiple keys, there will be a conflict (what value to be stored in that index). This is called a hash collision.

We can resolve the hash collision using one of the following techniques.

Open Addressing: Linear/Quadratic Probing and Double Hashing

This method as the name suggests provides a chain of boxes for the record in the table having two entries of elements. So whenever such collisions occur then the boxes act as a linked list will be formed.

This is another method for solving collision problems. As the name says whenever a collision occurs then two elements should be placed on the same entry in the table, but by this method, we can search for the next space or entry in the table and place the second element. This can again lead to another problem; if we do not find any empty entry in the table then it leads to clustering. Thus this is known as a clustering problem, which can be solved by the following method.

In this diagram 12 and 32 can be placed in the same entry with index 2 but by this method, they are placed linearly.

This method is a resolution for the clustering problem during linear probing. In this method the hash function with hash key is calculated as hash (key) = (hash (key) + x * x) % size of the table (where x =0, 1, 2 …).

We will learn about Hash functions in this blog post. We will see all of its types and a brief description of each type. We will also learn about Hash collision in this blog post.

hash function

Trending Blogposts on hash function

Complete review of Hash function :Types of Hash function

Popular Discussions on hash function

PRODUCTS

QUICK LINKS

LEGAL

hash function

Trending Blogposts on hash function

Complete review of Hash function :Types of Hash function

Popular Discussions on hash function