0

In a hash table implementation in C, I am relying on the mod operator to transform my hash of the key by the capacity of the hash table as follows:

int i = compute_index(key, hash, capacity);

while(table[i].occupied && (strcmp(table[i].key, key) != 0))
{
    ...

The hash seems to be computed correctly, because in my debugger, I am able to utilize the hash function and the key to output -724412585.

enter image description here

The strange thing is, when I mod this number by the capacity using a regular calculator, I get 7. But within the debugger, and my code, the integer -1 is returned. This is very confusing and I would appreciate some help.

My compute_index() simply does this:

int compute_index(const char* key, int (*hash)(const char*), int cap)
{
    return hash(key) % cap;
}

Would appreciate some guidance, thank you.

doomblah
  • 77
  • 2
  • 10
  • 5
    Usually you would want a hash to be an unsigned int. Or even an unsigned long, since int might not be very wide. – rici Nov 27 '17 at 05:04
  • 1
    https://stackoverflow.com/questions/4003232/how-to-code-a-modulo-operator-in-c-c-obj-c-that-handles-negative-numbers, https://stackoverflow.com/questions/24074869/why-is-the-behavior-of-the-modulo-operator-different-between-c-and-ruby-for, https://stackoverflow.com/questions/828092/python-style-integer-division-modulus-in-c – melpomene Nov 27 '17 at 05:12
  • The correct type to use for the hash function is `size_t` and nothing else, since this type will most likely be used as look-up index in an array. – Lundin Nov 27 '17 at 10:32

2 Answers2

1

There are two common conventions for the sign of a % b: in one case, the sign is the same as b (i.e. always positive when b is positive), and in the other case it's the same as a (i.e. negative when a is negative). Older versions of C allowed either behavior, but C99 and later require the second behavior (which goes hand-in-hand with requiring truncating division, rather than leaving the choice of truncating or flooring division up to the compiler).

The upshot of this is that if your hash function can return a negative number, then hash(key) % cap will also be negative sometimes. The simplest thing you can do is to alter hash to return unsigned int instead of int.

hobbs
  • 223,387
  • 19
  • 210
  • 288
  • @M.M sorry, massive thinko when I was writing that. Corrected :) – hobbs Nov 27 '17 at 08:18
  • In case this is the reason for the error, then the question is a duplicate of [What is the behavior of integer division?](https://stackoverflow.com/questions/3602827/what-is-the-behavior-of-integer-division). – Lundin Nov 27 '17 at 10:35
0

I agree w/ everything @hobbs said, except for the following:

I believe the easiest thing you can do is either:

  • change the output of hash() to unsigned int,
  • or cast the output of hash() to unsigned int within the body of compute_index() before the modulo operation, or
  • add the modulus back in if the result of the % operation < 0 (to get the abstract-algebraic sense of "integer mod q").

The behavior of % in C for negative numbers can be confusing to those with a background in abstract algebra, particularly for one who works with the rings of integers mod q.

lockcmpxchg8b
  • 2,205
  • 10
  • 16