Searching and Sorting - A Concise and Practical Introduction to Programming Algorithms in Java - page 141

two underlying ideas of hashing are:

- Convert object elements X into integer numbers x by a conversion function
x=I(X) . The problem is then to transform a set of n integers sparsely lying
in N into a compact array of size m much less than n (written as m<<n ).

- Use an array to store the elements. Since arrays are of prescribed sizes, use a
hashing function that operates some modulo operation to map an integer
x into its hash index h(x) .

The main problem hashing techniques have to deal with are collisions . Collision
occurs whenever two objects X and Y have been hashed into the same index.
That is, h(I(X)) is identical to h(I(Y)) . Often, the hashing function is taken
as h ( k )= k mod m , where m is a prime number.
Finding good hashing functions that minimize the risk of collisions, and
adopting a good search/store policy in cases of collisions are the two challenging
tasks of hashing that we will describe in the next chapter. The following code
shows a basic skeleton for hashing strings. It does not solve collisions but rather
explicitly reports them on the console output.

static int m=23;
static int String2Integer (String s)
int result=0;
for ( int j=0;j < s . length () ; j++)
r e s u l t +=( int )s.charAt(j);
return result ;
// Note that m is a static variable
static int HashFunction( int l)
{ return l%m; }

Program 6.12 A demonstration code for hashing strings
public static void main ( String [ ] args )
{ String [] animals= { "cat" , "dog" , "parrot" , "horse" , "fish" ,
"shark" , "pelican" , "tortoise" , "whale" , "lion" ,
"flamingo" , "cow" , "snake" , "spider" , "bee" , "peacock" ,
"elephant" , "butterfly" } ;

int i;
String [] HashTable= new String [m];

for (i=0;i < m; i ++)
HashTable [ i ]= new String( "-->" );

for (i=0;i < animals . length ; i++)
{ int pos=HashFunction(String2Integer (animals [ i ]) ) ;

HashTable [ pos]+=( "" +animals [ i ] ) ;