哪一個在散列表或排序列表中找到一個項目更快？

Question

哪一個在散列表或排序列表中找到一個項目更快？

Answer 1

算法的複雜性是一件好事，知道哈希表已知爲0（1），而排序的向量（在你的情況下，我想最好是使用有序數組而不是列表）將提供0（日誌n）訪問時間。

但是你應該知道，複雜符號爲你提供了訪問無限時間的訪問時間。這意味着如果您知道您的數據將繼續增長，複雜表示法會爲您提供一些關於要選擇的算法的提示。

當你知道你的數據將保持一個相當低的長度時：例如你的數組/哈希表中只有少數條目，你必須使用你的手錶和度量。所以有一個測試。

例如，在另一個問題：排序數組。對於幾個條目氣泡排序，而O（N^2）可能比..快速排序，而它是（N日誌）..

此外，相應於其他答案，並根據您的項目，你必須嘗試爲你的散列表實例找到最好的散列函數。否則，它可能會導致在你的哈希表中查找顯着的糟糕性能（正如Hank Gay的答案中所指出的那樣）。

編輯：看看這篇文章瞭解the meaning of Big O notation。

Answer 2

除非哈希算法是極其慢（和/或不好），哈希表將會更快。

更新：正如評論者指出的那樣，您可能也會因爲太多的碰撞而導致性能下降，這並不是因爲您的哈希算法不好，而僅僅是因爲哈希表不夠大。大多數庫實現（至少在高級語言中）會在後臺自動增加散列表 - 這會導致插入方式的性能低於預期，從而觸發增長 - 但是如果你自己推出，那肯定是某種東西考慮。

Answer 3

假設「排序列表」的意思是「隨機訪問，排序後的集合」。列表的屬性只能遍歷元素，這會導致O（N）的複雜性。

查找排序可索引集合中元素的最快方法是通過N元搜索O（logN），而沒有colliss的散列表的查找複雜度爲O（1）。

Answer 4

在某些情況下，它取決於集合的大小（以及較小程度的實現細節）。如果你的名單很小，可能會有5-10個項目，我猜這個名單會更快。否則xtofl就是對的。

Answer 5

對於包含10個以上項目的列表，HashTable會更有效。如果列表中的項目少於10個，則由於哈希算法的開銷將更大。

如果您需要快速字典，但還需要以有序方式保存項目，請使用OrderedDictionary。 （.Net 2.0起）

Answer 6

中的get操作是O(log n)，而相同的操作e HashTable是O(1)。所以，通常，HashTable會快得多。但是，這取決於許多因素：

• 列表的大小
• 散列算法的性能
• 碰撞次數/散列算法的質量

Answer 7

這取決於完全取決於您存儲的數據量。

假設你有足夠的內存來拋出它（所以哈希表足夠大），哈希表將定位目標數據的時間固定，但需要計算哈希將添加一些（也固定）開銷。

搜索已排序的列表將不會產生散列開銷，但執行實際定位目標數據所需的時間將隨着列表增長而增加。

因此，一般來說，對於小數據集，排序列表通常會更快。 （對於頻繁更改和/或不常搜索的極小數據集，排序列表可能會更快，因爲它避免了進行排序的開銷。）隨着數據集變大，列表的增長搜索時間掩蓋了哈希的固定開銷，並且哈希表變得更快。

斷點的位置會因特定的散列表和排序列表搜索實現而異。在許多通常大小的數據集上運行測試和基準性能，以查看哪些在您的特定情況下實際執行得更好。 （或者，如果代碼已經「足夠快地運行」，則不要，只要使用你更熟悉的那個，不用擔心優化不需要優化的東西）。