深入理解HashMap扩容机制（JDK7）

Hashmap扩容机制

说明：该系列分为JDK7和JDK8，当前文章只讲解JDK7，JDK8扩容讲解请移步《深入理解HashMap扩容机制（JDK8）》

一、扩容时机

网上总结的会有很多，但大多都总结的不够完整或者不够准确。大多数可能只说了满足我下面条件一的情况。扩容必须满足两个条件：

1. 存放新值的时候当前已有元素的个数必须大于等于阈值；
2. 存放新值的时候当前存放数据发生hash碰撞（当前key计算的hash值换算出来的数组下标位置已经存在值）

二、查看源码

put()方法源码

	public V put(K key, V value) {
　　　　//判断当前Hashmap(底层是Entry数组)是否存值（是否为空数组）
　　　　if (table == EMPTY_TABLE) {
　　　　　　inflateTable(threshold);//如果为空，则初始化
　　　　}
　　　　
　　　　//判断key是否为空
　　　　if (key == null)
　　　　　　return putForNullKey(value);//hashmap允许key为空
　　　　
　　　　//计算当前key的哈希值　　　　
　　　　int hash = hash(key);
　　　　//通过哈希值和当前数据长度，算出当前key值对应在数组中的存放位置
　　　　int i = indexFor(hash, table.length);
　　　　for (Entry<K,V> e = table[i]; e != null; e = e.next) {
　　　　　　Object k;
　　　　　　//如果计算的哈希位置有值（及hash冲突），且key值一样，则覆盖原值value，并返回原值value
　　　　　　if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
　　　　　　　　V oldValue = e.value;
　　　　　　　　e.value = value;
　　　　　　　　e.recordAccess(this);
　　　　　　　　return oldValue;
　　　　　　}
　　　　}
 
　　　　modCount++;
　　　　//存放值的具体方法
　　　　addEntry(hash, key, value, i);
　　　　return null;
　　}

在put()方法中有调用addEntry()方法，这个方法里面是具体的存值，在存值之前还要判断是否需要扩容

	void addEntry(int hash, K key, V value, int bucketIndex) {
　　　　//1、判断当前个数是否大于等于阈值
　　　　//2、当前存放是否发生哈希碰撞
　　　　//如果上面两个条件否发生，那么就扩容
　　　　if ((size >= threshold) && (null != table[bucketIndex])) {
　　　　　　//扩容，并且把原来数组中的元素重新放到新数组中
　　　　　　resize(2 * table.length);
　　　　　　hash = (null != key) ? hash(key) : 0;
　　　　　　bucketIndex = indexFor(hash, table.length);
　　　　}
 
　　　　createEntry(hash, key, value, bucketIndex);
	}

Entry类的源码

	static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;// 通过next构成一个单向链表
        int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
	｝

如果需要扩容，调用扩容的方法resize()

	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()方法把原数组中的值放到新数组中
　　　　transfer(newTable, initHashSeedAsNeeded(newCapacity));
　　　　//设置hashmap扩容后为新的数组引用
　　　　table = newTable;
　　　　//设置hashmap扩容新的阈值
　　　　threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
　　}

transfer()在实际扩容时候把原来数组中的元素放入新的数组中

	void transfer(Entry[] newTable, boolean rehash) {
　　　　int newCapacity = newTable.length;
　　　　for (Entry<K,V> e : table) {
　　　　　　while(null != e) {
　　　　　　　　Entry<K,V> next = e.next;
　　　　　　　　if (rehash) {
　　　　　　　　　　e.hash = null == e.key ? 0 : hash(e.key);
　　　　　　　　}
　　　　　　　　//通过key值的hash值和新数组的大小算出在当前数组中的存放位置
　　　　　　　　int i = indexFor(e.hash, newCapacity);
　　　　　　　　e.next = newTable[i];
　　　　　　　　newTable[i] = e;
　　　　　　　　e = next;
　　　　　　}
　　　　}
　　}

JDK7版本及以前使用是：头插法（对比JDK8使用的是尾插法）
注：使用头插法在多线程扩容的时候可能会导致循环指向，从而在获取数据get()的时候陷入死循环，导致线程执行无法结束。

头插法：
后来的（新插入的）节点会被插入到头部，并将head节点指向当前新节点，再将当前新节点的next指针指向之前的头部节点，这样整个链表越早插入的就逐渐到了链表的尾部，越晚插入的就存放在了链表的头部。

在扩容的时候，先取头部节点，然后把头部节点放到新对应数组下标的链表处，由于头插法，最早取出的节点会被最先放进，并逐步变成链表的最尾部，如果多线程执行扩容，将数组下标3位置处链表存入的A->B->C，扩容时存入到新的数组（假设扩容后A/B/C还在同一个链表上），线程1取第一个节点A被挂起，挂起的A节点的next指向B节点，而线程2扩容将头部B节点（原头部A节点已经被取走，B节点成为原链表的头结点）放入新的链表时，A节点被先放但没有完成，线程2在放入B节点后，B节点的next指向之前放入的A节点，当线程1执行的时候本身A的next指向B，这样就行程了循环引用，最后存入C节点，并将C节点的next指向B，最终就变成C->B-><-A，在get()方法执行到该数组下标时，遍历链表查找的时候就会出现死循环。

尾插法：
元素插入的时候都是从尾部插入，这样新进来的就在头部，后进来的就在尾部，扩容的时候，先进来的先出，指向next和扩容前方向一致，所以不存在循环指向的问题。

JDK7存入元素到同一个数组下标位置的链表处，每次存入的新元素是在链表的头部：

	HashMap map = new HashMap<Integer,Integer>(16);
    map.put(1,1);
    map.put(16,2);
    map.put(35,3);
    map.put(50,4);
    map.put(69,5);
    map.put(84,6);
    map.put(103,7);
    map.put(136,8);
    map.put(153,9);
    map.put(170,10);
    map.put(187,11);
    map.put(204,12);
    map.put(221,13);

如上面代码，在前12个元素存入数字下标为1的位置，那么链表是如下构成

再次总结解读代码：

	public V put(K key, V value) {

        // ...省略很多源码，看红色的方法

        modCount++;
        addEntry(hash, key, value, i);// i为上面省略处计算的数组下标
        return null;
	}

	void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex]; // bucketIndex 为数组下标，第一个元素进来时table[下标位置]=null,所以对应代码 put(1,1) 上图node第一个节点的 next 就为空
        table[bucketIndex] = new Entry<>(hash, key, value, e);// e表示上一个节点，将上一个节点放到新节点的next处——》并且将新new Entry对象给到当前table[数组下标位置]
        size++;
    }

所以这个过程下来，新节点就在链表的头部位置，最早被加入的Entry节点在最尾的位置。

三、总结

Hashmap的扩容需要满足两个条件：当前数据存储的数量（即size()）大小必须大于等于阈值；当前加入的数据是否发生了hash冲突。

因为上面这两个条件，所以存在下面这些情况

• 就是hashmap在存值的时候（默认大小为16，负载因子0.75，阈值12），可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值，每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。

• 当然也有可能存储更多值（超多16个值，最多可以存27个值）都还没有扩容。原理：前11个值全部hash碰撞，存到数组的同一个位置（虽然hash冲突，但是这时元素个数小于阈值12，并没有同时满足扩容的两个条件。所以不会扩容），[在存入第12个元素的时候，还是存入前面11个元素所在的下标位置，因为存入之前此时比较当前元素个数 11<12(16*0.75)，所以在存入第12个元素的时候不会发生扩容，那么还有15个数据下标的位置是空的，后面所有存入的15个值全部分散到数组剩下的15个位置（这时元素个数大于等于阈值，但是每次存入的元素并没有发生hash碰撞，也没有同时满足扩容的两个条件，所以叶不会扩容），前面12+15=27，所以在存入第28个值的时候才同时满足上面两个条件，这时候才会发生扩容现象。

该文章来自于本人多年前发表于博客园的原创作品：《深入理解HashMap的扩容机制》，转载请注明出处。