Hash Function and Hashing with open addressing(Linear probing)

 Hash function and hashing with open addressing(Linear probing)

Hash function

Hash function is a function which when applied to the key produces an integer which can be used as an address in a hash table.A good hash function minimizes collisions by spreading the elements uniformly throughout the array.

Characteristic of a good hash function 

• The hash function uses all the input data.
• The hash function uniformly distributes the data across the entire set of possible hash values.
• The hash function generates very different hash values for similar strings.
• The hash value is fully determined by the data being hashed.

Hash functions are

• Division method.
• Multiplication method.

Hashing with open addressing

Open addressing all elements are stored in the hash table itself.That is each table entry contains either an element of the dynamic set or NIL.When searching for an element systematically examine table slots until the desired element is found or it is clear that the element is not in the table.The process of examining the locations in the hash table is called probing.

To perform insertion using open addressing successively examine or probe the hash table until find an empty slot in which to put the key.

Three techniques are commonly used to compute the probe sequences required for open addressing.

• Linear probing.
• Quadratic probing.
• Double hashing.

Linear probing

Linear probing uses hash function

h(k,i)=(h'(k)+i)mod m

Here m is the size of hash table.

Example

Consider inserting the key 26,37,59,76,65,86 into a hash table size m=11 using linear probing  and hash function is h'(k)=k mod m.

Solution

h(26,0)=[26 mod 11+0]mod 11

           =4 mod 11=4

Since T[4] is free insert key 26 at this place.

h(37,0)=[37 mod 11+0]mod 11

           =4 mod 11=4

Since T[4] is not free the next probe sequence is computed as

h(37,1)=[37 mod 11+1]mod 11

           =5 mod 11=5

T[5] is free insert key 37 at this place.

h(59,0)=[59 mod 11+0]mod 11

           =4 mod 11=4

T[4] is not free so the next probe sequence is computed as

h(59,1)=[59 mod 11+1]mod 11

           =5 mod 11=5

h(59,2)=[59 mod 11+2]mod 11

           =6 mod 11=6

T[6] is free insert key 59 at this place. 

h(76,0)=[76 mod 11+0]mod 11

           =10 mod 11=10

T[10] is free insert key at this place.

h(65,0)=[65 mod 11+0]mod 11

           =10 mod 11=10

T[10] is occupied the next probe sequence is computed as

h(65,1)=[65 mod 11+1]mod 11

           =11 mod 11=0

T[0] is free insert key 65 at this place.

h(86,0)=[86 mod 11+0]mod 11

           =9 mod 11=9

T[9] is free insert key 86 at this place.

Main disadvantage of linear probing is that records tend to cluster appear next to one another.When load factor  is greater than 50% such clustering increase the average time for a record.