計算散列的速度有多快？

-1

它是在O（1）或O（n）還是在兩者之間完成的？計算一個非常大的對象和一個小對象的散列是否有缺點？如果重要，我使用Python。計算散列的速度有多快？

2017-06-16 Vic

取決於散列函數的實現。 – zerocool

一個插件：與較大的對象相比，較小的對象碰撞的可能性較高？ – Vic

那麼，我的迴應仍然是一樣的，碰撞是依賴於算法的。您可能有一個長度爲100個字符的字符串，另一個長度爲1個字符。現在，如果你的散列函數只考慮了字符串的第一個字符，你就會有很多衝突。 – zerocool

一般來說，對於「小」項目計算散列將是O（1），對於「大」項目（其中「N」表示項目的鍵的大小）計算散列將是O（N）。小的和大的精確的分界線是變化的，但是通常在寄存器的大小附近（例如，32位機器上的32位，64位機器上的64位）的某處。這也可以取決於輸入類型 - 例如，寄存器大小上的整數類型全部散列且具有恆定的複雜性，但字符串需要的時間與字節大小成正比，直至單個字符（即，兩個字符字符串大約是單個字符串的兩倍）。

一旦你計算出散列表，訪問散列表的過程就會有恆定的複雜度，但在最壞的情況下可能和O（N）一樣壞（但這是一個不同的「N」 - 項數插入表中，而不是個別密鑰的大小）。

來源

2017-06-16 22:25:13

漸近複雜性可能不是用於討論小輸入大小運行時間的最合適的工具，因爲它在技術上只關心當我們接近無窮大時發生的情況。另外，難道你不能說從N = 1開始它就像O（N/32）或O（N/64）（= O（N））一樣嗎？也許更重要的是，複雜性將完全取決於你如何實際計算哈希 - 我不認爲有一條規則說明你可能只做O（1）每字節的工作來計算哈希。 – Dukeling

謝謝。在一個相關的說明中，這是否意味着一個字符的字符串佔用64位，而一個兩個字符的字符串佔用128位？（假設是一個64位機器） – Vic

@Vic：不 - 通常一個字符會佔用一到四個字節的東西，但是比這更大的東西將會非常少見。 –

大部分時間你的散列將在O（1）的訪問中進行計算。但是，如果它是一個非常糟糕的散列，每個值都具有相同的散列值，那麼最壞的情況就是O（n）。

與哈希關聯的對象越多，就相當於碰撞的次數越多。

來源

2017-06-16 22:24:23

真正的答案取決於。你沒有指定你感興趣的散列函數。當我們談論像SHA256這樣的密碼散列時，複雜度是O（n）。當我們正在談論使用電話號碼的後兩位數字的散列函數時，它將是O（1）。哈希表中使用的哈希函數往往會針對速度進行優化，因此更接近O（1）。

有關散列表的進一步參考，請參閱Time Complexity上的python維基頁面。

來源

2017-06-18 19:33:49

計算散列的速度有多快？

回答

相關問題