哪些內存使用較少？將項目添加到Clojure原子的長列表或項目到地圖？

Question

我正在處理某些事情，我更新了許多在Clojure原子中排序的項目。我可以將項目存儲爲矢量或作爲索引映射。這些項目可能有數百萬個附件，所以我想選擇最高效的內存結構。

我的直覺是，加入新的項目到地圖中使用相比，經過數百次迭代的矢量內存少，但想獲得一個明確的答案：它可以是載體

所以：

["a" "b" ... "y"] -> ["a" "b" ... "y" "z"] 

並配有地圖將是：

{0 "a" 1 "b" ... 25 "y"} -> {0 "a" 1 "b" ... 25 "y" 26 "z"} 

那麼這將使用較少的內存？

Answer 1

在Clojure中，向量和散列圖都使用tries作爲他們的基本實現技術。

Clojure的向量直接使用元素的索引作爲密鑰的值，以便查找該值。使用位分區是爲了將索引拆分成可在每個級別用作密鑰的位塊。

另一方面，Clojure的哈希映射哈希提供的索引創建一個鍵來遍歷trie以便找到值。位分區用於哈希索引而不是直接在索引上。

用於遍歷向量和散列映射的實際關鍵字將是一個32位整數。

我期望矢量和散列圖之間的內存使用差異可以忽略不計。哈希映射應該使用更多的內存以迎合關鍵衝突，因此必須具有散列桶的開銷。

關於矢量和散列圖的實現細節available here有更深入的討論。