Data Structures and Algorithms (Hash Function)- Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

 

What are the characteristics of a good hash function?

There are multiple ways for constructing a hash function. Remember that hash function takes the data as input (often a string), and return s an integer in the range of possible indices into the hash table.

Characteristics of a Good Hash Function

 

There are four main characteristics of a good hash function:

1) The hash value is fully determined by the data being hashed.

2) The hash function uses all the input data.

3) The hash function "uniformly" distributes the data across the entire set of possible hash values.

4) The hash function generates very different hash values for similar strings.

Let's examine why each of these is important:

Rule 1: If something else besides the input data is used to determine the hash, then the hash value is not as dependent upon the input data, thus allowing for a worse distribution of the hash values.

Rule 2: If the hash function doesn't use all the input data, then slight variations to the input data would cause an inappropriate number of similar hash values resulting in too many collisions.

Rule 3: If the hash function does not uniformly distribute the data across the entire set of possible hash values, a large number of collisions will result, cutting down on the efficiency of the hash table.

Rule 4: In real world applications, many data sets contain very similar data elements. We would like these data elements to still be distributable over a hash table.

 

Demonstrate the insertion of the keys 5, 28, 15, 20, 33, 12, 17, 32 into a hash table with collisions resolved by linear probing. Let the table have 9 slots, with the starting index 0. Let the hash function be h(k) = k mod 9

 

Let the first key get inserted

h(k) = 5 mod 9 = 5

Hash Function	Key Insertion
0
1
2
3
4
5	5
6
7
8

 

Let the second key get inserted

 

h(k) = 28 mod 9 = 1

Hash Function	Key Insertion
0
1	28
2
3
4
5	5
6
7
8

 

Let the third key get inserted

h(k) = 15 mod 9 = 6

Hash Function	Key Insertion
0
1	28
2
3
4
5	5
6	15
7
8

 

Let the fourth key get inserted

h(k) = 20 mod 9 = 2

Hash Function	Key Insertion
0
1	28
2	20
3
4
5	5
6	15
7
8

 

Let the fifth key get inserted

h(k) = 33 mod 9 = 2

 

Hash Function	Key Insertion
0
1	28
2	20
3
4
5	5
6	15
7	33
8

 

Let the sixth key get inserted

h(k) = 12 mod 9 = 2

 

Hash Function	Key Insertion
0
1	28
2	20
3	12
4
5	5
6	15
7	33
8

 

 

 

Let the seventh key get inserted

h(k) = 17 mod 9 = 8

 

Hash Function	Key Insertion
0
1	28
2	20
3	12
4
5	5
6	15
7	33
8	17

 

Let the eighth key get inserted

h(k) = 32 mod 9 = 8

Hash Function	Key Insertion
0	32
1	28
2	20
3	12
4
5	5
6	15
7	33
8	17

 

This is a case of collision:

It will go to 0 by linear probing

Tirthankar Pal

MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview

2 year PGDM (E-Business) from Welingkar, Mumbai

4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology

Google and Hubspot Certification

Brain Bench Certification in C++, VC++, Data Structure and Project Management

10 years of Experience in Software Development out of that 6 years 8 months in Wipro

Selected in Six World Class UK Universities:-

King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds