Java Reference
In-Depth Information
1 // Acceptable hash function
2 public static int hash( String key, int tableSize )
3 {
4 int hashVal = 0;
5
6 for( int i = 0; i < key.length( ); i++ )
7 hashVal = ( hashVal * 128 + key.charAt( i ) )
8 % tableSize;
9 return hashVal;
10 }
figure 20.1
A first attempt at a
hash function
implementation
function somewhat faster by performing a single mod operation immediately
prior to the return. Unfortunately, the repeated multiplication by 128 would
tend to shift the early characters to the left—out of the answer. To alleviate
this situation, we multiply by 37 instead of 128, which slows the shifting of
early characters.
The result is shown in Figure 20.2. It is not necessarily the best function
possible. Also, in some applications (e.g., if long strings are involved), we
may want to tinker with it. Generally speaking, however, the function is quite
good. Note that overflow could introduce negative numbers. Thus if the mod
generates a negative value, we make it positive (lines 15 and 16). Also note
that the result obtained by allowing overflow and doing a final mod is not the
same as performing the mod after every step. Thus we have slightly altered
the hash function—which is not a problem.
The hash function
must be simple to
compute but also
distribute the keys
equitably. If there are
too many collisions,
the performance of
the hash table will
suffer dramatically.
1 /**
2 * A hash routine for String objects.
3 * @param key the String to hash.
4 * @param tableSize the size of the hash table.
5 * @return the hash value.
6 */
7 public static int hash( String key, int tableSize )
8 {
9 int hashVal = 0;
10
11 for( int i = 0; i < key.length( ); i++ )
12 hashVal = 37 * hashVal + key.charAt( i );
13
14 hashVal %= tableSize;
15 if( hashVal < 0 )
16 hashVal += tableSize;
17
18 return hashVal;
19 }
figure 20.2
A faster hash function
that takes advantage
of overflow
Search WWH ::




Custom Search