什麼時候哈希表比搜索樹更好用？

2010-12-17 user541169

什麼是搜索樹？如果你的意思是一個有序的集合，那麼答案就是：當你不需要排序時，你可以使用一個散列表。 – 2010-12-17 23:13:32

搜索樹未訂購。如果您以後綴或前綴順序遍歷它們，它們會被排序，但它們不會被排序。 – wilhelmtell 2010-12-17 23:16:47

@Daniel，來自維基百科：「在計算機科學中，搜索樹是一種樹型數據結構，其數據值可以從一些有序集合中存儲，這樣就可以在樹的有序遍歷中訪問節點按儲存值的升序排列「。二叉搜索樹和B樹是搜索樹的兩個例子。 – 2010-12-17 23:23:16

取決於你想要對數據結構做什麼。

Operation   Hash table Search Tree 
Search   O(1)  O(log(N)) 
Insert   O(1)  O(log(N)) 
Delete   O(1)  O(log(N)) 
Traversal   O(N)  O(N) 
Min/Max-Key  -hard-  O(log(N)) 
Find-Next-Key  -hard-  O(1)

插入，搜索哈希表取決於哈希表及其設計的負荷率。設計不佳的可惡人可以進行O（N）搜索和插入。搜索樹也是如此。
根據您的衝突分辨率狀態，在哈希表中刪除可能非常麻煩。
遍歷容器，查找最小值/最大值，查找下一個/上一類操作在搜索樹上更好，因爲它的排序。
以上搜索樹的所有估計都是針對「平衡」搜索樹的。

來源

2010-12-17 23:12:57

我想看到一個具有O（1）訪問權的哈希表。看到這些不當使用者，我的眼睛已經流血了。 – wilhelmtell 2010-12-17 23:33:22

儘管有衝突解決方案，設計正確的散列表*不會*具有O（1）查找功能。這是因爲查找時間不變 - 表格的大小並不重要。例如，（理論上）具有1000個元素的散列表將具有與具有1,000,000,000個元素的散列表相同的最壞情況查找時間。而具有1000個元素的樹最糟糕的情況是'log2（1,000）= 10'訪問，但具有十億個元素的樹最糟糕的情況是'log2（1,000,000,000）= 30'訪問。 – 2010-12-18 00:06:54

@Charles：假定散列函數的屬性可能實際或可能不實際實現 - 即它是O（1）並且是一致的。也就是說，樹的這些數字是用比較的數量來表示的，而不是按照運行時間來表示的，所以這些數字都是精美的。 – 2010-12-18 03:15:00

在許多問題中，它取決於哈希函數的價格是多少。根據我的經驗，散列函數的速度通常是平衡樹的兩倍，因爲散列函數是明智的，但它們的速度肯定會變慢。

來源

2010-12-17 23:23:26

當平均訪問和插入時間比最佳訪問和插入時間更重要時。實際上，我認爲搜索樹通常與散列表一樣是一個很好的解決方案，因爲即使理論上大的θ大於log n的大θ，log n也是非常快的，當你開始處理大的n值時影響實際差別縮小。另外，大的theta沒有提到常數的值。當然，這也適用於樹的複雜性，但樹的常數因子比哈希表的常數因子更加固定，通常數量很少。

同樣，我知道理論家在這裏會不同意我的觀點，但是我們在這裏處理的是計算機，而且對於計算機來說任何重要的負擔都必須是不切實際的。如果n是1萬億，那麼n的記錄是40，今天的計算機可以相當快地執行40次迭代。對於n的日誌增長到50你已經有超過四萬億元素。

現在的C++標準並沒有在它的容器中提供一個哈希表，我認爲這是十多年來人們習以爲常的原因。

來源

2010-12-17 23:27:45 wilhelmtell

「有一個原因，人們很好，因爲它已經有十多年了」 - 原因可能是STL和TR1都包含一個哈希表，所以一直有相當廣泛的可用性。例如，如果鍵是一個字符串，那麼哈希函數比（比如說）20個字符串比較更加合理，特別是如果很多字符串都有一個重要的公共前綴。如果你只是要查找1把鑰匙，那麼你很對，它很快。但是如果查找基本上都是你的程序的話，有時候只有2個因素會影響很多。 – 2010-12-18 03:23:43

第一個C++標準沒有包含哈希表的唯一原因是因爲他們想要發送該死的東西。 – fredoverflow 2010-12-18 08:45:05

我取的事情：

Operation     Hash table(1) SBB Search Tree(2) 
.find(obj) -> obj   O(1)   O(1)* 

.insert(obj)    O(1)   O(log(N)) 

.delete(obj)    O(1)   O(log(N)) 

.traverse/for x in... O(N)   O(N) 

.largerThan(obj) -> {objs} unsupported O(log(N)) 
              \ 
              union right O(1) + parent O(1) 

.sorted() -> [obj]   unsupported no need 
              \ 
              already sorted so no need 
              to print out, .traverse() is O(N) 

.findMin() -> obj   unsupported** O(log(N)), maybe O(1) 
              \ 
              descend from root, e.g.: 
              root.left.left.left...left -> O(log(N)) 
              might be able to cache for O(1) 

.findNext(obj) -> obj  unsupported O(log(N)) 
              \ 
              first perform x=.find(obj) which is O(1) 
              then descend from that node, e.g.: 
              x.right.left.left...right -> O(log(N))

（1）http://en.wikipedia.org/wiki/Hash_table

（2）http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree，例如http://en.wikipedia.org/wiki/Tango_tree或http://en.wikipedia.org/wiki/Splay_tree

（*）您可以將哈希表與搜索樹結合使用來獲取此信息。沒有漸近速度或空間的損失。否則，它是O(log(N))。（**）除非你永遠不刪除，在這種情況下，只需緩存最小和最大的元素，它的O(1)。

這些費用可能會攤銷。

結論：

你想用樹木在訂貨時事項。

來源

2011-09-13 19:22:43 ninjagecko

什麼時候哈希表比搜索樹更好用？

回答

相關問題