字符串的哈希函数-Java 学习之路

我们目前正在处理我 class 的哈希函数 . 我们的教练要求我们在互联网上使用哈希函数来与我们在代码中使用的两个函数进行比较 .

第一个：

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问题，但是并不确定在哈希函数中要查找什么 . 如果我理解正确，在我的情况下，哈希采用输入（字符串）并进行数学计算以为字符串分配数字并将其插入表中 . 这个过程是为了提高搜索列表的速度吗？

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

5 回答

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

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

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

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

许多软件库为您提供了足够好的散列函数，例如Qt有qhash，C11在 <functional> 中有std::hash，Glib在C中有几个hash functions，POCO有一些hash函数 .

我经常有散列函数涉及素数（参见Bézout's identity）和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实现，以了解哈希函数的功能 .

关于算法的大多数优秀书籍至少有一章致力于散列 . 从hash function＆hash table开始使用wikipages .
回复于 2024-04-26T11:50:00+08:00

-- The way to go these days --

使用SipHash . 为了您自己的保护 .

-- Old and Dangerous --

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

问谷歌“通用哈希函数”

回复于 2024-04-26T11:50:00+08:00

2
用于算法使用的散列函数通常有2个目标，首先它们必须快速，其次它们必须在可能的数字上均匀地分配值 . 散列函数还需要为相同的输入值赋予所有相同的数字 .

如果你的值是字符串，这里有一些坏哈希函数的例子：
- string[0] - ASCII字符a-Z比其他字符更频繁
- string.lengh() - 最可能的值是1
好的散列函数尝试使用输入的每一位，同时保持最小的计算时间 . 如果您只需要一些哈希码，请尝试将字节与素数相乘，然后求和 .
回复于 2024-04-26T11:50:00+08:00

使用boost::hash

#include <boost\functional\hash.hpp>

...

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

回复于 2024-04-26T11:50:00+08:00

Java的String implements hashCode like this：

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

回复于 2024-04-26T11:50:00+08:00

字符串的哈希函数

5 回答

相关问题