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

我有格式为cccnnn的6字节字符串，其中c是字符a-Z（ASCII 65-90）和n是字符0-9（ASCII 48-57）总共有263*103=17576000种不同的组合。
我想创建一个完美的散列函数，将这种类型的每个字符串映射到一个整数索引，我希望它尽可能快函数不必是最小的，但范围不能太大。两倍的组合可能是可以的，但最好不要超过这个数目，因为每个字符串将映射到一个已经~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是typedef和uint64_t的45700328 = ((((65*26+65)*26+65)*10+48)*10+48)*10+48，它将字符转换为正确的基而不是写入(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慢一点。这就是我没有好主意的地方。当然，我可以尝试制作一个函数，简单地移动每个字符的有效位，将它们叠加在一起，形成一个227位的数字，但这需要16MB的向量=太大。
那么，无论是使用相同的原则和更改代码，还是使用完全不同的原则，我如何才能根据第一段中提到的要求使哈希函数更快？

最佳答案

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

#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结果都有所不同你可能想试验一下自己。

关于c - 为6字节字符串创建更快的完美哈希函数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40172468/