in reply to Re^2: RFC: Is there a solution to the flaw in my hash mechanism? (p-1?)
in thread RFC: Is there a solution to the flaw in my hash mechanism? (And are there any others?)

$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.

- tye        

Replies are listed 'Best First'.
Re^4: RFC: Is there a solution to the flaw in my hash mechanism? (p-1?)
by BrowserUk (Patriarch) on Jun 03, 2015 at 03:24 UTC

    You're right! I misread the precedence. Is this what you meant? 

    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: 14 12 10  8  6  4  2  0 15 13 11  9  7  5  3  1 16
16:  0 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1

    [download]

    0 % anything == 0 so i becomes 1 + 0; and 0 gets added at each iteration; which never terminates.

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
    In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]
[d/l]

      I guess you need to have your demonstration code take a step back so that it is closer to the actual hashing problem in order for you to be able to use it to demonstrate the value of my suggestion. For example: 

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

      [download]

      An interesting side-effect is that slot 0 is now always the last slot to be filled (I believe).

      - tye        

[reply]
[d/l]

        The point of the outer loop:

        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; 
};;

        [download]

        with $i running 0 .. 16, is that $i takes on all possible values after the first mod prime. Ie. $i is the initial insertion point.

        In the original examples, $j was simply a copy of $i, so that it can retain the value of the initial insert point, for use when $j has been modified: i) for the row label; ii) because it is re-used in the calculation of the next insertion point: $j = ( $j + $i ) % 17 in the retry loop.

        What you've done by re-casting the code (which certainly works BTW), is effectively the same as this (with an offset) :

        for( my $i=0; $i < 17; ++$i ) { 
    my $j = $i ||= 1; 
    printf "%2u: %s\n", $i, join' ', map{ sprintf "%2u", $j = ( $j + $
+i ) % 17 } 0 .. 16; 
};;
 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

        [download]

        Which is intriguing.

        I'd almost settled on having a separate (dynamic) spill array to hold (probably rare (0.0000005%)) values that are 0 congruent to the prime and doing a linear search to check if they are already there.

        One upside of that idea is that it means I can use 0 in the main array to mean not allocated. If I don't go that route, I have to find another value to represent an empty slot; which would basically mean either reducing the possible range of inputs (exclude 2**64-1 for example), or use the spill array for that other value.

        If I'm going to have to have a spill array anyway, it might as well be for the 0s; but now looking at the pattern of the insertions your code presents, I'm torn.

        Thank you. And sorry I misunderstood you.

        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
        In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom