Java Reference
In-Depth Information
4567
4567
31969
27402
22835
18268
20857489
4567
Figure9.2
An illustration of the mid-square method, showing the details of
long multiplication in the process of squaring the value 4567. The bottom of the
figure indicates which digits of the answer are most influenced by each digit of
the operands.
(equivalently, all bits when the number is viewed in binary) contribute to the
middle two digits of the squared value. Figure 9.2 illustrates the concept.
Thus, the result is not dominated by the distribution of the bottom digit or
the top digit of the original key value.
Example9.7
Here is a hash function for strings of characters:
inth(Stringx,intM){
charch[];
ch=x.toCharArray();
intxlength=x.length();
inti,sum;
for(sum=0,i=0;i<x.length();i++)
sum+=ch[i];
returnsum%M;
}
This function sums the ASCII values of the letters in a string. If the hash
table size M is small, this hash function should do a good job of distributing
strings evenly among the hash table slots, because it gives equal weight to
all characters. This is an example of the folding approach to designing a
hash function. Note that the order of the characters in the string has no
effect on the result. A similar method for integers would add the digits of
the key value, assuming that there are enough digits to (1) keep any one
or two digits with bad distribution from skewing the results of the process
and (2) generate a sum much larger than M. As with many other hash
functions, the final step is to apply the modulus operator to the result, using
table size M to generate a value within the table range. If the sum is not
sufficiently large, then the modulus operator will yield a poor distribution.
For example, because the ASCII value for “A” is 65 and “Z” is 90,
sum
will
always be in the range 650 to 900 for a string of ten upper case letters. For
