CODEWITHSUNDEEP
chashhashtable
doomblah
doomblah

Reputation: 77

Using the mod operator correctly in C

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.

Upvotes: 0

Views: 1002

Answers (2)

hobbs
hobbs

Reputation: 240030

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.

Upvotes: 1

lockcmpxchg8b
lockcmpxchg8b

Reputation: 2303

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.

Upvotes: 0

Related Questions