Hash function in C for sets and associative arrays

Question

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.

Answer 1

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