0

I have a hash_probe function which takes a hash value, an index and an capacity to get the probe index by quadratic probing. I dont know why but as I tried different capabilities like 3, 5, 7, 11, 13, 17, 23 I saw that I would only hit every location from n to cap for cap == 3, 7, 11, 23.

Regarding to the answer by user "templatetypdef" and Wikipedia Examples of Quadratic Probing

You can try it below by changing TEST_PRIME macro to any prime number. What do I missunderstand or why does it work with 3, 7, 11, 23 but not with 5, 13, 17?

Example output for Cap == 7 (as expected):

4
3
1
2
6
0
5

Example output for Cap == 5 (not as aspected):

0
4
4
1
1

#include <stdio.h>
#include <string.h>

// hashes str until nullbyte is found
size_t djb2(const char *str)
{
    /* djb2 offset 5381 */
    unsigned long hash = 5381;
    int c;

    while ((c = *str++))
        hash = ((hash << 5) + hash) + (size_t) c; /* hash * 33 + c */

    return hash;
}

// calculates the probe index by hash, index and capability
size_t hash_probe(unsigned long hash, size_t i, size_t cap)
{

    size_t idx = 0;

    if(i & 1) { // odd
        idx = (hash + -(i*i)) % cap;
    } else {
        idx = (hash + (i*i)) % cap;
    }
    return idx;
}

#define TEST_PRIME 23

int main(void)
{
    // get hash
    unsigned long hash = djb2("Hallo Welt!\n");
    
    // loop though 0 to TEST_PRIME and print its probe index value
    for(size_t i = 0; i < TEST_PRIME; i++) {
        size_t idx = hash_probe(hash, i, TEST_PRIME);
        printf("%zu\n", idx);
    }

    return 0;
}
mortytheshorty
  • 175
  • 5
  • 2
    Using alternating signs only works if the number of buckets is a prime that is congruent to 3 mod 4, e.g. 3, 7, 11, 19, 23, 31. If an odd prime is not congruent to 3 mod 4, then it's congruent to 1 mod 4, i.e. 5, 13, 17, 29, etc. Those values won't work with alternating signs. The condition is stated [here in the wiki page](https://en.wikipedia.org/wiki/Quadratic_probing#Alternating_signs). – Tom Karzes Mar 12 '23 at 17:12
  • For all the algebra I don't know, the sequence of offsets isn't (0,) 1, -4, 9, -16… here, but -1, 4, -9, 16. – greybeard Mar 12 '23 at 17:17
  • 1
    @greybeard That's a good point, although I don't think it should matter, since negating all of the offsets just flips the pattern of values. – Tom Karzes Mar 12 '23 at 17:21
  • (@TomKarzes: I respect two and a half approaches: 1) follow spec to the letter 2) provide a rigorous proof 0) provide and pass a convincing test.) – greybeard Mar 12 '23 at 17:25
  • @greybeard I agree it's generally best to follow the spec to the letter. I'm just pointing out that negating the offsets shouldn't affect correctness. The proof that negating the offsets doesn't affect collisions is obvious enough. – Tom Karzes Mar 12 '23 at 17:28
  • I have a function that returns the next higher prime number by provided number. How do I test this `4 * j + 3` is valid for it? – mortytheshorty Mar 12 '23 at 17:44
  • Kidding? Look at the the bit with weight 2. – greybeard Mar 12 '23 at 17:59
  • @greybeard I should have add the beginner tag. What bit and what weight do you mean? – mortytheshorty Mar 12 '23 at 18:21
  • (Eh, just pulling legs. Operational blindness and making errors are characteristics of humans working.) – greybeard Mar 12 '23 at 18:24
  • 1
    (? `p = 4 * j + 3` means p % 4 = p & 3 = 3. As every prime above 2 is odd, `p & 2` and `p & (1 << 1)` are expressions fulfilling *every index should be hit*: for table size 2, original index and its successor mod 2 pretty much cover it.) – greybeard Mar 12 '23 at 18:40
  • 1
    @mortytheshorty To test if a prime `p` is congruent to 3 mod 4, you can use `if p % 4 == 3`. Equivalently, you can use `if (p & 3) == 3`. The latter makes use of the fact that the last two bits of `p`, i.e. `p & 3`, are equal to `p % 4`. – Tom Karzes Mar 12 '23 at 18:54
  • Thank you for explaination I still have problems with math. I was able to write a `GetNext3mod4PrimeI()` function with it. Any better name for it? – mortytheshorty Mar 12 '23 at 22:42

0 Answers0