Yes, I get it now.
On Wed, Jan 27, 2010 at 6:32 AM, Sean Owen <sro...@gmail.com> wrote:
> 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.
>>
>
