如何使用C++将字符串哈希为整数？

Question

我需要编写自己的哈希函数。如果我想要简单的哈希函数，将字符串中的每个字母映射到数字值（例如a=1，b=2，c=3，...），是否有一种方法可以在不必先将其转换为C字符串以查看每个单独字符的情况下对字符串执行此哈希？有没有更有效的哈希字符串的方法？

- zebraman

Answer 1

根据个人经验，我知道这个方法行之有效且产生出良好的分布。（从http://www.cse.yorku.ca/~oz/hash.html盗用）：

djb2

这个算法（k=33）是由Dan Bernstein多年前在comp.lang.c上首次报告的。这个算法的另一个版本（现在被Bernstein青睐）使用异或运算：hash(i) = hash(i - 1) * 33 ^ str[i]；数字33的魔力（为什么它比许多其他常量，无论是否为质数，都运行得更好）从未得到充分的解释。

unsigned long hash(unsigned char *str) {
    unsigned long hash = 5381;
    int c;

    while (c = *str++) {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }

    return hash;
}

- Tim Cooper

Answer 2

关于第一个问题，当然可以，例如：

int hash = 0;
int offset = 'a' - 1;
for(string::const_iterator it=s.begin(); it!=s.end(); ++it) {
  hash = hash << 1 | (*it - offset);
}

关于第二个问题，有很多更好的方法来哈希字符串。例如，可以查看这里提供的一些C示例（可以轻松地按照上面代码片段的方式转换为C ++）。

- Alex Martelli

---

我明白了。如果我想要进行不区分大小写的哈希，该怎么办呢？比如A=a=1？ - zebraman

+1，即使只是为了使用*2和|来创建一个滑稽可笑的哈希值；-) - Steve Jessop

创建一个滑稽的弱哈希，得分为-1。使用符号'^'，而不是'|'！即使使用'^'，对于短字符串，这仍会导致更多的碰撞，从而产生比需要更多的冲突。 - Tim Cooper

Answer 3

以下是我在Stroustrup的书中找到的C（++）哈希函数：

int hash(const char *str)
{
    int h = 0;
    while (*str)
       h = h << 1 ^ *str++;
    return h;
}

如果您将其用作哈希表（Stroustrup就是这样做的），则可以返回哈希取模质数的绝对值。因此，代码可以改为：

    return (h > 0 ? h : -h) % N_BUCKETS;

对于最后一行。

- Wren

---

如果 h 等于 INT_MIN，对 -h 进行求值会导致未定义的行为。更好的方法是使用无符号数进行哈希处理。 - fredoverflow

Answer 4

您可以使用[]运算符检查std::string中的每个字符。但是，您可以查看Boost::Functional / Hash以获取更好的哈希方案指导。此外，在c中还有一个散列函数列表，位于这里。

- wheaties

---

所以，我的理解是哈希函数将字符串映射到整数，但通常这些整数使用压缩映射映射到表地址，以便散列表具有更可管理的大小。这适用于您在链接中推荐的哈希函数吗？ - zebraman

你的意思是“桶”吗？在生成哈希表的大小和性能标准方面，有许多“常规”函数是权衡考虑的。你应该最担心的是重复值的数量，也就是说，你的结果有多均匀分布。糟糕的哈希定会让你得到一小堆链接列表，而不是一个恒定平摊时间的查找表。我没有研究过后者，但我见过Boost。那我回答了你的问题了吗？ - wheaties

Answer 5

C++11提供了一个用于字符串的标准哈希函数。

https://en.cppreference.com/w/cpp/string/basic_string/hash

#include <string>
#include<functional> // hash
int main(){
    std::string s = "Hello";
    std::size_t hash = std::hash<std::string>{}(s);
}

- alfC

Answer 6

我只是发布了一个对Arnestig的djb2算法进行改进的版本，以便支持constexpr。我不得不移除参数的unsigned限定符，这样它才能与字面字符串一起使用。

constexpr unsigned long hash(const char *str) {
    unsigned long hash = 5381;

    while (int c = *str++) {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }

    return hash;
}

- Zamfir Yonchev

Answer 7

小字符串的另一种方式：

int hash(const char* str) {
    int hash = 0;
    int c = 0;

    while (c < std::strlen(str)) {
        hash += (int)str[c] << (int)str[c+1];
        c++;
    }
    return hash;
}

- LUCAS

Answer 8

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// a variation on dan bernstein's algorithm
// [http://www.cse.yorku.ca/~oz/hash.html]
template<typename Int>
struct hash {
    hash() : acc(5381) { }
    template<typename Ch>
    void operator()(Ch ch) { acc = ((acc << 5) + acc) ^ ch; }
    operator Int() const { return acc; }
    Int acc;
};

int main(int argc, char* argv[])
{
    string s("Hellp, world");
    cout << hex << showbase
        << for_each(s.begin(), s.end(), hash<unsigned long long>()) << '\n';
    return 0;
}

- wilhelmtell

Answer 9

每次将四个字符进行异或操作。

- Stephen

---

我不太理解XOR是什么或者有什么作用。你能解释一下吗？ - zebraman

xor是一种位运算符，意思是“一个但不是两个”，在C++中表示为'^'运算符。例如： 0 ^ 1 => 1 1 ^ 1 => 0 3 ^ 1 => 2 (11 ^ 01 => 10)它会给你一个类似随机的整数值。无论如何，您都需要以类似于Alex Martelli解决方案的方式遍历字符串。因此，请使用该方法，您就不必担心字长的问题。 :) - Stephen

这不是一个很好的哈希函数。例如，在ASCII数据上，它根本不会触及单词的第8、16、24或32位。实际效果是，如果您的哈希表有512个桶，那么一半的桶永远不会被ASCII字符串使用。您需要在某个地方引入一些互质数，并且限制桶计数以弥补哈希中的弱点并不是必要的，因为有更好的哈希可用，而且速度并不慢。 - Steve Jessop

说得好。我并没有打算写一个好的哈希函数，只是一个简单的哈希函数而已。其他答案中提供了许多更好的哈希算法。我曾经认为（也许是错误的）hash<string>不可用，并且问题并没有真正要求性能或哈希质量。我应该明确地说明这一点。 - Stephen

这个哈希函数在例如 "abcd1234" 和 "1234abcd" 上会产生碰撞。更严重的是，它将产生不良分布。 - Tim Cooper

Answer 10

您可以使用字符串类的成员函数operator[]或at，或迭代器来访问字符串对象的单个字符，而无需将其转换为C风格的字符数组。

要将字符串对象哈希为整数，您需要访问字符串对象的每个单独字符，可以按如下方式进行：

for (i=0; i < str.length(); i++) {
    // use str[i] or str.at(i) to access ith element.
}

- codaddict

---

不要在每次迭代中调用 str.length()，特别是对于在循环期间不会更改的字符串进行哈希。此外，考虑直接使用 str.c_str() 进行操作，以避免任何函数调用。字符串以 NULL 字符结尾。 - CodeAngry