c - 如何在 C 中编写哈希函数？

Question

哈希表据说是最快/最好的存储/检索数据的方法。

我对哈希表的理解，哈希如下(如有错误请指正，如有不足请补充):

• 哈希表只不过是一个用于存储值的数组(单维或多维)。
• 散列 是在数组中查找索引/位置以插入/检索数据的过程。您获取一个数据项并将其作为键传递给哈希函数，您将获得插入/检索数据的索引/位置。

我有一个问题:

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

它们有什么不同？

• 如何用 C 语言编写散列函数？
• 是否有一些标准或指南？
• 我们如何确保哈希函数的输出，即索引不超出范围？

如果您能提及一些好的链接以更好地理解这些内容，那就太好了。

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;
}

这里的基本思想是让输入字符串的每一位都影响结果，并且(尽可能快地)让结果的每一位至少受到部分输入的影响。请注意，我并不是特别推荐它作为一个很棒的散列函数——只是想说明您要完成的事情的一些基础知识。