在散列表O（1）中查找？

如果一個散列表包含N個不同的項目並且沒有超載，那麼這N個項目的散列必須有大約1g（N）個比特，否則太多的項目會得到相同的散列值。在散列表O（1）中查找？

但是哈希表查找通常被認爲平均需要O（1）次。

這是不可能在O（1）時間來產生LG（N）位，所以對於哈希表的複雜性的標準的結果是錯誤的。

我的推理出了什麼問題？

O（1）只是一個預期的結果：D – Emadpres 2014-11-25 13:21:30

請參閱http://cs.stackexchange.com/q/1643（鏈接似乎是該網站上的相同問題：http://cs.stackexchange.com/q/27748） – 2014-11-25 13:44:34

的[可以哈希表確實是O（1）？（http://stackoverflow.com/questions/2771368/can-hash-tables-really-be-o1） – DavidRR 2017-05-14 17:44:30

你的推理出了什麼問題，是對「時間」的衝突定義的使用。

當一個說，查找在哈希表中花費O（1）時間，人們通常意味着需要O（1）比較，即，找到一個項目所需的比較的數量以上由界一個常數。在這個「時間」的概念下，用於計算散列的實際時間（就像用秒計算的東西）不會導致變化。

測量比較時間，雖然它可能不以同樣的方式，在秒測量它會，仍然提供了有關哈希表的行爲非常有用的信息反映實際情況的近似值。

這種事情對於算法的大多數漸近複雜性描述是正確的：人們經常使用具有非常抽象意義的「時間」，這不是「時間」的非正式含義，但更多的時候是一些變化「操作次數」（操作類型通常沒有說明，預計會很明顯，或從上下文中清楚）。

2014-11-25 13:23:36

優秀的答案。 O（1）可以被認爲是「人口中的元素數量不影響算法運行時間」。 – AlexanderBrevig 2014-11-25 13:50:55

-1

散列表搜索是O（1）。我想你是混合插入（這是O（n））和搜索。

2014-11-25 13:28:35

在hastable中搜索* expected * O（1）。但最壞的情況仍然是O（n）。 – dingalapadum 2016-06-20 08:41:00

分析是基於這樣的假設散列函數是固定的，不相關的存儲在表元素的實際數目。與其說散列函數是否存在在哈希表中的N個元素返回LG N比特值，所述分析是基於散列函數返回，也就是說，一個ķ位值，其中ķ是獨立於N。典型值爲k（如32或64）提供的散列表遠遠大於實際需要的任何值。

所以在一次感測，對，一個表保存N個元素需要返回O（LG n）位的哈希函數;但在實踐中，使用了遠大於lg n的預期最大值的常數。

2014-11-25 13:42:04 chepner

回答