爲什麼LinkedList作爲HashMap的存儲桶實現而不是另一個Hashmap？

Question

有誰知道爲什麼選擇通過LinkedList而不是另一個Hashmap實現HashMap的桶。看起來如果桶自己變成了HashMap，那麼包含或者得到的就是O（1）而不是O（1）。

Answer 1

想象一下，使用HashMap實現存儲桶，然後發生大量衝突。一個好的散列函數應該儘量消除衝突，但我們正在考慮大量的元素。碰撞現在將存儲在存儲區的HashMap實現中。這個HashMap應該有空間來容納它自己的桶。如果存在如此大量的元素，那麼這個HashMap在它的桶中也會發生多次碰撞呢？即使有一個非常好的散列函數，在某個地方，存儲桶HashMap（例如說B）的桶將開始干擾具有多個桶的HashMap A的桶，其中一個由B實現。

LinkedList不會有這個問題。另外請記住，一旦一個桶被分配給一個HashMap，它就會被阻塞到外面 - 即使它是空的。 LinkedList將動態增長，並且不需要比條目數更多的內存。

總而言之，你當然可以實現你想要的任何東西。你可以使用ArrayList或者只是一個數組。但他們也有自己的問題（刪除導致O（n）調整時間複雜度，數組必須具有固定的大小）。所以考慮到所有的權衡，LinkedList被認爲是最好的選擇。

Answer 2

如果HashMaps在另一個HashMap中作爲存儲桶實現，它仍然會被攤銷O（1）。假設兩個字符串被散列到HashMap的內部數據結構中的相同索引。如果該索引包含另一個HashMap，則這兩個字符串將再次散列到相同索引，但在HashMap存儲區以及中。那麼你將不得不決定如何處理HashMap中的衝突。因此，使用HashMaps實現HashMap作爲桶會產生兩個碰撞而不是一個碰撞。另外，HashMaps比LinkedLists對一組給定的數據使用更多的內存。它們需要比數據條目更多的內存插槽來保證O（1）運行時間的分期。

是的，LinkedLists對於存儲桶並不理想，因爲它需要O（n）次的桶大小來檢索正確的值。 LinkedList存儲桶不應該變得非常大，因爲HashMap應該足夠大，以至於碰撞的頻率是最小的。