DrJava code base. The generic hash function is the method hash in the
HashUtilities class in the util package. The new hash function is a
compromise between computational simplicity and hashing efficicacy; it
is purportedly based on a hash function suggested by Knuth, but I have
not confirmed this attribution by going back to the original sources
(The Art of Programming, vol. 3, Sorting and Searching). The key idea
is to combine 32 bit hash keys (where a typical class has multiple
hash keys) using exclusive OR after multiplying the existing accumulated
result by a large prime number that is approximately 2^32 divided
by the golden ratio. Since this quantity is an unsiged number bigger
than 2^31, it corresponds to a negative int. But this negative int
behaves just like Knuth's unsigned magic number when used in 32 bit
multiplications (which appear to compute an unsigned 32 bit result
modulo 2^32). It has been years since I looked at the details of
32 bit 2's complement arithmetic so I am accepting this notion based
on a limited set of experiments that I conducted in DrJava. It should
be investigated more thoroughly.
The new hash function appears slightly slower than the hash functions
it replaces, but that does not appear to have a perceptible effect on
performance (e.g. indenting MainFrame, which performs an enormous
number of hash table lookups).
The following files were modified or added:
M src/edu/rice/cs/drjava/model/debug/jpda/JPDABreakpoint.java
M src/edu/rice/cs/drjava/model/Query.java
M src/edu/rice/cs/drjava/model/DocumentRegion.java
M src/edu/rice/cs/drjava/config/UnaryOpProperty.java
M src/edu/rice/cs/drjava/config/DrJavaProperty.java
M src/edu/rice/cs/drjava/config/BinaryOpProperty.java
M src/edu/rice/cs/drjava/ui/MainFrame.java
M src/edu/rice/cs/drjava/ui/BrowserHistoryPanel.java
M src/edu/rice/cs/drjava/ui/BreakpointsPanel.java
M src/edu/rice/cs/drjava/ui/RegionsTreePanel.java
M src/edu/rice/cs/drjava/ui/RegionsListPanel.java
M src/edu/rice/cs/drjava/ui/FindResultsPanel.java
M src/edu/rice/cs/util/OrderedHashSet.java
M src/edu/rice/cs/util/docnavigation/JTreeSortNavigator.java
M src/edu/rice/cs/util/swing/HighlightManager.java
A src/edu/rice/cs/util/HashUtilities.java
