Hashing With Linear Probing

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, we systematically examine table slots until the desired element is found or it is clear that the element is not in the table. Thus in open addressing the load factor λ can never exceed 1.

The advantage of open addressing is that it avoids pointers altogether. Instead of following pointers, we compute the sequence of slots to be examined. The process of examining the locations in the hash table is called probing.

Given an ordinary hash function h^': U[0, 1,...., m-1] the method of linear probing uses the hash function as

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

Where m is the size of the hash table and h^'(k)= k mod m. Given key k, the first slot probed is T[h^'(k)]. We choose the next probe slot T[h^'(k) + 1] and so on up to slot T[m - 1].

---

Let's take an example. Consider the keys 26, 37, 59, 76, 65, and 86 into a hash table of size m=11 using linear probing with the hash function h^'(k)=k mod m.

Initially, the hash 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]

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

h(37, 0)= [37 mod 11 + 0]mod 11 = 4.Since a[4] is not free, the next probe sequence is computed as h(37, 1)= [37 mod 11 + 1]mod 11 = 5

Similarly, other key values are placed in the hash table. 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				26	37	59			86	76

---

Hashing With Linear Probing Using C

#include <stdio.h> #define MAX 10 int a[MAX]; void lp(int, int[]); void lpsr(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) lp(key,a); }while(key!=-1); break; case 2:printf("\nenter search key value:"); scanf("%d",&key); lpsr(key,a); break; case 3:display(a); break; case 4:return 0; } }while(ch!=4); return 0; } void lp(int key,int a[MAX]) { int loc; loc=key%MAX; while(a[loc]!=-1) loc=++loc%MAX; a[loc]=key; } void lpsr(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!