Hashing with open addressing with Quadratic probing

 

Hashing with open addressing Quadratic probing and double hashing

In 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 advantage of open addressing is that it avoids pointers altogether.

The process of examining the locations in the hash table is called probing.

Quadratic probing

In quadratic probing later positions probed are offset by amounts that depend in a quadratic manner on the probe number i.This method works much better than linear probing.

Quadratic probing uses a hash function of the form

h(k,i)=(h'(k)+C₁i+C₂i²)mod m

Example

Consider inserting the keys 76,26,37,59,21,65 into a hash table of size m=11 using quadratic probing with  C₁=1 and C₂=3.The primary hash function is h'(k)=k mod m.

Solution

Quadratic probing uses a hash function of the form

h(k,i)=(h'(k)+C₁i+C₂i²)mod m

Here C₁=1 and C₂=3

h(k,i)=(k mod m+i+3i²)mod m

Insert 76

h(76,0)=(76 mod 11+0+3*0)mod 11

            =(10+0+0)mod11=10

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

Insert 26

h(26,0)=(26 mod 11+0+3*0)mod 11

            =(4+0+0)mod11=4

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

Insert 37

h(37,0)=(37 mod 11+0+3*0)mod 11

            =(4+0+0)mod11=4

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

h(37,1)=(37 mod 11+1+3*1²)mod 11

            =(4+1+3)mod11

            =8 mod 11=8

T[8] is free,insert the key 37 at this place.

Insert 59

h(59,0)=(59 mod 11+0+3*0)mod 11

            =(4+0+0)mod11=4

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

h(59,1)=(59 mod 11+1+3*1²)mod 11

            =(4+1+3)mod11

            =8 mod 11=8

T[8] is  not free,so next probe sequence is computed as

h(59,2)=(59 mod 11+2+3*2²)mod 11

            =(4+2+12)mod11

            =18 mod 11=7

T[7] is free,insert the key 59 at this place.

Insert 21

h(21,0)=(21 mod 11+0+3*0)mod 11

            =(10+0+0)mod11=10

T[10] is  not free,so next probe sequence is computed as

h(21,1)=(21 mod 11+1+3*1²)mod 11

            =(10+1+3)mod11

            =14 mod 11=3

T[3] is free,insert the key 21 at this place.

Insert 65

h(65,0)=(65 mod 11+0+3*0)mod 11

            =(10+0+0)mod11=10

T[10] is  not free,so next probe sequence is computed as

h(65,1)=(65 mod 11+1+3*1²)mod 11

            =(10+1+3)mod11

            =14 mod 11=3

T[3] is  not free,so next probe sequence is computed as

h(65,2)=(65 mod 11+2+3*2²)mod 11

            =(10+2+12)mod11

            =24 mod 11=2

T[2] is free,insert the key 65 at this place.

After inserting key hash table is