散列最適合請求高查找速度的應用程序嗎？

我記住hash是我應該採取的第一件事情，如果我想編寫一個請求高查找速度的應用程序，而其他任何數據結構都不能保證。散列最適合請求高查找速度的應用程序嗎？

但是當我看到一些不同的帖子時，我感到困惑，比如後綴樹，trie，等等。

所以我想知道hash總是最好的事情高速查找？如果我想要高查找速度和更少的空間成本呢？

是否有任何材料（書籍或論文）關於高速查找和空間效率的數據結構或算法**的講解？任何這種都非常感激。

來源

2012-09-20 Alcott

從來沒有這樣的事情[某些普通問題]的最佳數據結構。一切都與案例有關。嘗試和基數樹可能對字符串很好，因爲無論如何你都需要閱讀字符串。數組允許簡單性和高速緩存效率 - 通常是小規模靜態信息的最佳選擇 – amit

@amit，是的，你是對的。 – Alcott

另外：相關 - [哈希表v/s樹]（http://stackoverflow.com/questions/10033417/hash-table-vs-trees） – amit

我假設你在這裏談論的是字符串，答案是「否」，哈希不是查找字符串的最快或最節省空間的方式，嘗試是。當然，編寫散列算法要比寫一個trie要容易得多。

有一件事你不會在維基百科或有關嘗試的書中找到的是，如果你天真地執行每個字母一個節點它們，你最終會有大量的低效，一個孩子的節點。爲了使一個真正燒燬CPU的trie必須實現節點，以便它們可以具有可變數量的字符。當然，這比編寫簡單的線索更困難。

我已經編寫了可以處理超過10億個條目的trie實現，我可以告訴你，如果正確完成，它非常快速，沒有其他比較。

嘗試的另一個問題是您必須編寫自定義堆，因爲如果您只是使用某種通用內存管理，它將會很慢。因此，除了實施trie之外，您還必須實施特洛伊木馬運行的堆。相當怪異複雜，但如果你這樣做，你會得到瘋狂的速度。

來源

2012-09-20 22:52:30

Upvoted。哈哈，我喜歡你的話。順便說一句，如何寫一個偉大的堆？ – Alcott

堆是一個大陣列。指針保持在堆中可用空間的開始處。當你在trie中添加一個節點時，這個節點就被添加到這個空閒的空間指針上。當一個節點被放大時（例如由於添加了一個孩子，例如）展開的節點被移動到空閒空間的開始處。這在舊節點所在的堆中留下了空隙。然後，您在節點之前告訴節點它有相鄰的空閒空間（每個節點知道「在它前面」有多少空閒空間）。如果那個節點需要放大，它不會移動，但會擴展到位。你有時也需要壓縮。 –

'哈希不是查找字符串的最快或者空間最有效的方式，嘗試是'這並不完全正確。嘗試有很多開銷。傳統的trie具有用於任何字符串的每個前綴的節點，並且每個都需要一個「SIZE」指針數組，其中SIZE是字母大小（對於8位字符爲256）。他們也非常緩存inefficeint，雖然他們提供了很好的理論複雜性。另外 - 你描述的優化不是一個特里，它是[基數樹]（http://en.wikipedia.org/wiki/Radix_tree）（這是壓縮嘗試）。 – amit

這也可能取決於元素的實際數量。在複雜性理論中，散列並不差，但是複雜性理論只有在元素的實際數量大於某個閾值時纔有效。

I.e.如果只有2個元素，則有一種比散列更快的方法;-)

來源

2012-09-20 13:24:54 lilalinux

哈希表是'O（1）'* average *，而它是'O（n）'*最糟糕的情況*這可能是一些應用程序的問題。 – amit

好的，我編輯了我的答案，以便更容易理解:-) – lilalinux

只有好的散列實現才能帶來良好的性能。在所有情況下，你都無法將散列與Trie進行比較。 Trie適用的情況很快，但在內存方面可能代價很高（同樣依賴於實施）。

但你有沒有測量性能？或者您正在尋找不必要的優化。地圖是否讓你失望？

來源

2012-09-20 13:29:19

不是，我只是想知道這裏有那麼多奇特的數據結構，什麼情況最適合。 – Alcott

@Alcott：瞭解更多關於任何數據結構的最好方法是對它們進行編碼，針對一些實際的輸入大小（可能是巨大的，隨機的等）運行它們，然後進行比較。我建議你在codechef.com上解決一些編程問題，它確實幫助我獲得了所有這些花哨的DS的感受！你可以通過這種方式發現更多的DS。 –

非常感謝codechef.com的想法。 – Alcott

所以我想知道哈希總是最好的東西，高速查找？

否。正如評論中所述：

從來沒有這樣的事情[某些普通問題]的最佳數據結構。一切都與案例有關。嘗試和基數樹可能對字符串很好，因爲無論如何你都需要閱讀字符串。陣列允許簡單和偉大的緩存效率 - 而通常最適合小規模的靜態信息
我曾經回答病例相關的問題，其中一棵樹可能會更好然後一個哈希表：Hash Table v/s Trees

，如果我想要什麼高查詢速度和更少的空間成本？

這兩個可能是自相矛盾。即使是大小爲X的散列表的簡單示例與大小爲2*X的散列表的簡單示例也是如此。較大的哈希表不太可能遇到衝突，因此預計會比較小的那個更快。

是否有任何關於高速查找和空間效率數據結構或算法的材料（書籍或論文）？

Introduction to Algorithms所使用的主要數據結構通過提供一個良好的步行。所開發的任何算法都試圖提供一個很好的空間和時間效率，但如前所述，這是一種折衷，而對於其他算法，某些算法對於特定情況可能會更好。
爲特定問題選擇正確的算法/數據結構/設計是工程所關注的，不是嗎？

來源

2012-09-20 13:35:32 amit

散列表是一個很好的通用結構，但如果散列函數不適合輸入數據，它們可能會失敗壯觀。最壞的情況查找是O（n）。正如你所提到的，它們也浪費了一些空間其他通用結構（如平衡二叉搜索樹）的平均情況比哈希表的情況差，但情況表現更好。這對於實時應用程序非常重要。特里結構是針對字符串查找量身定製的更特殊用途的結構。

來源

2012-09-20 13:39:08 japreiss

散列最適合請求高查找速度的應用程序嗎？

回答

相關問題