哈希表和列表並排嗎？

我需要一個有序的數據結構，但也提供快速的隨機訪問和插入和刪除。鏈表被排序和快速插入並刪除，但他們給予緩慢的隨機訪問。散列表提供快速的隨機訪問，但沒有排序。哈希表和列表並排嗎？

所以，它們似乎很好地使用它們在一起。在我當前的解決方案中，我的Hashtable包含列表的迭代器，List包含實際的項目。好而有效。好吧，它需要雙倍的內存，但這不是一個問題。

我聽說一些樹形結構能做到這一點還，但他們一樣快，這個解決方案？

來源

2010-11-07 glhfgg

如果我沒錯，內存使用不應該成爲一個問題。所有你需要的是爲鏈表存儲一些額外的指針/引用，對吧？ – TinkerTank 2010-11-07 14:42:16

你想如何隨機訪問？你會如何隨機訪問？ – nawfal 2014-06-06 08:06:58

我知道的最有效的樹結構是Red Black Tree，它不像解決方案那樣快，因爲它對所有操作都有O（log n），而對於一些操作（即使不是全部操作），您的解決方案有O（1）。

如果內存不是問題，並且您確定您的解決方案是O（1），這意味着在結構中添加/刪除/查找項目所需的時間與您擁有的項目數量無關，請參閱。

來源

2010-11-07 14:28:34

的Java實際上包含LinkedHashTable，它類似於您所描述的數據結構。有時候這可能會令人驚訝地有用。

樹結構可以工作爲好，看他們能執行（O log n）的時間隨機存取（和大多數其他操作）。不如哈希表（O 1）快，但仍然很快，除非您的數據庫非常大。

樹木的唯一真正的好處是，你不需要事先對容量決定。一些HashTable實現可以根據需要增加容量，但只需通過將所有項目複製到一個新的更大的散列表（當它們的容量已超出其容量時非常緩慢）即可實現。（O N）

來源

2010-11-07 14:30:25 TinkerTank

你應該考慮一個Skip List，這是一個有序鏈表與O（log n）的訪問時間。換句話說，你可以枚舉它O（n）和索引/插入/刪除是O（log n）。

來源

2010-11-07 14:34:42 Gabe

樹是爲此而製作的。最合適的是自我平衡的樹像AVL tree或Red Black tree。如果處理的數據量非常大，則創建B-tree（例如，它們用於文件系統）也可能很有用。

關於您的實現：它可能是或多或少高效然後樹木取決於數據量和你一起工作和散列表實施。例如。一些非常密集數據的哈希表可能不會在O（1）中提供訪問，而是在O（log n）甚至O（n）中提供訪問。另外請記住，從數據計算散列也需要一些時間，因此對於退出的小數據來說，計算散列的絕對時間可能更多，因此可能在樹中搜索它。

來源

2010-11-07 14:49:15 ffriend

你所做的幾乎是正確的選擇。

這個很酷的事情是，通過使用雙端雙向鏈表向現有映射實現添加排序實際上並沒有改變其漸近複雜性，因爲所有相關的列表操作（添加和刪除）都有一個Θ（1）的最壞情況步驟複雜性。（是的，刪除也是Θ（1）。究其原因通常是Θ（n）是因爲你必須找到元素刪除第一，這是Θ（N），但實際刪除本身是Θ（1）。在這個特定的情況下，你讓地圖做的發現，這是一樣的東西Θ（1）攤銷最壞情況步驟複雜或Θ（日誌_b＆thinsp; n）的最壞情況下的步驟的複雜性，這取決於地圖的類型）

例如，Ruby 1.9中的Hash類是一個有序映射，它至少在YARV和Rubinius中作爲嵌入鏈表的哈希表實現。

樹木通常具有Θ最壞情況步驟複雜（日誌_b＆thinsp; N）用於隨機接入，而散列表可以是在最壞的情況更差（Θ（n））的，但通常緩衝至Θ （1），前提是你不要搞亂哈希函數或調整大小函數。

[注：我故意只在這裏談論漸近行爲，又名「無限大」的收藏。如果你的系列很小，那麼只需選擇一個具有最小常數的系列。]

來源

2010-11-07 16:41:01

哈希表和列表並排嗎？

回答

相關問題