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

nxowjjhe 于 2023-01-12 发布在其他

关注(0)|答案(3)|浏览(125)

我有6字节的字符串，格式为cccnnn，其中c是字符A-Z（ASCII 65-90），n是字符0-9（ASCII 48-57），总共有263 * 103 = 17，576，000种不同的组合。
我想创建一个完美的哈希函数，将这种类型的每个字符串Map到一个整数索引，我希望它尽可能快。函数不必是最小的，但范围不能太大。两倍的组合数量可能是好的，但最好不要超过这个数量，因为每个字符串将被Map到一个位数组中的一个位，而这个位数组已经是~ 2 MB。
我能想到的最明显、也是目前最好的解决方案是将字符串解释为以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慢一点，这就是我没有好主意的地方。我当然可以尝试做一个函数，简单地移动每个字符的有效位，将它们堆叠在一起，形成一个227位的数字，但这需要16 MB的向量=太大了。
那么，无论是使用相同的原理并改变代码，还是使用完全不同的原理，我如何才能使我的哈希函数按照我在第一段中提到的要求“更快”呢？

来源：https://stackoverflow.com/questions/40172468/creating-a-faster-perfect-hash-function-for-6-byte-strings

3条答案

按热度按时间

myzjeezk1#

一个简单的方法是将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不想使用更宽的索引，但下面的代码确实可以快速生成一个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进行掩码也可以。

赞(0）回复(0）举报 2023-01-12

i5desfxk2#

使用3 A-Z的5个最低有效位，并将这些数字相乘为10位乘积：215 + 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 263 * 103需要的条目。

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个铲斗。

赞(0）回复(0）举报 2023-01-12

nle07wnf3#

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

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

赞(0）回复(0）举报 2023-01-12

我来回答

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

3条答案

相关问题

热门标签

最新问答

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

3条答案

相关问题

热门标签

最新问答

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