java中的哈希碼桶分佈

Question

假設我需要在Hashset中存儲1000個對象，最好是我有1000桶包含每個對象（通過爲每個對象生成哈希碼的唯一值）還是有10個桶大致包含100個對象？

具有獨特存儲桶的一個優點是，我可以在調用equals（）方法時節省執行週期嗎？

爲什麼設置桶的數量並儘可能均勻地分配它們中的對象很重要？

什麼應該是理想的對象鬥比？

Answer 1

爲什麼設置桶的數量並儘可能均勻地分配它們中的對象很重要？

A HashSet應該能夠平均確定O（1）時間的成員資格。從documentation：

這個類提供了基本操作（添加，刪除，包含和大小）固定的時間性能，假定哈希函數將分散的桶中正確的元素。

算法a​​用於實現此目的是檢索該對象的哈希碼並使用它來查找正確的桶。然後它遍歷桶中的所有項目，直到找到一個相等的項目。如果存儲桶中的項目數大於O（1），則查找將比O（1）時間花費更長的時間。

在最壞的情況下 - 如果所有項目都散列到同一個桶中 - 則需要O（n）時間來確定對象是否在該集合中。

什麼應該是理想的對象鬥比？

這裏有一個時空折衷。增加桶數減少了碰撞的機會。但是它也增加了內存需求。哈希集有兩個參數initialCapacity和loadFactor，它們允許您調整HashSet應創建的桶數。默認加載因子爲0.75，對於大多數用途來說這很好，但如果您有特殊要求，則可以選擇另一個值。

有關這些參數的詳細信息可以在文檔中找到了HashMap：

此實現提供穩定的性能爲基本操作（get和put），假定哈希函數將適當分散的元素中水桶。迭代集合視圖需要的時間與HashMap實例的「容量」（桶的數量）加上其大小（鍵值映射的數量）成正比。因此，如果迭代性能很重要，不要將初始容量設置得太高（或者負載因子太低）是非常重要的。

HashMap的一個實例有兩個影響其性能的參數：初始容量和負載因子。容量是哈希表中桶的數量，初始容量就是哈希表創建時的容量。加載因子是散列表在其容量自動增加之前被允許獲得的滿量程的度量。當哈希表中條目的數量超過負載因子和當前容量的乘積時，通過調用rehash方法，容量大約增加一倍。

作爲一般規則，默認加載因子（.75）提供了時間和空間成本之間的良好折衷。較高的值會減少空間開銷，但會增加查找成本（反映在大部分HashMap類的操作中，包括get和put）。在設置初始容量時，應考慮映射中的條目數量及其負載因子，以儘量減少重新運行操作的次數。如果初始容量大於最大入口數除以負載因子，則不會發生重新刷新操作。

Answer 2

對於處理器來說，每個元件大約一個存儲桶比較好，對於存儲器而言，存儲桶的數量太多。 Java將從少量存儲桶開始，一旦開始填充，它就會自動增加HashSet的容量，因此除非應用程序出現問題，並且您已將哈希集標識爲原因，否則您並不需要關心它。

如果你在每個桶中有多個元素，查找開始花費更長的時間。如果你有很多空的桶，你使用的內存比你需要的多，並且迭代這些元素需要更長的時間。

這看起來像是等待發生的過早優化 - 但在大多數情況下，默認的構造函數很好。

Answer 3

Object.hashCode()是int類型的，你只能有2^32不同的值，這就是爲什麼你創建桶和它們之間分配的對象。

編輯：如果您正在使用2^32桶儲存2^32的對象，然後挑釁獲取操作會給你不斷的複雜性，但是當你插入一個一個元件蓄積2^32對象則再次提出將不是方法執行，如果我們正在使用Object[]作爲存儲桶，然後每次超過array的長度時，它將創建新的陣列，其中更大的尺寸並將元素複製到此處。這個過程會增加複雜性。這就是爲什麼我們利用equals和hashcode的比例，並通過提供更好的hashing algorithm由Hashsets本身完成。