17

我必须编写自己的哈希函数。如果我只想制作一个简单的哈希函数，将字符串中的每个字母映射到一个数值（即 a=1，b=2，c=3，...），有没有办法可以在一个字符串，而不必先将其转换为 c 字符串来查看每个单独的字符？有没有更有效的哈希字符串方法？

4

10 回答 10

9

从个人经验来看，我知道这很有效并且产生了良好的分布。（抄袭自http://www.cse.yorku.ca/~oz/hash.html）：

djb2

该算法 (k=33) 是 dan bernstein 多年前在 comp.lang.c 中首次报道的。该算法的另一个版本（现在被 bernstein 青睐）使用 xor：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;
}
于 2012-11-21T05:52:28.833 回答
7

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

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++）。

于 2010-03-29T01:12:11.580 回答
5

您可以使用运算符检查 std::string 中的每个单独的字符[]。但是，您可以查看Boost::Functional/Hash以获得更好的散列方案的指导。此处还有一个 c 中的散列函数列表。

于 2010-03-29T01:09:14.380 回答
5

这是我在 Stroustrup 的书中找到的 C (++) 哈希函数：

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

如果您将它用于哈希表（Stroustrup 这样做），那么您可以改为返回哈希模数的 abs。所以与其

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

最后一行。

于 2012-08-05T19:38:45.640 回答
1

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);
}
于 2018-07-08T22:04:42.607 回答
1

只是发布了对 Arnestig 的 djb2 算法的改进，使其对 constexpr 友好。我必须删除参数的无符号限定符，以便它可以与文字字符串一起使用。

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;
}
于 2020-06-28T21:49:18.447 回答
0

xor 字符一起，一次四个。

于 2010-03-29T01:10:12.100 回答
0 
#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;
}
于 2010-04-14T08:30:20.023 回答
0

小字符串的另一种方法：

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;
}
于 2015-12-07T08:04:55.580 回答
-2

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

要将字符串对象散列为整数，您必须访问字符串对象的每个单独的字符，您可以这样做：

for (i=0; i < str.length(); i++) {
    // use str[i] or str.at(i) to access ith element.
}
于 2010-03-29T01:10:08.777 回答