0
\$\begingroup\$

I wrote a non-cryptographic hash function in C, which I am hoping might be suitable for use in an implementation of hash sets or hash maps.

uint_fast32_t hash_u32(uint_fast32_t x) {
    uint_fast32_t h = x;
    h = h ^ (h>>16);
    h = h * 0xae6a495b;
    h = h ^ (h<<16);
    h = h * 0xae6a495b;
    return h;
}

I've tested this integrated into a set implementation before, which can be seen here, and it seems to be working fine, but I'm interested in knowing whether this is a good approach to integer hashing, or general hashing assuming all problem domains can be reduced to map the value to an integer and then hash that.

\$\endgroup\$
  • 2
    \$\begingroup\$ Could you explain why you're hashing a uint_fast32_t to uint_fast32_t? That doesn't appear to gain you anything unless you further reduce the range (e.g. by slicing). What's the intent? \$\endgroup\$ – Toby Speight Sep 21 '18 at 12:31
  • \$\begingroup\$ The intent is to scramble patterns input which would cause collisions especially at small table sizes. For instance, if I ended up needing set of the first 16 powers of two and happened to have a table size of 32 at this time, most of the values would have a first choice location of the first slot in the underlying array. \$\endgroup\$ – Quinn Mortimer Sep 22 '18 at 5:20
  • \$\begingroup\$ Ah, so it's a transformation prior to reduction. In which case, we really need to know how you'll be reducing the result to fit your table size to say anything very meaningful about it. \$\endgroup\$ – Toby Speight Sep 25 '18 at 7:48
  • \$\begingroup\$ With the modulo operation. Is that the information you were looking for? \$\endgroup\$ – Quinn Mortimer Sep 28 '18 at 1:02
  • \$\begingroup\$ Yes, that's the important information - please edit to mention that (and how you choose the other argument to % - e.g. will it always be prime?). \$\endgroup\$ – Toby Speight Sep 28 '18 at 7:39
4
\$\begingroup\$

... in knowing whether this is a good approach ...

Small improvements

Keep in range

uint_fast32_t may be wider than 32 bits. Values outside the 32-bit range in x will have a result that depends on those excessive upper bits. I'd suggest coding to insure 1) only the lower 32 are used to form the answer and 2) the answer only has lower 32-bits set. #2 being an important aspect here - don't generate results outside 32-bits. When uint_fast32_t is 32-bit, a good compiler will optimize away the & 0xFFFFFFFF masks.

uint_fast32_t h = x & 0xFFFFFFFF;
...
return h & 0xFFFFFFFF;

Readability

Style issue:

I find reading hexadecimal constants easiest to read when the case of the x differs from the digits.

// h = h * 0xae6a495b;
h = h *    0xAE6A495B;

Avoid naked magic numbers.

I did not note the 2 hex constants were the same until a bit later. Defines/const objects would have helped and self-document the code.

const uint_fast32_t hash_m = 0xAE6A495B;
const uint_fast32_t uint32_mask = 0xFFFFFFFF;
const unsigned hash_shift = 16;

uint_fast32_t h = x & uint32_mask;
h = h ^ (h >> hash_shift);
h = h * hash_m;
h = h ^ (h << hash_shift);
h = h * hash_m;
return h & uint32_mask;

Why 32 for a general approach?

With "good approach to integer hashing or general hashing" seems to assume an "integer" is 32 bits. Such an assumptions breaks the "general hashing". For a "general hashing" I would use unsigned or perhaps size_t and steer the constants based on the type's range. Either that or forgo the "general" adjective to this code and simply say its is designed for 32-bit as hash_u32() implies.

uint_fast32_t vs. uint32_t

uint_fast32_t has 2 advantages, 1) it always exists since C99 as uint32_t may not exist on rare machines that lack 32-bit types. 2) It may be "faster".

Yet uint_fast32_t is also problematic. It is more difficult to test. Proper function testing obliges a test on machines where uint_fast32_t is 32 and more than 32-bit as the above masking discussion points out potential pitfalls on the rarer wide uint_fast32_t.

I doubt code was written to take advantage of #1 (uint32_t may not exist).

Unless #1 is a design concern, best, especially for a "general" function, to stick to fixed width or regular types and reserve the "fast" types for internal function usage and not as a function parameter nor return value. Using "fast" as part of the function I/F, may be useful in select cases, but not "general".

Missing header

I'd expect #include <stdint.h> as part of the code to define uint_fast32_t, else code does not compile.


Good Hash?

I threw together a quick test to see how 32-bit values mapped to what.

Note: On my machine with a 64-bit uint_fast32_t, code died on flag[i] unless OP's function had h masked with h & 0xFFFFFFFF.

#include <stdint.h>
uint_fast32_t hash_u32(uint_fast32_t x) {
  uint_fast32_t h = x & 0xFFFFFFFF;
  h = h ^ (h >> 16);
  h = h * 0xae6a495b;
  h = h ^ (h << 16);
  h = h * 0xae6a495b;
  return h & 0xFFFFFFFF;
}

#include <assert.h>
#include <stdio.h>
void hash_u32_test(void) {
  _Static_assert(CHAR_BIT == 8, "CHAR_BIT != 8");
  unsigned char *flag = calloc(1, 1u << (32 - 3));
  if (!flag) return;
  uint32_t twice = 0;
  uint32_t x = 0;
  do {
    uint_fast32_t y = hash_u32(x);
    uint_fast32_t i = y / 8;
    uint_fast32_t j = y % 8;
    if (flag[i] & (1u << j)) {
      twice++;
    }
    flag[i] |= (1u << j);
    x++;
  } while (x);
  printf("twice %lu\n", (unsigned long) twice);
}

int main() {
  hash_u32_test();
  return 0;
}

My result was twice 0 implying a one-one mapping of all 32-bit inputs to output, so from a hash perspective, that is good for OP's function to pass.

\$\endgroup\$
  • \$\begingroup\$ re: "Why 32 for a general approach?" I am imagining the problem of hashing arbitrary types as mapping a value to an integral value with a fixed bit-width, then running my hash function over that. I could have tried to write this algorithm at any number of bits but picked 32. \$\endgroup\$ – Quinn Mortimer Sep 22 '18 at 5:31
  • \$\begingroup\$ re: "uint_32t vs. uint_fast32_t": This could be overcompensation on my part for how often a machine without uint32_t would run my software. \$\endgroup\$ – Quinn Mortimer Sep 22 '18 at 5:34
  • \$\begingroup\$ It's much easier to show that it's a bijective function: it's a composition of bijective steps. \$\endgroup\$ – harold Sep 22 '18 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.