如何在C语言中编写哈希函数？

Question

哈希表被称为存储和检索数据的最快/最佳方式。

我对哈希表和散列的理解如下（如果我错了，请纠正我，如果有更多内容，请添加）：

• 哈希表只是一个数组（单维或多维）用于存储值。
• 散列是查找数组中插入/检索数据的索引/位置的过程。将数据项作为键传递给哈希函数，就可以得到要插入/检索数据的索引/位置。

我有一个问题：

用于存储/检索数据的哈希函数是否与用于身份验证等安全应用程序中的加密哈希函数（例如MD5、HMAC、SHA-1等）不同？

它们有何不同之处？

• 如何在C语言中编写哈希函数？
• 有没有一些标准或准则？
• 如何确保哈希函数的输出即索引不超出范围？

如果您能提供一些了解这些问题的好链接，那就太棒了。

- aks

---

范围可以通过模块（%）运算符进行限制。 - tur1ng

以下页面提供了多种通用哈希函数的实现，使用C语言以及其他许多语言编写：http://partow.net/programming/hashfunctions/index.html - Matthieu N.

Answer 1

一个加密哈希的重点是使任何人故意创建碰撞都变得困难。对于哈希表来说，重点通常在于快速地生成合理分布的结果。因此，两者通常有很大不同（特别是，加密哈希通常要慢得多）。

对于典型的哈希函数，其结果仅受类型限制--例如，如果它返回size_t，则它可以返回任何可能的size_t。你需要将输出范围缩小到表的大小（例如，使用除以表的大小的余数，该值通常应为质数）。

作为示例，一个相当典型的普通哈希函数可能看起来像：

// warning: untested code.
size_t hash(char const *input) { 

    const int ret_size = 32;
    size_t ret = 0x555555;
    const int per_char = 7;

    while (*input) { 
        ret ^= *input++;
        ret = ((ret << per_char) | (ret >> (ret_size - per_char));
   }
   return ret;
}

基本思路是让输入字符串的每一个位都影响结果，并且尽可能快地使结果的每一位都受到输入的至少一部分的影响。请注意，我并不特别推荐这作为一个很好的哈希函数 - 只是试图阐述一些你试图完成的基础知识。

- Jerry Coffin

---

密码哈希函数不一定很慢。特别是，MD4哈希函数据报道在某些平台上（例如基于ARM）比CRC32更快。然而，密码哈希函数往往具有较大的固定开销，这意味着对于小输入消息它们会变慢。当输入大小超过1 KB左右时，像MD4这样的函数才能实现其非常高的处理带宽（在我的2.4 GHz英特尔CPU上达到600 MB/s以上）。仍然，在小型输入（小于54字节）的情况下，我的PC仍然可以每秒计算出800万个MD4（使用单个核心）。 - Thomas Pornin

@Thomas：首先，虽然CRC32可能相对快速，但大多数哈希函数则更快。其次，虽然它确实是作为加密哈希函数设计的，但MD4现在并不再符合要求。它已经被全面攻破多年了——生成碰撞的速度和生成原始哈希值的速度差不多。参见：http://www.stachliu.com/md4coll.c以获取一个实现案例。 - Jerry Coffin

我知道MD4已经被攻破，但对于非加密目的（我们正在讨论的那些），MD4还是相当不错的；如果故意碰撞是一个问题，那么根据定义，每个非加密哈希函数都被排除在外。当没有安全问题时，可以至少考虑使用MD4。一些点对点系统使用MD4来识别文件元素。至于快速但强大的加密函数，正在进行选择新函数的竞赛。有关详细信息，请参见http://en.wikipedia.org/wiki/NIST_hash_function_competition（我是其中一位候选人的合著者）。 - Thomas Pornin

@Thomas：你的说法是“加密哈希函数不一定很慢”。我的回复只是说MD4并不支持这个说法，因为它不是一个加密哈希函数。 - Jerry Coffin

Answer 2

Bob Jenkins撰写了一篇深入的描述，介绍了他的良好但略显过时的哈希函数。该文章链接到更新、更好的哈希函数，但是这篇文章解决了构建一个好的哈希函数的问题。

此外，大多数哈希表实现实际上使用链表数组来解决碰撞。如果您想只使用数组，则哈希函数需要检查碰撞并创建一个新的哈希索引。

您提到的加密哈希函数可以用作哈希表的哈希函数，但它们比为哈希表设计的哈希函数慢得多。速度使暴力攻击更容易。

- RossFabricant

Answer 3

设计目标不同。

使用密码哈希函数时，您希望哈希和哈希函数不能用于确定原始数据或任何其他会产生相同哈希的数据。

与哈希表和其他数据结构一起使用的哈希函数不需要这样的安全属性。如果哈希函数快速且能将输入集均匀地分布到可能哈希的集合中（以避免不必要的聚类/冲突），通常就足够了。

- Anssi