Java 中 HashMap 的奇怪行为

Question

我在下面 class.

中发现 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);
    }
  }
}

当我使用 new Employee( "", i) 作为在地图中存储数据的键时，它工作正常并在第 12 个节点插入后调整地图大小。但在使用 new Employee( i+"", i) 作为键，它表现出奇怪的行为，在使用此键添加第 10 个元素时，它将地图的大小从 16 调整为 32，在添加第 11 个元素时，它再次将地图的大小从 32 调整为 64。如果您发现此行为的任何原因，请提供帮助。

Answer 1

如 @G_H 所述，我相信您指的是地图的内部结构，可通过调试器查看。 HashMap 使用 hashCode() 方法对 "buckets".

中的对象进行分组

您重写的 hashCode() 方法使用了 String 成员 a 的值。当 a 为 "" 时，其哈希码为 0，因此您插入的元素的哈希码彼此相对接近，而不是将 a 设置为具有更高哈希码的更有意义的字符串。

出于某种原因（取决于哈希桶的具体实现方式），当哈希码值相距较远时，HashMap 对象决定尽快扩大其内部结构。

对于您插入的元素，看一下它们的哈希码值，它就会有意义。

Answer 2

我试过重写你代码的 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);
}

Answer 3

原因 - Java 中 HashMap 的新组织 8. 当特定 bin 中的列表变得太长时 HashMap 将该列表迁移到树而不是链表 - 过程称为树化。

TREEIFY_THRESHOLD = 8 表示当在给定的 bin 中有 8 个条目时，给定的 bin 应该将冲突值存储在二叉树中而不是链表（从而改变此 bin 的搜索复杂度从 O(n) 到 O(log n).

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

方法 treeifyBin 将 bin 中的所有链接节点替换为散列，除非 table 太小，在这种情况下它会调整 table;

所以在你的情况下，你得到 64 大小（此代码使大小调整两次，将制表符大小增加到 32 和 64 (MIN_TREEIFY_CAPACITY)）：

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

Java 中 HashMap 的奇怪行为

Strange behavior of HashMap in Java

java

hashmap

hashcode