c++ - 字符串的哈希函数

Question

我们目前正在类里面处理哈希函数。我们的讲师要求我们在互联网上使用一个哈希函数来与我们在代码中使用的两个函数进行比较。

第一个:

int HashTable::hash (string word)   
// POST: the index of entry is returned
{       int sum = 0;
        for (int k = 0; k < word.length(); k++)
            sum = sum + int(word[k]);
        return  sum % SIZE; 
}

第二:

int HashTable::hash (string word)
{
   int seed = 131; 
   unsigned long hash = 0;
   for(int i = 0; i < word.length(); i++)
   {
      hash = (hash * seed) + word[i];
   }
   return hash % SIZE;
}

其中 SIZE 为 501(哈希表的大小)，输入来自 20,000 多个单词的文本文件。

我看到了this有几个代码示例的问题，但不完全确定要在哈希函数中寻找什么。如果我理解正确，在我的情况下，哈希接受一个输入(字符串)并进行数学计算，为字符串分配一个数字并将其插入表中。这样做是为了提高搜索列表的速度吗？

如果我的逻辑是合理的，是否有人有一个很好的例子或资源显示涉及字符串的不同哈希函数？甚至是我自己编写高效哈希函数的过程。

Answer 1

首先，在实践中通常没有那么重要。大多数哈希函数都“足够好”。

但如果你真的在乎，你应该知道它本身就是一个研究课题。关于这方面的论文有数千篇。通过学习和设计哈希算法，您今天仍然可以获得博士学位。

您的第二个哈希函数可能会稍微好一些，因为它可能应该分隔字符串 "ab"来自字符串 "ba" .另一方面，它可能不如第一个哈希函数快。它可能与您的应用相关，也可能不相关。

我猜想用于基因组字符串的散列函数与用于在电话数据库中散列姓氏的散列函数完全不同。甚至一些字符串哈希函数更适合德语，而不是英语或法语单词。

许多软件库都为您提供了足够好的哈希函数，例如Qt 有 qhash ，而 C++11 有 std::hash在 <functional> , Glib 有几个 hash functions在 C 中，和 POCO有一些hash功能。

我经常使用涉及素数(见 Bézout's identity)和异或的散列函数，例如

#define A 54059 /* a prime */
#define B 76963 /* another prime */
#define C 86969 /* yet another prime */
#define FIRSTH 37 /* also prime */
unsigned hash_str(const char* s)
{
   unsigned h = FIRSTH;
   while (*s) {
     h = (h * A) ^ (s[0] * B);
     s++;
   }
   return h; // or return h % C;
}

但我并不声称自己是哈希专家。当然，A 的值, B , C , FIRSTH最好是素数，但你也可以选择其他素数。

看一些MD5实现以了解散列函数可以是什么。

大多数关于算法的好书至少有一整章专门介绍哈希。从 hash function 上的维基页面开始& hash table .