为 6 字节字符串创建更快的完美哈希函数

Question

我有格式为 cccnnn 的 6 字节字符串，其中 c 是字符 A-Z (ASCII 65-90)，n 是字符 0-9 (ASCII 48- 57).一共有26³ * 10³ = 17,576,000种不同的组合。

我想创建一个完美的哈希函数，将这种类型的每个字符串映射到一个整数索引，我希望它尽可能快。功能不一定要极小，但范围不能太大。组合数量的两倍可能没问题，但最好不要超过这个数量，因为每个字符串都将映射到已经 ~2MB 的位数组中的一个位。

我能想到的最明显也是迄今为止最好的解决方案是将字符串解释为以 26 和 10 为基数的数字，然后进行所需的乘法和减法运算以得到 [0, 17576000-1]:

inline word hash1(unsigned char *buffer) 
{
  return (((((word) buffer[0]  * 26 + buffer[1]) * 26 
                  + buffer[2]) * 10 + buffer[3]) * 10 
                  + buffer[4]) * 10 + buffer[5]  - 45700328;
}

这里buffer[0-5]包含字符索引，word是uint64_t和45700328 = ((((65*26+65)*26+65)*10+48)*10+48)*10+48的typedef，它将字符转换为正确的基数写 (buffer[0] - 65) * 26 等（它节省了一些减法。）

我想到了改进的方法。我的一个想法是使用相同的原理，但使用移位而不是乘法。我不得不混合字符的顺序，以找到一个操作尽可能少的解决方案。我发现乘以 260 和 10 只需要两次移位和一次加法，分别是 (x << 8) + (x << 2) 和 (x << 3) + (x << 1)，我可以用它来分别计算表达式 ((x2*260+x1)*260+x0)*10+(x4*260+x3)*260+x5-47366978 中的每个乘法，其中 hi = buffer[i]。执行是：

inline word hash1(unsigned char *buffer)
{
  word y0, y1, y2, y3, y4;
  word x0 = buffer[0]; word x1 = buffer[1]; 
  word x2 = buffer[2]; word x3 = buffer[3]; 
  word x4 = buffer[4]; word x5 = buffer[5];
  y0 = (x4 << 2) + (x4 << 8) + x3;
  y1 = (y0 << 2) + (y0 << 8) + x5;
  y2 = (x2 << 2) + (x2 << 8) + x1;
  y3 = (y2 << 2) + (y2 << 8) + x0;
  y4 = (y3 << 3) + (y3 << 1) + y1;
  return y4 - 47366978;
}

不幸的是，hash2 比 hash1 慢一点。这是我运行出的好主意。我当然可以尝试制作一个简单地移动每个字符的有效位的函数，将它们堆叠在一起，形成一个 2²⁷ 位数，但这需要一个 16MB 的向量= 太大了。

那么，无论是使用相同的原理并更改代码，还是使用完全不同的原理，我如何才能根据我在第一段？

Answer 1

这是我对散列问题的看法。方法是少用中间值，多用常量，方便编译器优化代码。

#include <stdio.h>
#include <stdint.h>

uint64_t hash1(unsigned char *buffer)
{
  return
  (
    (
      (
        (
          (uint64_t)
            buffer[0] * 26
          + buffer[1]
        ) * 26
        + buffer[2]
      ) * 10
      + buffer[3]
    ) * 10
    + buffer[4]
  ) * 10
  + buffer[5]
  - 45700328;
}

uint64_t hash2(const unsigned char *buffer)
{
    uint64_t res
            = buffer[0] * 676000
            + buffer[1] * 26000
            + buffer[2] * 1000
            + buffer[3] * 100
            + buffer[4] * 10
            + buffer[5] * 1;
    return res - 45700328u;
}

int main(void)
{   
  unsigned char a, b, c, d, e, f;
  unsigned char buf[7] = { 0 }; // make it printable
  uint64_t h1, h2;


  for (a = 'A'; a <= 'Z'; a++) {
    buf[0] = a;
    for (b = 'A'; b <= 'Z'; b++) {
      buf[1] = b;
      for (c = 'A'; c <= 'Z'; c++) {
        buf[2] = c;
        for (d = '0'; d <= '9'; d++) {
          buf[3] = d;
          for (e = '0'; e <= '9'; e++) {
            buf[4] = e;
            for (f = '0'; f <= '9'; f++) {
              buf[5] = f;
              h1 = hash1(buf);
              h2 = hash2(buf);
              if (h1 != h2) {
                printf("Meh: %s mismatch: %llx %llx\n", (const char *)buf,
                  (unsigned long long)h1, (unsigned long long)h2);
                return 1;
              }
            }
          }
        }
      }
    }
  }

  return 0;
}

一些简单的 gprofing 表明 hash2() 速度更快，至少大多数时候是这样。每个运行的 gprof 结果略有不同。你可能想自己试验一下。

Answer 2

使用 3 个 A-Z 的 5 个最低有效位并将数字乘以 10 位乘积：2^{15 + 10} < 2*17,576,000。

如果 << 比 * 快，预计会更快。 YMMV

使用 const 指针可以进行可能尚未全部就绪的优化。

inline size_t hash3x26k(const unsigned char *buf) {
  return 0x1FFFFFF
      & (((buf[0] << 20) ^ (buf[1] << 15) ^ (buf[2] << 10))
          ^ ((buf[3] * 100 + buf[4] * 10 + buf[5])));
}

测试代码以显示完美的哈希值，并且需要不超过 2x 26³ * 10³ 个条目。

unsigned char z[0x1FFFFFF + 1u];

int main() {
  size_t max = 0;
  unsigned char b[7] = { 0 };
  for (b[0] = 'A'; b[0] <= 'Z'; b[0]++) {
    for (b[1] = 'A'; b[1] <= 'Z'; b[1]++) {
      for (b[2] = 'A'; b[2] <= 'Z'; b[2]++) {
        for (b[3] = '0'; b[3] <= '9'; b[3]++) {
          for (b[4] = '0'; b[4] <= '9'; b[4]++) {
            for (b[5] = '0'; b[5] <= '9'; b[5]++) {
              size_t i = hash3x26k(b);
              if (i > max) max = i;
              //printf("%s %zu\n", b, i);
              if (z[i]++) {
                printf("%s %zu\n", b, i);
                exit(-1);
              }
            }
          }
        }
      }
    }
  }
  printf("%zu\n", max + 1);
  return 0;
}

需要 29,229,056 个桶。

Answer 3

[更新 10/27]

一种简单的方法是将 48 位数组用作整数，然后按特定数字 mod。可以使用原始 ASCII 字符串。不需要从每个字符中减去 26 或 10，甚至不需要删除 '\n'。不需要任何乘法。只需 1 % 次操作。

typedef union {
  unsigned char b[8];
  uint64_t u64;
} U;

// Return a value in the range 0 to 33,541,273 which is less than 2*26*26*26*10*10*10
inline uint32_t hash3x26_mod(const unsigned char *buf) {
  static const uint32_t mod = 0X1FFCC9A;  // Determined by tests, assume little endian.
  return (uint32_t) (x->u64 % mod);
}

用法

fgets(&U.b, sizeof U.b, istream);
// Assume U.b[7] == 0
// Assume U.b[6] == 0 or `\n`, consistently 
uint32_t perfect_AAA000_hash = hash3x26k_1(&U);

或者，尽管 OP 不想使用更宽的索引，但下面确实会快速生成一个具有 *、>> 和 [=17= 的 30 位非冲突哈希]

inline size_t hash3x26k_1(const unsigned char *buf) {
  typedef union {
    unsigned char b[6];
    uint64_t u64;
  } U;
  U *x = (U*) buf;
  uint64_t y = (x->u64 * (1ull + 16 + 16*16 + 16*16*8 + 16ull*16*8*8 + 16ull*16*8*8*8)) 
      >> 17;
  return (size_t) (y & 0x3FFFFFFF);
}

我怀疑乘以某个 TBD 常数并用 0x01FF_FFFF 掩码也可以。

为 6 字节字符串创建更快的完美哈希函数

Creating a faster perfect hash function for 6-byte strings

c

string

optimization

hash-function