f448() - Another Tabulation Hash Function to implement a consistent Hash Ring
 
 

f448() - Another Tabulation Hash Function to implement a consistent Hash Ring

May 4, 2025
development
algorithms, C, bngx, IXDP

f448() #

f448() is another tabulation hashing function which maps two uint32_t to an uniform hash result of type uint64_t. This is being used to implement a skiplist based consistent hash ring with 2^64 possible ring slots (or positions).

The Implementation #

The implementation is similar to f82, the random data has also been retrieved from the Quantis QRNG device.

Instead of compressing or expanding, this hash function performs a mapping from a 2^64 input space to an equally sized 2^64 output space.

The input is hereby divided in two 32 bit parts, one of them representing a server ID, the other representing the label of this particular server ID entry. By inserting server ID entries multiple times with different labels, the label thus represents the weight of the server in the consistent hash distribution.

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

static uint64_t material[8 * 256];

uint64_t f448(uint32_t x, uint32_t y) {

  int i;
  uint64_t result;

  result = 0;

  for (i = 0; i < 4; i++) {
    result ^= *(material + i * 256 + *(((uint8_t *)&x) + i));
  }

  for (i = 4; i < 8; i++) {
    result ^= *(material + i * 256 + *(((uint8_t *)&y) + i - 4));
  }

  return (result);
}

static uint64_t material[8 * 256] = { 
  0xc08c0cd56e9b1cb3, 0x8c79af978ad2c02a, 0x5e3174f7886e33d1, 0x101edfe349747b09,
  0x6808355c268dff16, 0xb0c3c8ea0be2c2c0, 0x4d72ad2f2ad34386, 0x2b03c357d4714f4c,
  // true random data omitted
  0x7d558a89d92d79a0, 0xbe372889576ba61d, 0x98895746beb6580c, 0x5b783b1710447450,
  0x823b0d5d4c3eb4dd, 0xb7498666ea80dae6, 0x53cdb6b0885a1d58, 0xc93f2f6ae211f0d1
};

Resources #