字符串的哈希函数

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

我用一些代码示例看到了这个问题,但是并不确定在哈希函数中要查找什么.如果我理解正确,在我的情况下,哈希采用输入(字符串)并进行数学计算以为字符串分配数字并将其插入表中.这个过程是为了提高搜索列表的速度吗？

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

Answer 1

首先,它在实践中通常无关紧要.大多数哈希函数都"足够好".

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

你的第二个哈希函数可能稍好一些,因为它可能应该将字符串"ab"与字符串分开"ba".另一方面,它可能不如第一个散列函数快.它可能会或可能不会与您的申请相关.

我猜测用于基因组字符串的哈希函数与用于在电话数据库中哈希族名称的哈希函数完全不同.也许甚至一些字符串哈希函数更适合德语,而不是英语或法语单词.

许多软件库为您提供了足够好的散列函数,例如Qt具有qhash,而C++ 11具有std :: hash in <functional>,Glib 在C中具有多个散列函数,并且POCO具有一些散列函数.

我经常有散列函数涉及素数(见Bézout的身份)和xor,例如

#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实现,以了解哈希函数可以是什么.

关于算法的大多数优秀书籍至少有一章致力于散列.从哈希函数和哈希表上的wikipages开始.

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

问谷歌"通用哈希函数"