Logo Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Character String Keys

Strings of characters are represented in Java as instances of the String class. A character string is simply a sequence of characters. Since such a sequence may be arbitrarily long, to devise a suitable hash function we must find a mapping from an unbounded domain into the finite range of int.

We can view a character string, s, as a sequence of n characters,

displaymath61628

where n is the length of the string. (The length of a string can be determined by calling the String method length). One very simple way to hash such a string would be to simply sum the numeric values associated with each character:

  equation10709

As it turns out, this is not a particularly good way to hash character strings. Given that a Java char is a 16-bit quantity, tex2html_wrap_inline61636, for all tex2html_wrap_inline61638. As a result, tex2html_wrap_inline61640. For example, given a string of length n=5, the value of f(s) falls between zero and tex2html_wrap_inline61646. In fact, the situation is even worse, in North America we typically use only the ASCII  subset of the Unicode  character set. The ASCII character set uses only the least-significant seven bits of a char. If the string is comprised of only ASCII characters, the result falls in the range between zero and 640.

Essentially the problem with a function f which produces a result in a relatively small interval is the situation which arises when that function is composed with the function tex2html_wrap_inline61650. If the size of the range of the function f is less than M, then tex2html_wrap_inline61544 does not spread its values uniformly on the interval [0,M-1]. For example, if M=1031 only the first 640 values (62% of the range) are used!

Alternatively, suppose we have a priori knowledge that character strings are limited to length n=4. Then, we can construct an integer by concatenating the binary representations of each of the characters. For example, given tex2html_wrap_inline61664, we can construct an integer with the function

  equation10723

where tex2html_wrap_inline61666. Since B is a power of two, this function is easy to write in Java:

static int f (String s)
{
    return s.charAt(0) << 21 | s.charAt (1) << 14
	| s.charAt (2) << 7 | s.charAt (3);
}
While this function certainly has a larger range, it still has a problems--it cannot deal strings of arbitrary length.

Equation gif can be generalized to deal with strings of arbitrary length as follows:

equation10727

This function produces a unique integer for every possible string. Unfortunately, the range of f(s) is unbounded. A simple modification of this algorithm suffices to bound the range:

  equation10732

where tex2html_wrap_inline61270 such that w is word size of the machine. Unfortunately, since W and B are both powers of two, the value computed by this hash function depends only on the last W/B characters in the character string. For example, for tex2html_wrap_inline61372 and tex2html_wrap_inline61666, this result depends only on the last five characters in the string--all character strings having exactly the same last five characters collide!

Writing the code to compute Equation gif is actually quite straightforward if we realize that f(s) can be viewed as a polynomial in B, the coefficients of which are tex2html_wrap_inline61690, tex2html_wrap_inline61692, ..., tex2html_wrap_inline61694. Therefore, we can use Horner's rule  (see Section gif) to compute f(s) as follows:

static int f (String s)
{
    int result = 0;
    for (int i = 0; i < s.length (); ++i)
	result = result * B + s.charAt (i);
    return result;
}
This implementation can be simplified even further if we make use of the fact that tex2html_wrap_inline61698, where b=7. Since B is a power of two, in order to multiply the variable result by B all we need to do is to shift it left by b bits. Furthermore, having just shifted result left by b bits, we know that the least significant b bits of the result are zero. And since each character has no more than b=7 bits, we can replace the addition operation with an exclusive or  operation.
static int f (String s)
{
    int result = 0;
    for (int i = 0; i < s.length () ; ++i)
	result = result << b ^ s.charAt (i);
    return result;
}

Of the 128 characters in the 7-bit ASCII character set, only 97 characters are printing characters including the space, tab, and newline characters (see Appendix gif). The remaining characters are control characters which, depending on the application, rarely occur in strings. Furthermore, if we assume that letters and digits are the most common characters in strings, then only 62 of the 128 ASCII codes are used frequently. Notice, the letters (both upper and lower case) all fall between tex2html_wrap_inline61714 and tex2html_wrap_inline61716. All the information is in the least significant six bits. Similarly, the digits fall between tex2html_wrap_inline61718 and tex2html_wrap_inline61720--these differ in the least significant four bits. These observations suggest that using tex2html_wrap_inline61722 should work well. That is, for tex2html_wrap_inline61372, the hash value depends on the last five characters plus two bits of the sixth-last character.

We have developed a hashing scheme which works quite well given strings which differ in the trailing letters. For example, the strings "temp1", "temp2", and "temp3", all produce different hash values. However, in certain applications the strings differ in the leading letters. For example, the two Internet domain names  "ece.uwaterloo.ca" and "cs.uwaterloo.ca" collide when using Equation gif. Essentially, the effect of the characters that differ is lost because the corresponding bits have been shifted out of the hash value.

   program10761
Program: Str class hashCode method.

This suggests a final modification which shown in Program gif. Instead of losing the b=6 most significant bits when the variable result is shifted left, we retain those bits and exclusive or  them back into the shifted result variable. Using this approach, the two strings "ece.uwaterloo.ca" and "cs.uwaterloo.ca" produce different hash values.

Table gif lists a number of different character strings together with the hash values obtained using Program gif. For example, to hash the string "fyra", the following computation is performed (all numbers in octal):

146 f
tex2html_wrap_inline61728 171 y
tex2html_wrap_inline61728 162 r
tex2html_wrap_inline61728 141a

147706341

 

 

x Hash(x) (octal)
"ett" 01446564
"två" 01656545
"tre" 01656345
"fyra" 0147706341
"fem" 01474455
"sex" 01624470
"sju" 01625365
"åtta" 0344656541
"nio" 01575057
"tio" 01655057
"elva" 044556741
"tolv" 065565566
Table: Sample character string keys and the hash values obtained using Program gif.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.