通常說，在哈希表中插入和查找字符串是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