RFC: Is there a solution to the flaw in my hash mechanism? (And are there any others?)

[BrowserUk]

In Re^6: Heap structure for lookup?, I posted the bare bones of a very lightweight hash algorithm that is to be used for lookup purposes only.

The basis of that algorithm is (I think this is the correct mathematical term) co-primality.

Size the underlying array to that of a prime number somewhat bigger than the number of elements you want to store in the hash -- I chose 200,000,033 for my tests.

To insert an element, calculate the hash function -- or in my case, use the value of the 64-bit integer as the hash --, calculate the insertion point as i = hash % PRIME;, and attempt the insertion.

If that slot is already occupied, add the prime number to the previously calculated insertion point and again take the result mod PRIME: i = ( i + PRIME ) % PRIME; and try again.

This simple mechanism has the rather nice property that it will eventually try every possible location before returning to the starting point -- which if it happened would indicate that the array is completely full.

A second nice property is that the steps by which it jumps around the array are different for every initial insertion point; thus (probabilistically) avoiding excessive clustering.

To demonstrate with small numbers. An array size 17:

 ReTry: 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
First
    0:  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
    1:  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16  0  1
    2:  4  6  8 10 12 14 16  1  3  5  7  9 11 13 15  0  2
    3:  6  9 12 15  1  4  7 10 13 16  2  5  8 11 14  0  3
    4:  8 12 16  3  7 11 15  2  6 10 14  1  5  9 13  0  4
    5: 10 15  3  8 13  1  6 11 16  4  9 14  2  7 12  0  5
    6: 12  1  7 13  2  8 14  3  9 15  4 10 16  5 11  0  6
    7: 14  4 11  1  8 15  5 12  2  9 16  6 13  3 10  0  7
    8: 16  7 15  6 14  5 13  4 12  3 11  2 10  1  9  0  8
    9:  1 10  2 11  3 12  4 13  5 14  6 15  7 16  8  0  9
   10:  3 13  6 16  9  2 12  5 15  8  1 11  4 14  7  0 10
   11:  5 16 10  4 15  9  3 14  8  2 13  7  1 12  6  0 11
   12:  7  2 14  9  4 16 11  6  1 13  8  3 15 10  5  0 12
   13:  9  5  1 14 10  6  2 15 11  7  3 16 12  8  4  0 13
   14: 11  8  5  2 16 13 10  7  4  1 15 12  9  6  3  0 14
   15: 13 11  9  7  5  3  1 16 14 12 10  8  6  4  2  0 15
   16: 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0 16

The flaw with that is the first row. If the (initial_hash_value % PRIME ) = 0;, then the scheme falls apart and the second and all subsequent hash%prime == 0 values can never be stored.

The code I posted incorporated an iteration count (c), that defended against an infinite loop; but it doesn't address the problem.

My first thought was to size the array 1 larger than the chosen prime, and add 1 to the mod'd value; thus the zeroth element is never used; but that just results in an infinite loop of 1s rather than 0s.

Is there a trivial (or not so) solution to the problem that I'm missing?

Are there any other problems I'm missing?

[tye]

Start by taking $i = 1 + $hash % ($p-1) instead of $i = $hash % $p ?

[BrowserUk]

That just offsets the problem, not fixes it unfortunately:

for( my $i=0; $i<17; ++$i ) { 
    my $j = ( 1 + $i ) % ( 17 - 1 ); 
    printf "%2u: %s\n", $i, join' ', map{ sprintf "%2u", $j = ( $j + $
+i ) % 17 } 0 .. 16; 
};;
 0:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 <<<<<<<<<<<<<<<
+<<<<<<<<<<<<<<<<<<<<<<
 1:  3  4  5  6  7  8  9 10 11 12 13 14 15 16  0  1  2
 2:  5  7  9 11 13 15  0  2  4  6  8 10 12 14 16  1  3
 3:  7 10 13 16  2  5  8 11 14  0  3  6  9 12 15  1  4
 4:  9 13  0  4  8 12 16  3  7 11 15  2  6 10 14  1  5
 5: 11 16  4  9 14  2  7 12  0  5 10 15  3  8 13  1  6
 6: 13  2  8 14  3  9 15  4 10 16  5 11  0  6 12  1  7
 7: 15  5 12  2  9 16  6 13  3 10  0  7 14  4 11  1  8
 8:  0  8 16  7 15  6 14  5 13  4 12  3 11  2 10  1  9
 9:  2 11  3 12  4 13  5 14  6 15  7 16  8  0  9  1 10
10:  4 14  7  0 10  3 13  6 16  9  2 12  5 15  8  1 11
11:  6  0 11  5 16 10  4 15  9  3 14  8  2 13  7  1 12
12:  8  3 15 10  5  0 12  7  2 14  9  4 16 11  6  1 13
13: 10  6  2 15 11  7  3 16 12  8  4  0 13  9  5  1 14
14: 12  9  6  3  0 14 11  8  5  2 16 13 10  7  4  1 15
15: 15 13 11  9  7  5  3  1 16 14 12 10  8  6  4  2  0
16:  0 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1

[tye]

$i = 1 + $hash % ($p-1)

my $j = ( 1 + $i ) % ( 17 - 1 );

I'm not sure who you got those extra parens from, but they weren't from me. :)

Or, looking at it another way:

my $i=0;

The point of my suggestion, $i = 1 + $hash % ($p-1), is that it never results in $i == 0 (even if your computed $hash equals 0). So calling out the line that resulted from you doing $i=0 doesn't really have much bearing on the validity of my suggestion.

Does any of that help you see how you misinterpreted my suggestion? I ask because I'm not completely sure were the disconnect is and I'm reluctant to try guess at what I should try to explain.

[RichardK]

You didn't calculate (n + p) %p -- what you actual did was (n + n%p) % p, and when n%p is zero you get stuck.

[BrowserUk]

You didn't calculate (n + p) %p

But ( 0 + x ) % x is just x % x; and is always 0?

[RichardK]

Yes you're right.

So your code does something like this :-

     int r = rand();
     int n = r % p;
     while ( a[n] != 0 ) {
         n = (n + n) % p;
     }
     a[n] = r;

so you get stuck when n =0. But if you add a value to n that's relatively prime to P then it should work.

for example,

say (($_ + 5) % 11 ) for (0..10);

5
6
7
8
9
10
0
1
2
3
4

[QM]

I'm not sure I've captured all of the comments here, but here's my suggestion: Use the value at the hash collision to get the offset for the next hash key. If the hash value is 0 mod $PRIME, use half the prime as an offset, to avoid clustering. In Perl, if you will:

my %hash; # hash of stored values
my $PRIME = some_large_prime(); # random or fixed, your choice
my $PRIME_HALF = int($PRIME/2); # or some other known value or functio
+n
...
my $i = $initial_index; # wherever you get this from
my $failed_tries = $PRIME;
while (defined($hash{$i}) and $failed_tries--) {
    my $offset = $hash{$i} % $PRIME;
    $offset = $PRIME_HALF if ($offset == 0);
    $i = ($i + ($hash{$i}) % $PRIME;
}

if ($failed_tries) {
    $hash{$i} = $value;
} else { 
    warn "Hash full\n";
}

Update: I'm assuming that the hash values, once written, are read only, and never change.

[BrowserUk]

Use the value at the hash collision to get the offset for the next hash key.

Problem. The value giving the trouble is 0; so the value at the hash collision can be 0; and 0 + 0 == 0 :)

Of course, it won't always be zero. Any multiple of the Prime size will mod to a hash of 0; but is still means that if a true 0 value arises, the thing disappears up it you know where.

Having spent the last 3 days running some long-running, large scale simulations; I'm satisfied that the benefits of the declustering affect of the i⁺¹ = ( i + prime ) % prime scheme are real, and outweigh the need to have an if( !i ) { //take a different path conditional test in the inner loop.

I'm still trying a couple of things for that other path; but adding prime/2 seems as good as any other thing I've thought of.