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

Question

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

我对哈希表的理解,哈希如下(如果我错了请纠正我或者请添加如果还有更多):

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

我有个问题:

哈希函数是用于存储/检索数据DIFFERENT来自安全应用程序中使用的加密哈希函数,用于身份验证,如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;
}

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

Answer 2

鲍勃·詹金斯 (Bob Jenkins) 深入描述了他的哈希函数，该函数虽然有点过时，但很好。这篇文章提供了更新、更好的哈希函数的链接，但这篇文章解决了构建一个好的哈希函数的问题。

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

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