c - 数组索引的散列

Question

在我的 C 程序中，我在结构中分配了四个 8 位 (char) 变量。如果我想对这些数字进行哈希处理以创建用于索引数组的键(代表整个结构)，我该怎么办？ (程序中有很多这样的结构；因为我经常必须在符号表中搜索它们是否存在，如果我不想创建其他结构，我不知道要使用哪种哈希算法，如果我想要进行键索引搜索)。

我考虑过一种哈希方法，它获取四个数字，将它们转换为十六进制数字，将它们连续放置，然后将得出的数字转换为十进制数字。

但是我需要一些不那么“重”的东西...这个方法似乎太徒劳了，而且我认为它不太适合创建数组索引。

是吗？是否有另一种哈希函数，如果可能的话，它占用的内存也少于 32 位？

Answer 1

您可能想看看这个list of hash functions .

为了实现哈希表(我想这是你的目标)，你需要一个带有 avalanche effect 的哈希函数。以避免相似输入值出现太多哈希冲突。

当然，您可以使用任何函数将字符转换为任意整数表示形式，但如果该表示形式不会因不同输入而变化，则您实际上拥有链表的性能(想象一下使用其他建议之一和表大小为 256，并且所有结构在字节 4 上都没有变化)。您对 32 位哈希有什么担忧？当然，您会使用 hash%tablesize 进行索引吗？

通常您也不会使用加密哈希函数(例如 md5、sha-1)。只需选择一种非加密哈希函数(例如 Pearson/Jenkins 哈希)。

/* jenkins hash, copied from http://en.wikipedia.org/wiki/Jenkins_hash_function */
uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
  uint32_t hash, i;
  for(hash = i = 0; i < len; ++i)
  {
    hash += key[i];
    hash += (hash << 10);
    hash ^= (hash >> 6);
  }
  hash += (hash << 3);
  hash ^= (hash >> 11);
  hash += (hash << 15);
  return hash;
}

旁注:当您拥有良好的哈希值分布时，还要确保哈希表的大小足够大。当数组的占用率(负载因子)接近 1 时，您将观察到性能下降，因为哈希冲突的可能性会增加。