FWIW this is also the implementation I used, also nicked from Knuth
(with credit), in my "Fast" set and map implementations. I also
believe it to be correct.
private int find(long key) {
int theHashCode = (int) key & 0x7FFFFFFF; // make sure it's positive
long[] keys = this.keys;
int hashSize = keys.length;
int jump = 1 + theHashCode % (hashSize - 2);
int index = theHashCode % hashSize;
long currentKey = keys[index];
while (currentKey != NULL && (currentKey == REMOVED || key != currentKey)) {
if (index < jump) {
index += hashSize - jump;
} else {
index -= jump;
}
currentKey = keys[index];
}
return index;
}
On Wed, Jan 27, 2010 at 8:38 AM, Dawid Weiss <dawid.we...@gmail.com> wrote:
> The implementation in Colt is correct, it is double addressing, the
> value of the second hash is always relatively prime to the first one
> (and must not be zero). The colt's implementation can be rewritten as:
>
> const_increment = 1 + h % (m - 2);
>
> if you do a loop
>
> while (true)
> {
> slot = (slot + const_increment) % m;
> }
>
> you will eventually iterate all slots between 0...m-1, no matter what
> const_increment's value was chosen. As far as I remember, Knuth also
> suggests to pick h2 (the second hash function) as a function of the
> first hash function, don't have the book with me right now though.
>
> D.
>
