Java Reference
In-Depth Information
a hash table of size 100 or less, a reasonable distribution results. For a hash
table of size 1000, the distribution is terrible because only slots 650 to 900
can possibly be the home slot for some key value, and the values are not
evenly distributed even within those slots.
Example9.8
Here is a much better hash function for strings.
longsfold(Strings,intM){
intintLength=s.length()/4;
longsum=0;
for(intj=0;j<intLength;j++){
charc[]=s.substring(j
*
4,(j
*
4)+4).toCharArray();
longmult=1;
for(intk=0;k<c.length;k++){
sum+=c[k]
*
mult;
mult
*
=256;
}
}
charc[]=s.substring(intLength
*
4).toCharArray();
longmult=1;
for(intk=0;k<c.length;k++){
sum+=c[k]
*
mult;
mult
*
=256;
}
return(Math.abs(sum)%M);
}
This function takes a string as input. It processes the string four bytes at
a time, and interprets each of the four-byte chunks as a single long integer
value. The integer values for the four-byte chunks are added together. In
the end, the resulting sum is converted to the range 0 to M 1 using the
modulus operator.
2
For example, if the string “aaaabbbb” is passed to
sfold
, then the first
four bytes (“aaaa”) will be interpreted as the integer value 1,633,771,873
and the next four bytes (“bbbb”) will be interpreted as the integer value
1,650,614,882. Their sum is 3,284,386,755 (when viewed as an unsigned
integer). If the table size is 101 then the modulus function will cause this
key to hash to slot 75 in the table. Note that for any sufficiently long string,
2
Recall from Section 2.2 that the implementation fornmodmon many C
++
and Java compilers
will yield a negative number ifnis negative. Implementors for hash functions need to be careful that
their hash function does not generate a negative number. This can be avoided either by insuring that
nis positive when computingnmodm, or addingmto the result ifnmodmis negative.
Here,
sfold
takes the absolute value of
sum
before applying the modulus operator.
