Friday, 10 November 2017

Hashing in Data Structure

Hash function is a mathematical formula which when applied to a key, produces an integer which can be used as an index for the key in the hash table. Hash table is a data structure in which keys are mapped to array positions by a hash function. The main aim of the hash function is that elements should be relatively, randomly and uniformaily distributed. It produces aunique set of integers within some suitable range in order to reduce the number of collisions. In practice, there is no hash function that eliminates collisions completely. So a good hash function only minimize the number of collisions by spreading the elements uniformaily throughtout the array.

Different hash functions:
1. Division Method
2. Multiplication Method
3. Mid-Square Method
4. Folding Method

Different Collision resolution methods:
1. Open Addressing
   1.1 Linear Probing
   1.2 Quadratic Probing
   1.3 Double Hashing
2. Chaining 
   2.1 Chained Hash Table
   2.2 Bucket Hashing

Mukesh Rajput

No comments:

Post a Comment

Mukesh Rajput