如何使用C++将字符串散列为int？

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

来源

2010-03-29 zebraman

重的第一个问题，当然，e.g，是这样的：

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

关于第二，有很多更好的方法来哈希字符串。例如，参见here以获得几个C示例（可以轻松地转换成上面代码片段中的C++）。

来源

2010-03-29 01:12:11

我明白了。如果我想做大小写不敏感的散列，那怎么样？其中A = a = 1？ – zebraman 2010-03-29 01:35:54

+1，如果仅仅使用'* 2'和'|'来创建一个喜剧性较差的散列;-) – 2010-03-29 01:40:06

@zebraman，请参阅http://www.cplusplus.com/reference/clibrary/cctype/tolower/ – 2010-03-29 02:17:09

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

来源

2010-03-29 01:09:14 wheaties

所以，我的理解是，散列函数的字符串映射为int，但通常这些整数映射使用压缩映射到表地址，以便哈希表是一个更易于管理的大小。这适用于你在链接中推荐的散列函数吗？ – zebraman 2010-03-29 01:21:31

你的意思是水桶？有许多“通常”的功能是根据散列表的大小和性能标准进行权衡。你最应该关心的是多少次重复的值，也就是说你的结果是多么一致地分布。可怜的哈希总是会给你留下一小串链表，而不是一个固定的摊销时间查询表。在我看到Boost的时候，我还没有检查过它。我回答了吗？ – wheaties 2010-03-29 01:29:33

我这么认为。 o_o – zebraman 2010-03-29 01:36:09

-2

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

哈希字符串对象为整数，你必须访问字符串对象的每个单独的字符，你可以做：在一个时间

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

来源

2010-03-29 01:10:08 codaddict

不要为每个迭代调用'str.length（）'，特别是对于在循环中不改变的散列字符串。另外，考虑直接使用'str.c_str（）'来避免函数调用。字符串以'NULL'字符结束。 – CodeAngry 2014-04-30 14:10:02

XOR中的人物，四。

来源

2010-03-29 01:10:12 Stephen

我真的不明白xor是什么。你能解释一下吗？ – zebraman 2010-03-29 01:13:21

xor是一个按位运算符，意思是“one-but-not-both”，即C++中的'^'运算符。例如 0^1 => 1 1^1 => 0 3^1 => 2（11^01 => 10）它会给你一个随机的整数值。无论哪种方式，您都需要以类似于Alex Martelli解决方案的方式遍历字符串。所以，去那个，你不需要担心字的大小。 :) – Stephen 2010-03-29 01:22:57

感谢您的帮助 – zebraman 2010-03-29 01:26:22

#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-14 08:30:20 wilhelmtell

这里有一个C（++），散列函数，我在Stroustrup的书中发现：

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

如果你正在使用它的哈希表（斯特劳斯做），那么你可以改为回报哈希模的一个素数。所以，而不是

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

为最后一行。

来源

2012-08-05 19:38:45 Wren

如果'h'是'INT_MIN'，则评估'-h'会导致未定义的行为。更好地使用无符号数字进行散列。 – fredoverflow 2012-11-21 09:00:00

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

djb2

该算法（K = 33）首先由丹伯恩斯坦在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-21 05:52:28

为小弦的另一种方法：

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-07 08:04:55 LUCAS

如何使用C++将字符串散列为int？

回答

相关问题