必須使用數組實現哈希表嗎？

必須使用數組實現哈希表嗎？另一種數據結構是否會達到相同的效率？如果是，爲什麼？如果不是，那麼數據結構必須滿足哪些條件才能確保數組提供的效率相同？必須使用數組實現哈希表嗎？

2012-09-03 psyko666

是否必須使用數組實現哈希表？

號你可以實現HashTable接口與其他數據結構besided的arrray。例如。紅黑樹（java的TreeMap）。
這提供O(logN)訪問時間。
但Hash Table預計有O(1)訪問時間（最好的情況 - 沒有衝突）。
這隻能通過一個在恆定時間內提供隨機訪問可能性的數組來實現。

數據結構必須滿足什麼條件才能確保數組提供的效率相同？

必須具有與數組相當的性能（小於O(N)）。一個樹形圖有O(logN)最差訪問時間爲全部操作

來源

2012-09-03 15:54:40 Cratylus

我認爲哈希表是一個與基於比較的映射完全不同的野獸。這些差異不僅僅在理論上和實際情況中，它們都涉及到對密鑰的要求：散列表需要散列函數和相等性，而另一個則需要總排序。 – delnan

@delnan：這取決於你如何解釋OP.My的觀點是'HashTable'是'Dictionary'數據結構的實現/擴展。它提供了一個'Dictionary'的界面。抽象數據結構可以具有各種實現，例如一個由數組或TreeMap支持的'HashTable'。如果定義和*一樣嚴格，那麼HashTable表示一個* hash函數*，只能由一個數組支持 – Cratylus

謝謝你的回答，並且對於遲到的回覆感到抱歉，我總是忘記檢查一下stackoverflow，再次感謝你 – psyko666

必須使用數組實現哈希表嗎？

回答

相關問題