我如何将 djb2 映射到散列 table？

Question

我有一个作业（CS50 - 拼写器），我必须在其中使用链表实现哈希 table。然而，对于额外的挑战，我们也被要求实施哈希算法，我对哈希 tables 和哈希完全陌生，并且对密码学了解为 0；在阅读了一段时间后，我发现 djb2 hash 我认为它可以很好地处理我的数据集（143k 小写单词的字典（有些带有 '）），我必须使用它来拼写检查其他数据集。

分析数据集后，我最初的想法是将其拆分为前三个字母，然后有一个（我的数据集元素上总共有 3 个字母的变体）3 个字符的数组，其中包含一个二进制三链表的头部每个字。（我不能那样做，因为练习已经包含一个 sllist 结构和一个哈希函数的原型）

这当然是在了解到散列 table 之所以被称为散列之前，因为它们使用散列。我完全不知道如何进行。

我看到人们经常使用 mod % 将其映射到他们的列表，但这让我感到困惑，因为你怎么能保证那样不会有更多的碰撞以及会发生什么最小化它们的最佳数组大小？

如何将 djb2 函数的结果映射到散列 table？我的情况有更好的方法吗？

Answer 1

您使用模数。如果你说大小总是 2 的幂，那么你也可以使用按位与计算相同的东西。

how can you guarantee that there wont be more collisions that way AND what would be the optimal array size to minimize them?

你不能。没人知道。除了它应该尽可能大，但不要大到用尽你所有的内存。

哈希 table 从根本上讲是概率数据结构。没有办法确保它们在各个方面都是 100% 完美的。您只能获得“足够完美”，这通常是 95% 的完美程度。如果你 5% 的水桶里有两件东西……大不了，谁在乎呢。 95% 的时间你只需要检查一项，5% 的时间你仍然只需要检查两项。

每个散列 table 都可能发生冲突。如果它是一个很好的散列函数，那么项目完全随机地进入桶中 - 就像任何人都可以说的那样接近。如果您有 5 件物品和 10 个桶，则桶 1 中有物品的可能性约为 50%（实际上为 41%）。它有大约 7% 的几率有 2 件物品。它有大约 0.8% 的几率有 3 个项目。

处理这个问题的方法是确保你的散列table可以在同一个桶中有多个项目，但它不必要快，因为它不会经常发生。链表是一种方式。更好的方法（因为 CPU 缓存）是使用下一个存储桶，这称为 开放寻址 ，但它很复杂。

如果您开始将 10 件物品放入 10 个桶中，这些概率会迅速上升。为了确保概率保持在低水平，大多数哈希tables 将在它们“满”的大约 50% 到 75% 时扩大它们的大小（当项目数除以桶数，超过一些他们在 0.5 和 0.75 之间选择的数字）。

如果您的哈希函数不好，您也可以在一个桶中存放大量物品，例如

int hash(const char *s) {return 0;}

会将每个项目放入同一个桶中，无论您的散列 table 尝试如何分配它们 - 无论它使用模数还是其他方式。这就是为什么一个好的哈希函数是必不可少的。

Answer 2

关于哈希函数，我相信您需要了解三件事：

您想将一个 N 字节字符串压缩为一个 int 数字。
您想进一步将那个 int 数字简化为散列中“桶”的数量 table。选择的工具当然是模运算符，%.
要真正做到这一点出奇地困难，但如果您刚刚起步，即使是糟糕的哈希函数也能做到。

#1 有很多种方法。您可以将字符串中字符的字节值相加：

unsigned int hash1(const char *str)
{
    unsigned int hash = 0;
    unsigned char *p;
    for(p = str; *p != '[=10=]'; p++)
        hash += *p;
    return hash;
}

或者您可以对字符串中字符的字节值进行异或操作：

unsigned int hash2(const char *str)
{
    unsigned int hash = 0;
    unsigned char *p;
    for(p = str; *p != '[=11=]'; p++)
        hash ^= *p;
    return hash;
}

（跳到第 3 点，这两者最终都非常糟糕，但暂时还可以。）

在调用者中，您通常采用这些人之一的 return 值，并使用 % 将其转换为散列的索引 table:

#define HASHSIZE 37
HashtabEnt hashtab[HASHSIZE];

// ...

unsigned ix = hash(string) % HASHSIZE;
x = hashtab[ix];

// ...

然后最大的问题是，如何编写好的散列函数？这实际上是一个具有相当大的和持续的理论兴趣的领域，我不是专家，所以我不会试图给你一个完整的治疗。至少您需要确保输入的每个字节对输出都有影响。理想情况下，您希望能够生成完全覆盖输出范围的值。优选地，它将生成覆盖具有合理均匀分布的输出范围的输出值。如果您需要加密安全散列，您将有额外的要求，但对于简单的字典式散列，您不必担心这些。

我上面的函数 hash2 很糟糕，因为它从不生成大于 255 的散列值（即超过 8 位，因此它可能无法“完全覆盖输出范围”）。 hash1 也好不了多少，因为除非输入字符串很大，否则它不会超过 8 位。一个简单的改进是结合移位和异或：

unsigned int hash3(const char *str)
{
    unsigned int hash = 0;
    unsigned char *p;
    for(p = str; *p != '[=13=]'; p++)
        hash = (hash << 1) ^ *p;
    return hash;
}

但这也不好，因为它总是向左移位，这意味着最终的散列值最终只是最后几个输入字节的函数，而不是所有输入字节的函数——也就是说，它在“输入的每个字节对输出都有影响”时失败。

所以另一种方法是进行循环移位，然后对下一个字节进行异或运算：

unsigned int hash4(const char *str)
{
    unsigned int hash = 0;
    unsigned char *p;
    for(p = str; *p != '[=14=]'; p++)
        hash = ((hash << 1) & 0xffff | (hash >> 15) & 1) ^ *p;
    return hash;
}

这是Unix "sum" command使用的传统算法。

我如何将 djb2 映射到散列 table？

How would I map djb2 to a hash table?

c

hash

hashmap

hashtable

cs50