二叉樹(binary tree)和哈希表(hash table)都是很基本的數據結構，但是我們要怎麼從兩者之間進行選擇呢？他們的不同是什麼？優缺點分別是什麼？
回答這個問題不是一兩句話可以說清楚的，原因是在不同的情況下，選擇的依據肯定也不同。首先來回顧一下這兩個數據結構：
哈希表使用hash function來對輸入的數據分配index到哈希表對應的槽中。假設有一個哈希表的size是100，而我們輸入的數據是從0～99，我們要把輸入數據儲存到哈希表中。理論上來說，該哈希表插入和查找操作的時間複雜度都是O(1)。
二叉樹遵循右子樹大於根節點，左子樹小於根節點的原則進行數據的插入和保存。如果這個樹的平衡的，那麼，對於每個元素的插入和查找操作的時間複雜度是O(log(n))，n是樹的節點個數，log(n)通常是樹的深度。當然，對於不平衡的情況，那就需要更復雜的數據結構的樹（紅黑樹等）進行處理。
上文似乎得出結論哈希表要好於二叉樹，但是it is not always the case。哈希表有以下幾個突出的缺點：
- 當更多的數插入時，哈希表衝突的可能性就更大。對於衝突，哈希表通常有兩種解決方案：第一種是線性探索，相當於在衝突的槽後建立一個單鏈表，這種情況下，插入和查找以及刪除操作消耗的時間會達到O(n)，且該哈希表需要更多的空間進行儲存。第二種方法是開放尋址，他不需要更多的空間，但是在最壞的情況下（例如所有輸入數據都被map到了一個index上）的時間複雜度也會達到O(n)。
- 所以，在決定建立哈希表之前，最好可以估計輸入的數據的size。否則，resize哈希表的過程將會是一個非常消耗時間的過程。例如，如果現在你的哈希表的長度是100，但是現在有第101個數要插入。這時，不僅哈希表的長度可能要擴展到150，且擴展之後所有的數都需要重新rehash。
- 哈希表中的元素是沒有被排序的。然而，有些情況下，我們希望儲存的數據是有序的。
另一方面，我們討論二叉樹：
- 二叉樹不會有衝突（collision），這意味著我們能夠保證二叉樹的插入和查找操作一直都是O(log(n))的時間複雜度。
- 二叉樹的空間佔用跟輸入的輸入數據一致。所以我們不需要為二叉樹預先分配固定的空間。所以，你也不需要預先知道輸入數據的size。
- 所有的元素在樹中是排序好的。
Summary
如果你預先知道輸入數據的大小，而且有足夠的空間儲存哈希表，且不需要對數據進行排序，那麼哈希表總是好的。因為哈希表在插入，查找和刪除操作中只需要常數時間。
另一方面，如果數據是持續的加入，你預先不知道數據的大小，那麼二叉樹是一個折中的選擇。
分享到:
閱讀更多 技匠志 的文章
