在實踐中，最好的選擇是什麼：哈希表，基數樹，紅黑樹或...？

Question

您是否對上述這些結構有過一些經驗？如果插入和查找很重要，那麼在實踐中似乎最好？

如果散列表有很多衝突，你最終會得到一個你需要遍歷的桶列表，所以如果性能問題很重要的話，你最終可能會以O（n）結尾。到目前爲止，我還沒有對基數樹進行過任何經驗，而且我已經認識到紅黑樹在查找時會擊敗AVL樹。

你的經驗是什麼？

感謝， 丹

Answer 1

我不認爲我曾經有過，我已經寫代碼用哈希表的情況下，其結構已被證明具有固有的不可接受的性能。

我不認爲自己曾經有過使用平衡樹編寫代碼的情況，並且該結構已被證明具有固有的不可接受的性能。

所以我不用擔心它太多，並採取簡單的路線。 Python提供了基於散列的集合/字典，所以我使用這些。 C++ 03提供set和map但不是unordered_set和unordered_map，所以我使用這些。在可用的語言/庫中，如果我需要訂單，則使用樹;如果（a）我不需要訂單，則使用散列表。（b）我有或可以編寫體面的散列函數。如果我已經有了一個自然順序，但不是一個自然的哈希函數，那麼當然這個簡單的路由就是一棵樹。

在實踐中，絕大多數關聯數組的鍵都是字符串，整數或這些元組的元組。所以你總是有一個訂單，一個體面的散列函數並不遙遠。如果我使用的那個看起來很狡猾，那麼嘗試它們都是很容易的。

基數基本上適用於您期望長通用前綴的情況。例如，如果您的密鑰是網頁的網址，則「幾乎所有」和「全部」之間的某處將以http://或https://開頭，主機名爲樹的各個部分提供更多通用前綴。因此，顯而易見的優化是避免在查找過程中多次比較該通用前綴，這表示針對「普通」平衡樹。但是與往常一樣，「明顯的」優化不一定值得付出努力，除非你碰巧有一個庫已經存在。

Answer 2

這是一個問題，必須回答「這取決於」。這取決於很多因素。哈希表可能佔用比基於樹的結構更多的空間，因此有時需要犧牲快速查找更小的內存佔用量。有時候，你必須快速查找。有時你會檢索x到y的項目列表，所以有序的基於樹的結構更有意義。有時你需要最近的鄰居，一棵BK樹。有時候......你明白了，不是？

這就是他們所說的一個好算法的意思。您的選擇將受到問題域的影響，您將需要處理的事情等。

Answer 3

我認爲你錯過了這個問題的觀點。沒有適用於所有可能情況的最佳萬能數據結構。每個結構都有自己的優點和缺點。例如，如您所知，散列表具有預期的O（1）查找和插入/刪除性能。缺點是這沒有考慮到必須實際計算可能非常昂貴的值的散列（例如，當使用大字符串時）的隱藏常數。如果使用良好的散列函數，碰撞應該非常罕見，但即使是少量的碰撞也會累加並影響性能。另一方面，平衡二進制搜索樹（紅黑和AVL）支持O（log n）操作，這確實較慢，但具有保持元素排序的附加優勢 - 因此可以實現更多的操作（例如，最小，最大，第k個元素，上限，下限，範圍查詢等），這在無序結構（如散列表）中是不可能的。實際上，兩者之間的速度差異往往可以忽略不計，即使是涉及數百萬個元素的操作。紅黑和AVL樹之間的速度差異甚至不那麼明顯，都是O（log n），並且只有一個小的常數因子。

然後還有很多其他數據結構，如分段樹，二叉索引樹（AKA Fenwick樹）和您提到的基數樹。請閱讀一本關於數據結構的好書（推薦使用CLRS），或者至少閱讀維基百科上的每篇文章，瞭解它們的工作原理和操作成本，並決定哪一個適合您的工作。

底線是您選擇的數據結構取決於您需要的數據結構。沒有哪個結構是絕對最好的，並且可以滿足你可能想出的任何場景。

Answer 4

在R-B和AVL樹之間，您需要查看搜索與插入/刪除的頻率。 AVL樹更加接近平衡，因爲它的搜索速度稍快，但插入/刪除速度稍慢。實際上，這種差異通常可以忽略不計，除非其中一個批次比另一個更頻繁。

對散列表進行評論幾乎是不可能的。在最基本的情況下，哈希表具有固定的大小。然而，對於通用用途，這通常被認爲是不可接受的。爲了在各種尺寸範圍內保持可用性，大多數散列表執行某種重新哈希或增量調整大小。具體如何完成通常對速度有影響（例如，根據我的經驗，簡單的固定大小的散列表通常在其極限內快一個數量級左右）。

很大程度上還取決於您使用的鍵的性質。樹的比較只能查看密鑰的部分，並在兩個密鑰之間發現不匹配時立即作出決定。體面散列，但比較，總是基於整個關鍵。如果你有一個擁有大鍵的小集合（例如，長字符串），你可以在很短的時間內完成樹搜索，而不是完成計算散列。 OTOH，如果你有一個複合鍵，其中主要領域往往是平等的，比較可以匆忙放緩。

Answer 5

我在去年進行了很多實驗，發現令我驚訝的是，它非常難以擊敗234棵樹（AVL樹本質上是23棵樹）。每個數據結構都有其最佳位置，但是在開始優於那些234棵樹之前，您必須獲得相當多的數據。這些234樹的實施是非破壞性的，以啓動。

也就是說，對於大數據量，請使用散列表。