neo4j/neo4j — pull request #2246 by tinwelint (2014-04-08 22:59:26+00:00)
Title: Primitive hash collections and maps using hop-scotch hashing

Hop-scotch hashing is an algorithm for dealing with conflicts coming from
hashing values to an index and not really about the hashing itself, as any
hash function can be used with it.

Measured to be comparable to other leading libraries with equal
functionality and with substantially less, also dry, code.
The algorithm itself is pulled out into its own class and clocks in on
about 200-300 LOC, whereas the hash set/map implementations calls that
algorithm with one-liners. The state itself is abstracted into a Table interface
which is trivial to implement with, for example a primitive long[], a
combination of long[] and int[] for a long->int primitive map, a.s.o.

Implementation was driven by an iterative randomizing testing framework
also added in this commit where actions are defined, for example "add" and
"remove" with checks that goes with the actions. In the event a check not
returning OK the execution stops, reduces the list of actions down to a
minimum (by brute-force-reduction one action at a time) and finally prints
a java-code test case to reproduce the problem. Confidence in the code is
high since it has been tested for a very large combination of values
and sizes.

These sets and maps should be preferable over java.util collections in
cases where the key is int or long and access is single threaded.
If need be a multi-threaded version of the algorithm can be added later.