Hashing With Quadratic Probing

Quadratic probing uses a hash function of the form:

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

Where h' is the auxiliary hash function, c1 and c2 != 0 .The initial position probed is T(h'(k)); later positions probed are offset by amounts that depend in a quadratic manner on the probe number i .

---

Let's take an example. Consider the keys 76, 26, 37, 59, 21, and 65 into the hash table of size m=11 using quadratic probing with c₁=1 and c₂=3 with hash function h^'(k)=k mod m.

Initially, the table is empty.

a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]	a[10]

h(76,0) = (76 mod 11 + 0 + 3x0) mod 11 =10

h(26,0) = (26 mod 11 + 0 + 3x0) mod 11=4

h(59,0) = (59 mod 11 + 0 + 3x0) mod 11=4. a[4] is not free. So the next sequence will be

h(59,1) = (59 mod 11 + 1 + 3x1) mod 11=8

Similarly, other keys are placed properly in the correct position. The hash table becomes,

a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]	a[10]
		65	21	26			59	37		76

---

Source code of Hashing with Quadratic Probing

#include <stdio.h> #define MAX 11 int a[MAX]; void qp(int ,int[]); void qpsr(int, int[]); void display(int[]); int main() { int i,key,ch; for(i=0;i < MAX;i++) a[i]=-1; do { printf("\n1.insert"); printf("\n2.search key"); printf("\n3.Display"); printf("\n4.exit"); printf("\nenter choice:"); scanf("%d",&ch); switch(ch) { case 1:do { printf("\nenter key value[type -1 for termination]"); scanf("%d",&key); if(key!=-1) qp(key,a); }while(key!=-1); break; case 2:printf("\nenter search key value:"); scanf("%d",&key); qpsr(key,a); break; case 3:display(a); break; case 4:return 0; } }while(ch!=4); return 0; } void qp(int key,int a[MAX]) { int loc,i=1; loc=key%MAX; while(a[loc]!=-1) { loc=(key%MAX+(i*i)); loc=loc%MAX; i++; } a[loc]=key; } void qpsr(int key,int a[MAX]) { int loc; loc=key%MAX; while((a[loc]!=key)&&(a[loc]!=-1)) loc=++loc%MAX; if(a[loc]!=-1) printf("\nsearch successful at %d index of list",loc); else printf("\nsearch unsuccessful"); } void display(int a[MAX]) { int i; for(i=0;i < MAX;i++) printf("%d ",a[i]); }

Happy Exploring!