哈希表與分類數組 - 使用哪個？

Question

假設我有一組數據（未排序），我希望爲快速查找而存儲。在加載數據之前，我不知道大小是多少，我應該一次加載所有數據，以便我可以立即開始執行查找。另外，在程序執行期間的任何時候，可以向我呈現更多的數據以存儲在我選擇的數據結構中。

我應該使用散列表還是有序數組來存儲這些數據？顯然，靜態哈希表需要根據數據大小在運行時進行 - 這是否足以造成我只需對給予的數據進行排序的缺點，即使它是O（NlogN）而不是O（ N）？或者我應該考慮一些動態哈希方法？

澄清：我需要加載任意大小的數據，然後在數據上執行搜索和插入操作，沒有明確的順序或想要查找/插入的數量，我不得不這樣做。

我知道這真的很一般...但是如果我在加載數據之後必須做更多的插入而不是搜索呢？更多的搜索比插入更多？

Answer 1

這實際上取決於操作的頻率。

• 如果你做了很多相對於查找的數量插入的，則排序後的數組可能不是一個很好的選擇，因爲插入排序後的數組是昂貴的（O（n）的時間）。二進制搜索樹或哈希表可能適用於此。

• 如果相對於插入次數進行大量查找，那麼排序後的數組可能是個好主意，儘管哈希表可能會更快。當您需要數據按排序順序執行範圍搜索或最近鄰居查找等操作時，排序數組通常是一個不錯的選擇，但如果您不需要這樣做，則可能不合適。

• 如果您的密鑰具有某些類型（整數，字符串等），您可以使用更具體的數據結構（如trie或van Emde Boas tree）以獲得額外的性能。這些有時比散列表或排序數組更好，因爲它們可以利用數據的細節。

如果你真的不知道會發生什麼事情，我會使用散列表作爲初始實現。這不太可能是一個不好的選擇，儘管可能會有更精細的數據結構可供您使用。如果您事先不知道使用模式，則排序後的數組不太可能是個好主意。

希望這會有所幫助！

Answer 2

Templatetypedef的答案是現貨，但我會在RedBlack樹上添加一些更多的信息，這些信息在兩個選項之間提供了一個很好的折中。他提到了嘗試和vEB樹（之前沒有聽說過後者，聽起來很有用！）RedBlack樹比這些選項更不理想，但可能是更通用的解決方案。當然值得研究這些更優雅的樹結構選項以及列表或散列圖。

RedBlack Tree: 
Insertion: O(log n) 
Key Lookup: O(log n) 
Key Search: O(log n) 
Iteration: O(n) 

Sorted List: 
Insertion: O(n log n) 
Index Lookup: O(1) 
Sorted Search: O(log n) 
Iteration: O(n) 

Hash Table: 
Insertion: O(1) 
Key Lookup: O(1) 
Key Search: O(n) 
Iteration: O(n)