f82() - A Hash Function with strong theoretical Properties
 
 

f82() - A Hash Function with strong theoretical Properties

April 2, 2025
development
algorithms, C

f82() #

f82() is hash function which hashes (or maps) a unt64_t 8 byte unsigned integer key to a uint16_t 2 byte hash value. It belongs to the class of tabulation hashing functions and is perfect for implementing lock-less hash tables and other data structures that require an uniform and perfect distribution.

The Implementation #

The implementation is straightforward, most importantly: The random material needs to be from a high quality random number generator (in our case we retrieved it from the Quantis QRNG device).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

static uint16_t material[8 * 256];

uint16_t f82(uint64_t n) {
  int i;
  uint16_t result;

  for (i = 0, result = 0; i < 8; i++) {
    result ^= *(material + i * 256 + *(((uint8_t *)&n) + i));
  }

  return (result);
}

static uint16_t material[8 * 256] = {
  0xdc71, 0x5b4e, 0x1c58, 0x05df, 0xb815, 0x88fb, 0xea24, 0x12e2,
  0x41fe, 0x34fe, 0x22b4, 0xe9a1, 0x5fec, 0x104a, 0xffce, 0x3a86,
  0xa819, 0xe974, 0xe42a, 0xf0ca, 0xaece, 0xc71e, 0x84a2, 0xb895,
  0x34d8, 0xe545, 0x361f, 0x5db7, 0x6afc, 0x1dd7, 0xef66, 0xd3b7,
  // true random data omitted
  0xa8fb, 0x87c7, 0x109e, 0x5f7e, 0x8d68, 0xc49a, 0x0a87, 0xc77f,
  0xe508, 0x6806, 0xe641, 0xd138, 0xc7df, 0x178d, 0x7f19, 0xb823,
  0xda12, 0xcb14, 0x4835, 0xcef0, 0x98d2, 0xea02, 0xfc46, 0xef3a,
  0x1121, 0x72ca, 0x54a8, 0x0019, 0x6e8d, 0x8a82, 0xb96f, 0x2ae2
};

4-Independency? #

Despite its simplicity, tabulation hashing has strong theoretical properties that distinguish it from some other hash functions. In particular, it is 3-independent: every 3-tuple of keys is equally i likely to be mapped to any 3-tuple of hash values. However, it is not 4-independent.

What does this actually mean?

As Pătraşcu & Thorup (2012) observe, tabulation hashing is 3-independent but not 4-independent. For any single key x, T[x0,0] is equally likely to take on any hash value, and the exclusive or of T[x0,0] with the remaining table values does not change this property. For any two keys x and y, x is equally likely to be mapped to any hash value as before, and there is at least one position i where xi ≠ yi; the table value T[yi,i] is used in the calculation of h(y) but not in the calculation of h(x), so even after the value of h(x) has been determined, h(y) is equally likely to be any valid hash value. Similarly, for any three keys x, y, and z, at least one of the three keys has a position i where its value zi differs from the other two, so that even after the values of h(x) and h(y) are determined, h(z) is equally likely to be any valid hash value.

This RPCL example dialog shows this dependency between 0xaaaa, 0xaabb, 0xbbaa and 0xbbbb (XORing the 4 results is always 0 - independent of the random material in place):

$ rpclsh
ok ".f82" @ .
returns f82() result in hex ( u64x - result )
ok ".f82-4" @ .
returns XOR of 4 f82() results in hex ( h0 h1 h2 h3 - result )
ok aaaa .f82 .
6BE6
ok aabb .f82 .
E7F
ok bbaa .f82 .
644
ok bbbb .f82 .
63DD
ok aaaa aabb bbaa bbbb .f82-4 .
0
ok

For the mentioned and intended purposes this lack of 4-independency is neglectable.

Resources #