C++中用于将字符串转换为整数的哈希函数

Question

我正在寻找一个C++中的哈希函数，用于将字符串哈希为整数。我使用了CMapStringToPtr，但它有一个名为“GetNextAssoc”的函数，允许检索键作为字符串，这意味着字符串必须被存储，占用了大量内存。 是否有其他哈希函数可以占用更少的内存，并且不需要存储字符串？

- Bipario

---

尝试使用std::hash<std::string>()()。 - Kerrek SB

我不确定我理解你的问题。几乎在任何需要使用哈希函数的地方，您都必须跟踪原始数据，因为哈希函数都会发生冲突，而基于哈希的查找需要原始数据才能确定，或者用于解决冲突。 - Omnifarious

我会使用 boost::hash_value(const std::string & val)。 - ali_bahoo

@Kerrek：std::hash<std::string>()()似乎是C++11的一个特性。我的编译器（VS 2008）没有这个功能，我很遗憾。 - Christian Ammer

尝试使用 std::tr1::hash。 - Kerrek SB

Answer 1

C++内置了一个哈希函数，用于所有STL哈希容器。可以使用std::hash来实现。另外，你也可以自己编写哈希函数，只需要将字符串通过常量引用传递，并循环遍历其每个字符，将它们添加到一个整数中，然后对某个值取模即可 :)

- John Humphreys

---

也许我错了，但是你的链接指的是 SGI 扩展（在 SGI <hash_map> 中定义），在 C++11 之前它不是 C++ 标准的一部分（在<functional>中定义）。 - Christian Ammer

一半一半吧。我认为这是一个扩展程序，但如果它不在您的系统上，我会非常惊讶——因为它几乎无处不在。 - John Humphreys

什么是对某个值取模？ - dustinyourface

@dustinyourface Mod 表示使用模数运算符：http://www.cprogramming.com/tutorial/modulus.html。根据《Effective Java》的一些指导，在数组中的每个重要字段上，执行 "result = 31 * result + field"。您可以将结果初始化为某个随机数字，例如 17。推荐使用质数作为乘数（据说可以减少冲突，但我的数学过不去）。 - John Humphreys

std::hash 返回的是 size_t 而不是 int。 - Fries

Answer 2

 int hash( const string &key, int tableSize) {
   int hashVal = 0;

   for(int i = 0; i<key.length();  i++)
     hashVal = 37*hashVal+key[i];

   hashVal %= tableSize;

   if(hashVal<0)
     hashVal += tableSize;

   return hashVal;
 }

- Angelos Kapsimanis