Non-Linear Data Structure 553
15.8 HASHING TECHNOLOGY
Hash method: Hash technique is one of the complex searching techniques. In this topic, we consider
a class of search techniques whose search time is dependent on the number of entries available in the
table. In this method, we fix the position of the key (element) into the table or the file, which is determined
by the hash function. The function in which we use this key is known as the hashing function.
For example, if we want to search a number from the ten numbers of a file, then we must find the
number throughout this range from the first number to the tenth number. When we use the key for
fixing its position in a table, then the number can be searched very easily.
Hashing function: In order to follow the operation of a hashing function consider an array that
comprises a list containing some finite number of elements. Each element of it is a key. On performing
operations on each key, some value is obtained. The key is assigned to the index, which is having the
appropriate value. The table prepared with the keys is called a hashing table.
Let us assume the following array that will hold the hash table.
12,22,32,17,19,28,15,29,16,18,13,11.
Let us use the division method for the following hash table. We divide the key by '3' and the key is
placed in the index based on the remainders obtained. The keys having equal remainders are placed
in the same index. Any number divided by 3 always returns 0,1 or 2. A hash table is prepared with
three indices such as 0,1,2. All the above keys are stored in these three indices as shown in Table 15.1.
Take the first key '12', divide it by the '3'. The remainder is 'O', hence insert it into the '0' index.
Then take the next key '22', divide it by the '3'. The remainder is T . Hence, insert the key in to the T
index.
In the same way, divide the key '32' by 3. Its reminder is 2 after dividing it by 3. Place it into the '2'
index in the table.
For the remaining elements, the same procedure is to be repeated and by knowing reminders the
numbers can be placed appropriately in the respective index table.
Table 15.1 explains a hashing table.
Table 15.1 Hash table
Index Keys
0 12,15,18
1 22,19,28,16,13
2
32,17,29,11
In short, the hashing function takes the key, and maps it to some index to the array. In our example,
division function has been selected. The programmer can take any other function. This function maps
several different keys to the same index. In the above table, keys 12,15 and 18 are assigned to the index
0. While keys 22,19,28,16 and 13 are placed in index 1. Keys 32,17,29 and 11 are in the index 2.
After preparation of the index table, it becomes easier to search the element from the list. One can
use any searching method to search the element from the hashing table.
Consider the following program for preparation of an index using divide method.
15.3 Write a program to prepare the hashing table. Enter the elements through the keyboard
and map them in index. Use the division function.
#include<8tdio. h>
#include<canio. h>
main ()
554 Programming and Data Structures
{
Int n [12],iO [12],i l [12],i2 [12];
int rem,a*0,bs0,cs0,i, j;
clrsc rO ;
printf (" nEnter the elements of array:11) ;
for (icO;i<12; i++)
scanf ("%dB#& n[i]);
for(i=0; i<12;i++>
{
rem*n[i]%3;
if(remssO)
{
a++;
iO [a ]= n [i];
}
else
{
if(rem =*l)
{
b+ + ;
11 [b] =n [i] ;
}
else
{
C++;
12 [c] =n [i] ;
}
}
}
printf ("n
The Hashing Table is as follows :n") ;
printf ("
--------------------------------------------------
") ;
printf ( "Index 0: ");
fo r (j=l;j<=a;j++)
prin tf("% 5 d",i0 [j]);
printf ("
lndex 1 :");
fo r (j*l;j< =b ;j+ +)
p rin tf(»% 5 d -,il[j]);
printf ("
lndex 2 :");
fo r (j»l;j< * c ;j+ + )
prin tf("% 5 d",i2 [j]);
printf ("
-------------------------------------------------- ");
Non-Linear Data Structure 555
OUTf i TT:
Enter the elements of array: 12 22 32 17 19 28 15 29 16 18 1311
The Hashing Table is as follows:
Index 0: 12 15 18
Index 1: 22 19 28 16 13
Index 2: 32 17 29 11
Explanation In the above program the main array 'n[12]' is declared having 12 elements. Ln addition
to the above, i0[], il [] and i2[] arrays are initialized for storing the index. These arrays also accommodate
12 elements. In the above program, we calculate the hashing table by using the division method. The
keys are divided by 3. Using the mod operation the reminders are computed and they are placed in the
appropriate index.
Some of the hashing methods that are commonly used are stated below.
The division method: The commonly used hashing method is the division method. In this hashing
function, the integer key is divided by some number. The reminder value is taken as the hashing value.
This method can be expressed as follows.
H(k) = k(mod x )+1
In the above equation, the H(k) is the hashing function. In addition, k is the key, which is to be used
in hashing. k(mod x) shows the result of division k by x.
In the above equation, 'k' is the key and V is the size of the list. We can take any value for x.
For example, key is 25 and x=10,
H(25) = 25(mod 10)+1 =5+1=6
Consider an example to prepare a hashing table and search the prompted number from the hashing
table. Each number (key) is divided (mod operation) by 3. No addition of 1 is done after division. It is
up to the user how to deal with the problem. The user can perform simply division operation and note
down the remainders and place them in appropriate index. As such, there will be three indices. The
following program illustrates this concept.
15.4 Write a program for division method hashing and find the given number from the
hashing table.
#include<stdio. h>
#include<conio. h>
main ()
int n [5] , 10 [5], i l [5], 12 [5];
int mim,rem,aa0,b«0,CB0,i, j;
clrscr();
printf ("
Enter the elements of a r ra y :");
for(i=0;i<5;i++)
scanf ( "%d", &n [ i ] );
556 Programming and Data Structures
for(i=0;i<5;i++)
{
rem=n[i] %3;
if(rem*=0)
{
a++ ;
iO [a] «n [i] ;
}
else
{
if(rem »=l)
{
b++;
i l [b] * n [ i ] ;
}
else
{
C++;
i2 [c] *n [i] ;
}
}
}
printf ("nnThe Hashing Table is as follows :n") ;
p rin tf( " -----------------------------------------
--------
n");
p rin t f( " Index 0: ") ;
fo r(j=l;j<=a;j++)
p rin tf( "%5d",iO [j ]);
printf ("
lndex 1: ");
fo r(j=l;j<=b;j+ +)
p rin tf( "%5d", i l [ j ] ) ;
printf (" nlndex 2 : ") ;
fo r (j= l;j<»c ;j+ + )
p rin tf(*%5d",i 2 [j ] );
printf ("n--------------------------------------
-----------
");
printf ("
Enter the key to search:")
scanf ("%d", &num) ;
renwuo%3;
i f (rem==0)
{
fo r (j= l;j<=a ;j+ + )
i f (numa=iO [j ] )
prin tf ("nThe position of the number is %d in the Index 0", j ) ;
Non-Linear Data Structure 557
if(rem==l)
{
fo r (j=l;j<=b;j++)
if(n um ==il[j ] )
printf ("nThe position of the number is %d in Index 1", j) ;
}
if(rem==2)
{
for(j=l;j<=c ;j++)
i f (num»i2 [ j ] )
prin tf ("
Tbe position of the number is %d in the Index 2", j ) ;
}
OUTPUT:
Enter the elements of array:4 11 5 17 23 12 10 13 6 21
The Hashing Table is as follows:
Index 0: 12 6 21
Index 1: 4 10 13
Index 2: 11 5 17 23
Enter the key to search:23
The position of the number is 4 in the Index 2
Explanation In the above program the main array 'n[]' is declared. In it five elements are declared. In
addition to the above, i0[], il[] and i2[] arrays are also initialized for storing the index. In the above
program, we calculate the hashing table by using the division method. The keys are divided by 3.
Using the mod operation, the remainders are calculated and are placed in the appropriate index. The
number which is to be searched is prompted through keyboard, using variable num. The number is
divided by 3 and after knowing the remainder the particular index is searched for the element.
The mid-square method: In mid-square method the key is multiplied by itself and the middle digit is
chosen as the address of that element in the hashing table. It is defined as follows.
H(k)=(k*k)
For example, if the key is k=12,
H(12) = (12*12) =144
In the above example, the key is 12, its square 144 and its middle digit is 4. Hence, 12 is paced in the
hash table in the index 4 as index 4 is the address of 12. Similarly, for other keys the squares are
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.