我必须编写自己的哈希函数。如果我只想制作一个简单的哈希函数,将字符串中的每个字母映射到一个数值(即 a=1,b=2,c=3,...),有没有办法可以在一个字符串,而不必先将其转换为 c 字符串来查看每个单独的字符?有没有更有效的哈希字符串方法?
10 回答
从个人经验来看,我知道这很有效并且产生了良好的分布。(抄袭自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;
}
关于第一个问题,当然,例如:
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++)。
您可以使用运算符检查 std::string 中的每个单独的字符[]
。但是,您可以查看Boost::Functional/Hash以获得更好的散列方案的指导。此处还有一个 c 中的散列函数列表。
这是我在 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;
最后一行。
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);
}
只是发布了对 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;
}
xor 字符一起,一次四个。
#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;
}
小字符串的另一种方法:
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;
}
您可以使用字符串类或迭代器的成员函数operator[]或at来访问字符串对象的单个 char,而无需将其转换为 c 样式的 char 数组。
要将字符串对象散列为整数,您必须访问字符串对象的每个单独的字符,您可以这样做:
for (i=0; i < str.length(); i++) {
// use str[i] or str.at(i) to access ith element.
}