Bug ID: JDK-4045622 java.lang.String.hashCode spec incorrectly describes the hash algorithm

SUGGESTED FIX The following is the accepted proposal for the new string hash function, followed by a report justifying its selection: New String Hash Function (Bugs 4045622, 1258091) ================================================ The Problem: The currently specified String hash function does not match the currently implemented function. The specified function is not implementable. (It addresses characters outside of the input string.) The implemented function performs very poorly on certain classes of strings, including URLs. (The poor performance is due to the "sampling" nature of the function for strings over 15 characters.) I view the specification problem as the perfect opportunity to replace the unfortunate implementation. Requesters: The problems with the implementation have been mentioned on comp.sys.java.lang.programmer, though the extent of the problem may not be known outside of JavaSoft. The problems with the spec were discovered by Peter Kessler and myself. Proposed API change: No API would change, per se. The function computed by String.hashCode() would change to: s[0] * 31^(n-1) + s[1] * 31^(n-2) + ... + s[n-1] where s[i] is the ith character of string s. The Java Language Specification (which specifies the value to be returned by String.hashCode()) would be modified to reflect this. The new hash function was selected after a fair amount of study, as described in Exhibit A. In the unlikely event that you want even more detail, see me. Implementation: Trivial. (4 lines of code, which have already been written.) Performance impact: Hashing large strings will be somewhat more expensive, as the new hash function examines every character, but Hashtables performance will, on balance, improve, as hash collisions will be vastly reduced. While one could construct a program to demonstrate the reduced speed of the new hash function, I would be very surprised if any real applications were adversely affected in any measurable way. Risk Assessment: Surprisingly small. Serialization of Hashtables does not depend on consistent hash values. It is possible that some customer has implemented some persistent data structure that relies on the String hash function not changing, but it is highly unlikely that more than a handful of customers have done so. Testing Impact: None, really. I've performed a fair number of tests on the proposed hash function already. (See below.) Doc Impact: The release notes would have to mention the change, so that any "researchy" customers who do rely on the precise behavior of the hash function would be alerted. The JLS would have to be modified in its next edition. The actual text would be very short (1-2 paragraphs). ****************************************************************************** Exhibit A As per Guy's request, here's a note describing the "Pedigree" of my proposed String hash function. Surprisingly, I could find very little in the way of published literature on practical, general-purpose string hash functions; much of what is published is either outdated (e.g., Knuth V. 3, Pp. 508-513) or arcane (lots of journal articles on 'perfect hashing'). Most of the standard algorithms and data structures textbooks barely mention the subject. The best treatment I was able to find was in Aho, Sethi and Ullman's "Compilers: Principles, Techniques and Tools" AKA "The Dragon Book" (Pp. 433-438). The class of hash function that I recommend using is polynomials whose coefficients are the characters in the string: P(x) = s[0] * x^(n-1) + s[1] * x^(n-2) + ... + s[n-1] This polynomial is calculated by the following code fragment: int hashVal = 0; for (int i=0; i<string.length; i++) hashVal = x*hashVal + s.charAt(i); The value of x is part of the definition of the hash function; choosing this value is somewhat of a black art. Clearly 1 or any multiple of 2 is bad. Primes seem safer than composite numbers, though some composite numbers yield excellent performance (as shown below). While this class of hash function is recommended in The Dragon Book (P(65599)) and Kernighan and Ritchie's "The C Programming Language, 2 Ed." (P(31)), it is not attributed in either of these books. I went so far as to call up Dennis Ritchie, who said that he did not know where the hash function came from. He walked across the hall and asked Brian Kernighan, who also had no recollection. A shareware library from Germany called "Matpack" contains ten string hash functions, including P(33), which it attributes to noted Unix hacker Chris Torek. I sincerely doubt that it's original with him. P(37) is used in the definition of the current Java String hash function for short (< 16 characters) strings. I'm afraid that the origins of this little function are lost to history. So why do I think we should use this function? Simply put, it's the best general purpose string hash function that I was able to find, and it's cheap to calculate. By 'general purpose', I mean that it's not optimized for any specific type of strings (e.g., compiler symbols), but seems to resist collisions across every collection of strings that I was able to throw at it. This is critical given that we have no idea what sort of strings people will store in Java hash tables. Also, the performance of this class of hash functions seems largely unaffected by whether the size of the hash table is prime or not. This is important because Java's auto-growing hash table is typically does not contain a prime number of buckets. In addition to the class of hash functions described above, The Dragon Book highly recommends a slightly more complex hash function due to P. J. Weinberger, originally used internally in his C compiler. Matpak's author, Dr. Berndt M. Gammel (of Technische Universit??t M??nchen), however, claims that Weinberger's function does not work well for large collections of arbitrary strings. It turns out that Matpak's implementation of Weinberger's function contains a typo, and the resulting function is far, far worse even than the currently implemented Java string hash function (see table below). I notified Dr. Gammel, and he promised to fix the typo. The published version of Weinberger's function (in the Dragon book) differs slightly from the version that he (Peter Weinberger) personally recommends. (They differ in the number of bits to which the hash value is shifted: the published value is 24, the recommended value is 28.) The recommended version is significantly better (see Table). Gammel recommends only three of the ten hash functions in Matpak for "general use." One is P(33), one is a minor variant on P(129), ascribed to Phong Vo, and the third is a table lookup based, S-box like algorithm, relying on a table of 256 "random" 32-bit numbers, from the WAIS project. (The Vo variant merely adds the constant 987654321 to each character to form the polynomial coefficients.) The table below summarizes the performance of the various hash functions described above, for three data sets: 1) All of the words and phrases with entries in Merriam-Webster's 2nd Int'l Unabridged Dictionary (311,141 strings, avg length 10 chars). 2) All of the strings in /bin/*, /usr/bin/*, /usr/lib/*, /usr/ucb/* and /usr/openwin/bin/* (66,304 strings, avg length 21 characters). 3) A list of URLs gathered by a web-crawler that ran for several hours last night (28,372 strings, avg length 49 characters). The performance metric shown in the table is the "average chain size" over all elements in the hash table (i.e., the expected value of the number of key compares to look up an element). Webster's Code Strings URLs --------- ------------ ---- Current Java Fn. 1.2509 1.2738 13.2560 P(37) [Java] 1.2508 1.2481 1.2454 P(65599) [Aho et al] 1.2490 1.2510 1.2450 P(31) [K+R] 1.2500 1.2488 1.2425 P(33) [Torek] 1.2500 1.2500 1.2453 Vo's Fn 1.2487 1.2471 1.2462 WAIS Fn 1.2497 1.2519 1.2452 Weinberger's Fn(MatPak) 6.5169 7.2142 30.6864 Weinberger's Fn(24) 1.3222 1.2791 1.9732 Weinberger's Fn(28) 1.2530 1.2506 1.2439 Looking at this table, it's clear that all of the functions except for the current Java function and the two broken versions of Weinberger's function offer excellent, nearly indistinguishable performance. I strongly conjecture that this performance is essentially the "theoretical ideal", which is what you'd get if you used a true random number generator in place of a hash function. I'd rule out the WAIS function as its specification contains pages of random numbers, and its performance is no better than any of the far simpler functions. Any of the remaining six functions seem like excellent choices, but we have to pick one. I suppose I'd rule out Vo's variant and Weinberger's function because of their added complexity, albeit minor. Of the remaining four, I'd probably select P(31), as it's the cheapest to calculate on a RISC machine (because 31 is the difference of two powers of two). P(33) is similarly cheap to calculate, but it's performance is marginally worse, and 33 is composite, which makes me a bit nervous. Josh ****************************************************************************** From: Guy Steele - Sun Microsystems Labs <###@###.###> To: jbloch@Eng Cc: gls@East, James.Gosling@Eng, wnj@central, ###@###.###, riggs@East, ###@###.### Subject: Re: String Hash Function Redux (long) Date: Mon, 28 Apr 1997 09:47:22 -0400 (EDT) Good work! Besides the fact that you have clearly established that we ought to revamp Java's hash function and have found a good solution, I think you have an MPU here (Minimum Publishable Unit)---that is, I would encourage you to write this up even more carefully and send it to an ACM conference (PLDI?) or journal. --Guy