27

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

我对散列表的理解，散列如下（如有错误请指正或如有补充请补充）：

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

我有个问题：

用于存储/检索数据的散列函数是否不同于安全应用程序中用于验证的加密散列函数，如 MD5、HMAC、SHA-1 等...？

它们在哪些方面不同？

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

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

4

3 回答 3

11

加密哈希强调让任何人都难以故意制造冲突。对于哈希表，重点通常是快速产生合理的结果分布。因此，两者通常完全不同（特别是，加密哈希通常要慢得多）。

对于一个典型的散列函数，结果仅受类型的限制——例如，如果它返回一个 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;
}

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

于 2010-02-10T15:54:31.263 回答
4

Bob Jenkins 写了一篇关于他的好（虽然有点过时）的哈希函数的深入描述。这篇文章有更新、更好的哈希函数的链接，但这篇文章解决了构建一个好的哈希函数的问题。

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

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

于 2010-02-10T15:50:40.807 回答
0

设计目标不同。

例如，对于加密散列函数，您希望散列和散列函数不能用于确定原始数据或任何其他会产生相同散列的数据。

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

于 2010-02-10T21:42:54.553 回答