通常说，在哈希表中插入和查找字符串是O（1）。但是，如何创建一个字符串的哈希键？为什么它不是O（L），字符串的长度？ 对我来说很清楚，为什么整数是O（1），但不适用于字符串。在哈希表中创建字符串哈希值的时间复杂度
请注意，我明白了为什么一般情况下，插入到散列表中是O（1），但在将散列插入到表中之前，我感到困惑。
在Java中的hashTable和C++中的unordered_map之间如何产生字符串哈希键之间有什么区别？
在散列表中插入等是O（1），这意味着它在表中的元素数中是不变的。
在此上下文中的“O（1）”没有声明您可以计算散列的速度有多快。如果努力以某种方式增长，那就是这样。然而，我发现像样的（即“适合这个应用程序”）散列函数的复杂度不太可能比散列对象的“大小”（即我们的字符串示例中的长度）中的线性更差。
那么，有没有什么办法可以实现C++和Java中哈希的快速计算？理论上（以及编程竞赛和面试问题！），它可以在分析算法的时间复杂性方面发挥重要作用。 – MehrdadAP
@MehrdadAP至少在C++中，不是不看哈希函数的实现。然而，我期望每一个合理的散列函数都会在它的散列对象的“长度”或“大小”（无论对于你正在哈希的对象是什么意思）中具有线性复杂度。尽管我可以想象出现某些情况，出于某种原因，“较慢”的哈希值具有优势。 –
@MehrdadAP不能用C++说话，但Java哈希值是O（N），N取决于字符串的大小。在大多数情况下，C++不存在散列。例如，std :: map通常是一棵红黑树。 – user4581301
根据Java的实现，Hashtable使用key（String或Integer）的hashCode方法。根据http://en.cppreference.com/w/cpp/utility/hash Hashtable String.hashCode Integer.hashCode
和C++使用std::hash<std::string>或std::hash<int>和实现在功能文件（/路径/到/ C++ ... /include/c++/4.8/functional）
有趣的看到Java实现...谢谢！ –
通常说，在散列表中插入和查找字符串是O（1）。但是，如何创建一个字符串的哈希键？为什么它不是O（L），字符串的长度？对我来说很清楚，为什么整数是O（1），但不适用于字符串。
O（1）通常引用表示时间不随容器中元素的数量增长。正如你所说，时间以产生一个字符串的哈希值本身并没有为O（1）在串的长度- 尽管对于一些实现，它是：例如微软的C++ std::hash<std::string>有：
size_t _Val = 2166136261U;
size_t _First = 0;
size_t _Last = _Keyval.size();
size_t _Stride = 1 + _Last/10;
if (_Stride < _Last)
_Last -= _Stride;
for(; _First < _Last; _First += _Stride)
_Val = 16777619U * _Val^(size_t)_Keyval[_First];
return (_Val);
_Stride是字符串长度的十分之一，所以一个固定的字符数量将会被合并在散列值中。这样的散列函数是字符串的长度为O（1）。
GCC的C++标准库采用不同的方法：在V4.7.2至少，它通过_Hash_impl支持类为static非成员函数_Hash_bytes，它不包含每一个字节杂音哈希召唤。因此，GCC的hash<std::string>是字符串的长度为O（N）。
std::unordered_set和std::unordered_map，其中MS的实现没有做明显的 - 至少直到VS2013/VC12;总而言之，对于不易发生碰撞的键，MS的方法将更轻/更快，但是否则会更快更恶劣地降级。而且是有间如何散列密钥串被在C++ java和unordered_map Hashtable的产生的任何差？
C++标准没有规定字符串是如何散列的 - 它留给个别的编译器实现。因此，不同的编译器会遇到不同的妥协 - 甚至是同一编译器的不同版本。
文档大卫·佩雷斯·卡布雷拉的答案的链接解释在Java中hashCode功能：
返回的哈希码此字符串。为字符串对象的哈希码是使用
int算术，其中s[i]是字符串的i个字符计算为
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
，
n是串的长度，及^表示求幂。 （空字符串的散列值为零）
这很明显是字符串长度的O（N）。
为什么你关心字符串的长度，但忽略整数中的位数？ – Matt
啊，即使没有任何上下文，具有普遍意义的神奇的“O（1）”。 –
@Matt，因为当数字可以放入32位或64位时，大部分操作都可以由CPU在O（1）中完成。 另外，大部分时间我们都有很长的字符串，而不是大整数。 （特别是在编程竞赛中！） – MehrdadAP