字符串的哈希函数

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多个单词的文本文件。

我看到了这篇问题，其中有几个代码示例，但我不确定在哈希函数中应该寻找什么。 如果我理解正确，在我的情况下，哈希将输入（字符串）进行数学计算以分配一个数字并将其插入表中。 这个过程是为了增加搜索列表的速度？

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

- Nick

---

您刚刚提供了2个答案来回答您的问题。 - Pubby

你的教练怎么能要求你分析两个哈希函数，他还没教过你有关哈希表/函数的任何内容呢？ - Seth Carnegie

有没有好的例子或资源？ [是的。]（http://en.wikipedia.org/wiki/Hash_function#Hash_function_algorithms） - Robᵩ

请参阅 https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed。 - Yann Droneaud

Answer 1

首先，在实践中通常并不太重要。大多数哈希函数都足够好。

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

你的第二个哈希函数可能会更好一些，因为它可能会将字符串“ab”与字符串“ba”分开。另一方面，它可能比第一个哈希函数慢一些。它可能与你的应用程序相关，也可能与你的应用程序无关。

我猜用于基因组字符串的哈希函数与用于电话数据库中的家庭名称的哈希函数是非常不同的。甚至一些字符串哈希函数更适合德语单词，而不是英语或法语单词。

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

我经常使用涉及质数（参见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 入手。

- Basile Starynkevitch

---

非常好的答案。+1 ... :) - hellodear

Answer 2

-- 现在的正确做法 --

使用SipHash，以保护自己。

-- 旧而危险 --

unsigned int RSHash(const std::string& str)
{
    unsigned int b    = 378551;
    unsigned int a    = 63689;
    unsigned int hash = 0;

    for(std::size_t i = 0; i < str.length(); i++)
    {
        hash = hash * a + str[i];
        a    = a * b;
    }

    return (hash & 0x7FFFFFFF);
 }

 unsigned int JSHash(const std::string& str)
 {
      unsigned int hash = 1315423911;

      for(std::size_t i = 0; i < str.length(); i++)
      {
          hash ^= ((hash << 5) + str[i] + (hash >> 2));
      }

      return (hash & 0x7FFFFFFF);
 }

向Google询问“通用哈希函数”。

- esskar

Answer 3

算法使用的哈希函数通常有两个目标，首先它们必须快速，其次它们必须将值均匀分配到可能的数字中。哈希函数还要求对于相同的输入值给出相同的数字。

如果您的值是字符串，则以下是一些糟糕的哈希函数示例：

1. string[0] - ASCII字符a-Z比其他字符更常见
2. string.lengh() - 最可能的值是1

好的哈希函数尝试在保持计算时间最小的同时使用输入的每个位。如果您只需要一些哈希代码，请尝试使用素数乘以字节并将它们相加。

- Evan Dark

Answer 4

C++中已经实现了一个用于std::string的哈希函数：

std::hash<std::string>

#include <iostream> // not actually required for the hash
#include <string>

auto main() ->int
{
    const std::string input = "Hello World!";
    const std::hash<std::string> hasher;
    const auto hashResult = hasher(input);
    
    std::cout << "Hash for the input is: " << hashResult << std::endl;
}

在这里运行此代码：https://onlinegdb.com/33KLb91ku。

- Adrian Maire

Answer 5

使用 boost::hash。

#include <boost\functional\hash.hpp>

...

std::string a = "ABCDE";
size_t b = boost::hash_value(a);

- Denise Skidmore

---

在Linux上，#include指令中的反斜杠可能无法正常工作，因此您的代码可能是Windows特定的（或者您应该将反斜杠改为斜杠）。 - Basile Starynkevitch

这是关于哈希概念的学术问题，因此没有任何用处。 - Nick

Answer 6

Java 的 String 实现 hashCode 的方式如下：

public int hashCode()

Returns a hash code for this string. The hash code for a String object is computed as

     s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.) 

就像这样：

int HashTable::hash (string word) {
    int result = 0;
    for(size_t i = 0; i < word.length(); ++i) {
        result += word[i] * pow(31, i);
    }
    return result;
}

- Brendan Long

---

我认为Java使用C级移位来计算该值，而不是直接计算表达式。31=32-1，因此31^k=(32-1)^k=(-1)^k+232(-1)^(k-1) ... 32^k；由于32=2^5，32^7 > sizeof(int)，所以你只需要计算前6个和即可，甚至可以通过移位进行计算。与使用pow()相比，这样速度更快，因此除非你愿意优化一些计算，否则不要这么做。 - Evan Dark