Hashing, Hash table, hash function, collision and collision resolution technique

Rumman Ansari   2017-10-19   Student   Data structure > Hashing   6084 Share

What is Hashing?

hashing is a technique for performing almost constant time in case of insertion deletion and find operation.

Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects.

Mapping key must be simple to compute and must help in identifying the associated records.

Function that help us in generating such type of keys is termed as Hash Function.

Need of Hashing

Hashing is the process of mapping large amount of data item to a smaller table with the help of a hashing function. The essence of hashing is to facilitate the next level searching method when compared with the linear or binary search. The advantage of this searching method is its efficiency to hand vast amount of data items in a given collection (i.e. collection size). Due to this hashing process, the result is a Hash data structure that can store or retrieve data items in an average time disregard to the collection size.

Hash Table

Hash table support on eof the most efficient type of searching. Fundamentally a hash table consists of an array in which data is accessed via a special index caled key.

Application of Hash table

  • Database system
  • Symbol table in compiler
  • Tagged buffer etc.

Hash Function

Hash function is a function which is applied to the key produce an int which can be used as an aggress in a hash table.

Perfect hash function produces no collision. Good hash function minimize collision by seperating the elements uniformly throughout the array.

Examples of Hashing Technique or Hashing Collision Resolution Technique

  • Hashing With Channing or Separate Chaining
Open Addressing
  • Linear Porbing
  • Quadratic Probing
  • Double Hashing
Hashing Name Hash Function
Hashing With Channing h(k)=k mod n
Linear Probing h(k,i)= (h'(k)+i)mod m
h'(k) = k mod m
Quadratic Probing h(k,i)= (h'(k)+C1i +C2i2)mod m
h'(k) = k mod m
C1 and C2 are constant
Double Hashing h(k,i)= (h1(k)+ i.h2(k))mod m
h1(k) = k mod m
h2(k) = k mod m'
Here m' is slightly lesser than m (sy (m-1) or (m-2))

Problem 1

Conside the following insertion of element 5, 28, 19, 15, 20, 33, 12, 17, 10 into a chained hash table. The hash table has nine slots and function being h(k) = k mod 9.

Solution

Step 1: Insert 5:   h(5) = 5 mod 9 = 5
Step 2: Insert 28: h(28) = 28 mod 9 = 1
Step 3: Insert 19: h(19) = 19 mod 9 = 1
Step 4: Insert 15: h(15) = 15 mod 9 = 6
Step 5: Insert 20: h(20) = 20 mod 9 = 2
Step 6: Insert 33: h(33) = 33 mod 9 = 6
Step 7: Insert 12: h(12) = 12 mod 9 = 3
Step 8: Insert 17: h(17) = 17 mod 9 = 8
Step 9: Insert 10: h(10) = 10 mod 9 = 1

Final Solution:

View Solution Step by Step

Problem 2

Conside the following keys 26, 37, 59, 76, 65, 86 inta a gash table of size m=11 using linear probing, consider the primary hash function h'(k) = k mod m

Problem 3

Consider insertion the keys 20, 12, 31, 4, 25, 28, 27, 88, 69 into a hash table of length m=11, hashing open addressing with the primary hash function hj(k) = k mod m . Illustrate the result of inserting keys using double hashing with h2(k) = 1+ ( k mod (m-1)).

Share this Post: