它是如何決定一個HashMap已滿，因爲每個HashMap的桶可以包含項目

Question

數量龐大的HashMap的大小是根據負載因子增加，但它是如何決定一個HashMap已滿，因爲每個hashmap存儲桶可以包含大量的條目。爲什麼它會創建新的桶而不是將條目添加到現有的桶中？有什麼方法可以確定一個桶中的條目數量嗎？ 負載因數如何起作用？假設初始容量爲16，加載因子爲0.75，那麼在存儲了多少條目之後，hashmap將被重新存儲？因爲16 * 0.75是12，那麼在我們存儲12個條目後它會被重新映射，還是在12個桶有條目並且剩下的桶是空的時候它會被重新映射？這12個代表什麼？

Answer 1

HashMap的充滿度相對於桶的數量的條目的數量來判斷。通常，這兩個值只是作爲數據成員存儲在散列表中，並在更改時進行更新。

將條目添加到現有的水桶使得HashMap慢，中，因爲你必須看看桶，如果它存在所需的值將在每個項目中不存在項搜索時尤其如此。

想象一下，如果您存儲按名稱索引的記錄。如果你只有300條記錄，按名稱的第一個字母索引它們可能沒有問題。最糟糕的情況是，如果你正在尋找名字以「S」開頭的人，你可能需要查看20條記錄。但是如果你有2000條記錄，你可能想用多於一個字母來索引它們，也就是說，使用多於26個桶。

在實踐中，這是當他們有更大的記錄索引號人做什麼。例如，他們可能會通過將「S」桶拆分爲「Sa-Sk」和「Sl-Sz」來添加一個桶。

Answer 2

因爲如果我們添加進入現有的桶，這些作品將被存儲在桶中的列表格式，它會增加get方法運行時間。 因爲列表需要O（n）來比較一個元素。

Answer 3

它是如何決定散列表已滿？

理論上它不能說是完整的。我們仍然可以將任意數量的對象添加到存儲區的鏈接列表中（如您所說）。

假設這麼多的（鍵，值）條目被添加到HashMap中。理想情況下，HashMap函數（get，put，contains）必須在O（1）中工作。要實現它，每個HashMap桶只能存儲一個（鍵，值）對。每當哈希映射發生衝突時，它都必須重新組織它的底層數據結構以促進理想的哈希。爲每次衝突重新組織內部數據結構是一項複雜的操作，它會降低哈希映射的性能。

因此決定，一些碰撞將被容忍。當映射中元素的數量達到最大閾值時，完成哈希映射的重新哈希。重新調整時間，底層桶將變成雙倍，並且（鍵值）將被映射到這些新的桶組。

通過這樣做，桶中（鍵，值）對的數量通常會減少。 因此，通過使用額外的空間，散列圖效果更好。

有什麼方法可以確定存儲桶中的條目數量嗎？

在HashMap中，我們無法知道每個桶中的條目數。即使我們知道我們不能只分割那個桶。例如，HashMap中有16個存儲桶，如果我們知道許多（Key，Value）對映射到一個存儲桶，我們不能簡單地將該存儲桶拆分爲2.我們不能明確地創建一個新的存儲桶來共享負載的那個桶。在這兩種情況下，桶計數應該變爲17.但是HashMap應該總是將桶的數量設置爲2的n次方。所以我們不能做任何特別的事情來了解桶中的條目數量。所以在HashMap中，存儲桶級決策將不會完成。全局決策將根據條目數量在HashMap中完成。