Java HashMap 内部实现

Question

Java HashMap 内部实现

3

我对Java的HashMap类有一些疑问。我的理解是：

 transient Entry[] table;

将根据

hashCode()的值来保存数据。我需要知道什么时候会初始化此数组。这个数组的长度是基于我们在HashMap初始化期间定义的容量还是如果在调用构造函数时未定义，则默认容量为16？

HashCode()如何缩放到数组索引？例如，如果hashCode()有一个很大的值，它如何缩放到类似于10、20的数组索引上？

我已经阅读过当达到阈值时会发生rehashing的内容。例如，在默认情况下，当16是容量且0.75是负载因子时，那么阈值为16 * 0.75 = 12。一旦添加了12个项目，就会发生rehashing并增加容量。这是否意味着table数组大小会增加？

- San

2个回答

0

public HashMap(int initialCapacity, float loadFactor) {
     if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity);
     if (initialCapacity > MAXIMUM_CAPACITY)
         initialCapacity = MAXIMUM_CAPACITY;

     if (loadFactor <= 0 || Float.isNaN(loadFactor))
         throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);

     // Find a power of 2 >= initialCapacity
     int capacity = 1;
     while (capacity < initialCapacity)
         capacity <<= 1;
     this.loadFactor = loadFactor;
     threshold = (int)(capacity * loadFactor);
     table = new Entry[capacity];
     init();
 }

上面的代码块解释了何时以及如何填充table。一旦重新散列发生，它不会增加表数组的大小，因为您可以一次声明数组大小；它每次都会创建一个具有更新大小的新数组：

void resize(int newCapacity) {
     Entry[] oldTable = table;
     int oldCapacity = oldTable.length;
     if (oldCapacity == MAXIMUM_CAPACITY) {
         threshold = Integer.MAX_VALUE;
         return;
     }
     Entry[] newTable = new Entry[newCapacity];
     transfer(newTable);
     table = newTable;
     threshold = (int)(newCapacity * loadFactor);
 }

- Helios

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，

- entpnerd · Accepted Answer

由于您的帖子有很多问题，我将列举您的问题作为我的答案的一部分。另外，请注意，我会参考Java 1.8 b132的HashMap源代码来回答问题。

Q: 我需要知道这个数组何时被初始化。
A: 只有在数据首次输入到映射中（例如调用put()方法）时，table数组才会被初始化。除非调用复制构造函数或将映射反序列化为对象，否则它不会作为映射本身的实例化的一部分而发生。
Q: 数组长度是基于我们在HashMap初始化期间定义的容量还是在调用构造函数时未定义时默认的16个容量？
A: 正确，table数组的长度是基于您传递给构造函数的初始容量。当未指定初始容量并调用默认构造函数时，使用默认容量。
Q: 哈希码如何缩放到数组索引？
A: 关于执行此操作的实际代码，请参见 putVal()方法的实现。基本上，代码获取非常大的哈希值，并对其进行与表的最后一个元素索引的按位与运算。这有效地随机化了键/值对与table数组的位置。例如，如果哈希值为333（二进制为101001101），而table数组大小为32（100000），则最后一个元素索引将为31（11111）。因此，选择的索引将为11111&101001101 == 01101 == 13。
Q: 我已经了解到当达到阈值时，会发生重新哈希。...这是否意味着表数组大小会增加？
A: 或多或少是的。当超过threshold时，表将被调整大小。请注意，通过调整大小，现有的table数组不会被修改。相反，将创建一个新的table数组，其容量是第一个table数组的两倍。有关详细信息，请参见resize()方法的实现。