Java中HashMap的奇怪行爲

我發現hashmap的一些奇怪行爲在下面的類中。Java中HashMap的奇怪行爲

class Employee { 

    private String a; 
    private int b; 

    public Employee(String a, int b) { 
    this.a = a; 
    this.b = b; 
    } 

    @Override 
    public int hashCode() { 
    final int prime = 31; 
    int result = 1; 
    result = prime * result + ((a == null) ? 0 : a.hashCode()); 
    result = prime * result + b; 
    return result; 
    } 

    @Override 
    public boolean equals(Object obj) { 
    if (this == obj) 
     return true; 
    if (obj == null) 
     return false; 
    if (getClass() != obj.getClass()) 
     return false; 
    Employee other = (Employee) obj; 
    if (a == null) { 
     if (other.a != null) 
      return false; 
    } else if (!a.equals(other.a)) 
     return false; 
    if (b != other.b) 
     return false; 

    return true; 
    } 

    public static void main(String[] args) { 
    HashMap<Employee,Integer> map = new HashMap<>(); 

    for(int i = 0; i < 13; i++) { 
     map.put(new Employee(i + "", i), i + i); 
    } 
    } 
}

當我使用新的Employee（「」，i）的作爲鍵在地圖存儲數據時，它工作正常和調整大小12節點插入後地圖。但在使用新員工（i +「」，i）作爲鍵時，它顯示出奇怪的行爲，使用此鍵添加第10個元素時，它將地圖的大小調整爲16到32，並添加第11個元素，然後再次調整大小映射到64. 如果您發現此行爲的任何原因請幫助。

來源

2017-05-16 Varun Bansal

你是如何觀察這種行爲？用調試器？你可能在談論內部的大小，而不是地圖中的實際數量，對吧？ –

是的，在調試模式下，你可以檢查添加第10個元素，它調整大小從16到32 ... –

的理由 - 這個過程被稱爲treeifying - 在Java中8.當特定格內部列表變得太長HashMap遷移該列表的樹，而不是一個鏈表的HashMap的新組織。

TREEIFY_THRESHOLD = 8表明，當給定的倉內有8個條目，則代替的鏈表，給定倉應存儲在二叉樹衝突值（由此從爲O（n）到變化的搜索複雜性與此箱O（log n）。

if (binCount >= TREEIFY_THRESHOLD - 1) 
       treeifyBin(tab, hash);

方法treeifyBin替換斌所有鏈接節點的哈希表，除非是太小了，在這種情況下，它會調整表;

所以你的情況，你會得到64尺寸（此代碼調整兩次，增加標籤的尺寸爲32和64（MIN_TREEIFY_CAPACITY））：

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 
      resize();

來源

2017-05-16 11:25:29 Olga

由於@G_H提到，我相信你指的是地圖的內部結構，通過調試器可見。 HashMap使用hashCode（）方法對「桶」中的對象進行分組。

重寫的hashCode（）方法使用String成員a的值。當a是「」時，其哈希碼爲0，因此您插入的元素的哈希碼彼此相對更接近，而不是將哈希碼設置爲更有意義的字符串。

由於某些原因（取決於哈希桶如何正確實現），當哈希碼值進一步分開時，HashMap對象決定儘早擴大其內部結構。

對於你插入的元素，看看他們的哈希碼值，它會有道理。

來源

2017-05-16 10:37:00

它實際上是「更好的擴散元素」（如字符串「a == i +」「'）導致地圖調整兩次。正如@Olga發現這是由於** treefying **開始，但我想知道爲什麼所有這些值都會導致map將它們放入一個bin中。 – diginoise

我試着重寫代碼的has方法。您的實現（使用反射來獲取地圖信息），

Loop 0 : Capacity : 16, Factor : 12, Current Size : 1 
Loop 1 : Capacity : 16, Factor : 12, Current Size : 2 
Loop 2 : Capacity : 16, Factor : 12, Current Size : 3 
Loop 3 : Capacity : 16, Factor : 12, Current Size : 4 
Loop 4 : Capacity : 16, Factor : 12, Current Size : 5 
Loop 5 : Capacity : 16, Factor : 12, Current Size : 6 
Loop 6 : Capacity : 16, Factor : 12, Current Size : 7 
Loop 7 : Capacity : 16, Factor : 12, Current Size : 8 
Loop 8 : Capacity : 32, Factor : 24, Current Size : 9 
Loop 9 : Capacity : 64, Factor : 48, Current Size : 10 
Loop 10 : Capacity : 64, Factor : 48, Current Size : 11 
Loop 11 : Capacity : 64, Factor : 48, Current Size : 12 
Loop 12 : Capacity : 64, Factor : 48, Current Size : 13

如下重寫後，

public int hashCode() { 
    final int prime = 31; 
    return prime * this.b; 
}

然後將大小增加不如預期，

Loop 0 : Capacity : 16, Factor : 12, Current Size : 1 
Loop 1 : Capacity : 16, Factor : 12, Current Size : 2 
Loop 2 : Capacity : 16, Factor : 12, Current Size : 3 
Loop 3 : Capacity : 16, Factor : 12, Current Size : 4 
Loop 4 : Capacity : 16, Factor : 12, Current Size : 5 
Loop 5 : Capacity : 16, Factor : 12, Current Size : 6 
Loop 6 : Capacity : 16, Factor : 12, Current Size : 7 
Loop 7 : Capacity : 16, Factor : 12, Current Size : 8 
Loop 8 : Capacity : 16, Factor : 12, Current Size : 9 
Loop 9 : Capacity : 16, Factor : 12, Current Size : 10 
Loop 10 : Capacity : 16, Factor : 12, Current Size : 11 
Loop 11 : Capacity : 16, Factor : 12, Current Size : 12 
Loop 12 : Capacity : 32, Factor : 24, Current Size : 13

雖然我無法解釋可以肯定的是，下面的HashMap實現代碼片段指出了散列計算值可能會增加Map的大小。

void More addEntry(int hash, K key, V value, int **bucketIndex**) { 
    Entry<K,V> e = table[bucketIndex]; 
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 
    if (size++ >= threshold) 
     resize(2 * table.length); 
}

來源

2017-05-16 11:18:13 Sekar

Java中HashMap的奇怪行爲

回答

相關問題