Java中几种容器的扩容机制总结

发表于 | 分类于 |

本文总结Java中常用容器的扩容机制，扩容的过程是很耗时的，理解这些容器的扩容机制对开发来说还是很有必要的。

Java中的部分需要扩容的内容总结如下：

第一部分：HashMap，HashSet，Hashtable

第二部分：ArrayList，Vector，CopyOnWriteArrayList

第三部分：StringBuffer，StringBuilder

本文从以下几个方面分析（JDK1.8）：

  1. 初始容量
  2. 扩容机制
  3. 同类型之间的对比

1.1 HashMap

HashMap在JDK1.8中 底层数据结构上采用了数组＋链表＋红黑树。

A. 初始容量默认为1<<4 (16)，最大容量为1<<30，源码：

1
2
3
4
5
6
7
8
9
10
11
/**
  * The default initial capacity - MUST be a power of two.
  */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
  * The maximum capacity, used if a higher value is implicitly specified
  * by either of the constructors with arguments.
  * MUST be a power of two <= 1<<30.
  */
static final int MAXIMUM_CAPACITY = 1 << 30;

B. 扩容加载因子为0.75，当HashMap中元素数量大于等于数组长度×加载因子(16×0.75=12) 时，触发扩容，扩容后的数组长度为原来的2倍。Node<K,V>[] resize()方法是扩容的核心源码：

HashMap的扩容可以分为三种情况：

第一种：使用默认构造方法初始化HashMap。从下面resize()源码可以知道HashMap在一开始初始化的时候会返回一个空的table，并且thershold为0。因此第一次扩容的容量为默认值DEFAULT_INITIAL_CAPACITY也就是16。同时threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。

第二种：指定初始容量的构造方法初始化HashMap。那么从下面源码可以看到初始容量会等于threshold，接着threshold = 当前的容量（threshold） * DEFAULT_LOAD_FACTOR。

第三种：HashMap不是第一次扩容。如果HashMap已经扩容过的话，那么每次table的容量以及threshold量为原有的两倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
   * The load factor used when none specified in constructor.
   */
 static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table; // 首次初始化后table为null
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;  // 默认构造器的情况下为0
        int newCap, newThr = 0;
        if (oldCap > 0) {  // table扩容过，说明不是第一次扩容
            if (oldCap >= MAXIMUM_CAPACITY) {  // 当前table容量大于最大值的时候返回当前table
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // table的容量乘以2，threshold的值也乘以2，符合上述第三种扩容情况
                newThr = oldThr << 1; 
        }
        else if (oldThr > 0) 
            // 使用带有初始容量的构造器时，table容量为初始化得到的threshold
            newCap = oldThr;
        else {           
            // 默认构造器下进行扩容
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            // 使用带有初始容量的构造器在此处进行扩容
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
             // 对新扩容后的table进行赋值
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

1.2 HashSet

初始容量定义：16。因为构造一个HashSet，其实相当于新建一个HashMap，然后取HashMap的Key。

扩容机制和HashMap一样。

1.3 Hashtable

初始容量定义：capacity (11)。

扩容加载因子(0.75)，当超出默认长度（int）（11 × 0.75）=8时，扩容为old×2+1。

扩容核心源码rehash()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
protected void rehash() {
        int oldCapacity = table.length;
        Entry<?,?>[] oldMap = table;

        // overflow-conscious code
        int newCapacity = (oldCapacity << 1) + 1;
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

        modCount++;
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;

        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                Entry<K,V> e = old;
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = (Entry<K,V>)newMap[index];
                newMap[index] = e;
            }
        }
    }

小结：HashMap和Hashtable区别

  1. 继承不同

public class Hashtable extends Dictionary implements Map
public class HashMap extends AbstractMap implements Map

  1. 同步性

Hashtable 中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下，可以直接使用Hashtable，但是要使用HashMap的话就要自己增加同步处理了。

  1. null键和null值

Hashtable中，key和value都不允许出现null值。

HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，即可以表示 HashMap中没有该键，也可以表示该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。

  1. 遍历方式

两个遍历方式的内部实现上不同。Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式 。

  1. 哈希值

Hashtable直接使用对象的hashCode。而HashMap重新计算hash值。

  1. 扩容

Hashtable中hash数组默认大小是11，增加的方式是 old × 2+1。HashMap中hash数组的默认大小是16， 增加的方式是 old × 2。

2.1 ArrayList

初始容量：10

扩容：oldCapacity + (oldCapacity >> 1)，即原集合长度的1.5倍。核心扩容方法grow()，扩容源码：

ArrayList的扩容也可以分为三种情况进行分析：

  1. 当前数组是由默认构造方法生成的空数组并且第一次添加数据。此时minCapacity等于默认的容量（10）那么根据下面逻辑可以看到最后数组的容量会从0扩容成10。而后的数组扩容才是按照当前容量的1.5倍进行扩容。
  2. 当前数组是由自定义初始容量构造方法创建并且指定初始容量为0。此时minCapacity等于1那么根据下面逻辑可以看到最后数组的容量会从0变成1。这边可以看到一个严重的问题，一旦我们执行了初始容量为0，那么根据下面的算法前四次扩容每次都 +1，在第5次添加数据进行扩容的时候才是按照当前容量的1.5倍进行扩容。
  3. 不是第一次扩容，当扩容量（newCapacity）大于ArrayList数组定义的最大值后会调用hugeCapacity来进行判断。如果minCapacity已经大于Integer的最大值（溢出为负数）那么抛出OutOfMemoryError，否则的话根据与MAX_ARRAY_SIZE的比较情况确定是返回Integer最大值还是MAX_ARRAY_SIZE。这边也可以看到ArrayList允许的最大容量就是Integer的最大值（-2的31次方~2的31次方减1）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
private static final int DEFAULT_CAPACITY = 10; //数组默认初始容量

/**
* 定义一个空的数组实例以供其他需要用到空数组的地方调用，其中一处就是使用自定义初始容量构造方法时候如果你指
* 定初始容量为0的时候就会返回
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 是用来使用默认构造方法时候返回的空数组。如果第一次添加数据的话那么数组扩容长度为DEFAULT_CAPACITY=10
* 跟前面的区别就是这个空数组是用来判断ArrayList第一添加数据的时候要扩容多少
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* 数据存的地方它的容量就是这个数组的长度，同时只要是使用默认构造器
* （DEFAULTCAPACITY_EMPTY_ELEMENTDATA ）第一次添加数据的时候容量扩容为DEFAULT_CAPACITY = 10
*/
transient Object[] elementData;
 
private int size; //当前数组的长度

/**
* minCapacitt表示修改后的数组容量，minCapacity = size + 1，此方法是进行add操作时就会调用判断
*/
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 判断看看是否需要扩容
    ensureExplicitCapacity(minCapacity);
}

/**
* 判断当前ArrayList是否需要扩容
*/
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
* 扩容核心方法
*/
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

2.2 CopyOnWriteArrayList

CopyOnWriteArrayList在做修改操作时，每次都是重新创建一个新的数组，在新数组上操作，最终再将新数组替换掉原数组。因此，在做修改操作时，仍可以做读取操作，读取直接操作的原数组。读和写操作的对象都不同，因此读操作和写操作互不干扰。只有写与写之间需要进行同步等待。另外，原数组被声明为volatile，这就保证了，一旦数组发生变化，则结果对其它线程(读线程和其它写线程)是可见的。

CopyOnWriteArrayList并不像ArrayList一样指定默认的初始容量。它也没有自动扩容的机制，而是添加几个元素，长度就相应的增长多少。CopyOnWriteArrayList适用于读多写少，既然是写的情况少，则不需要频繁扩容。并且修改操作每次在生成新的数组时就指定了新的容量，也就相当于扩容了，所以不需要额外的机制来实现扩容。

小结

  1. ArrayList与Vector初始容量都为10。
  2. 扩容机制不同，当超出当前长度时ArrayList扩展为原来的1.5倍，Vector扩容时有一个增量的概念，这个值可以在初始化Vector时作为参数传递，真正的扩容是newCapacity()这个函数，首先它判断增量是否大于0，也就是判断是否有最初设定的增量大小，如果有增量大小，新容量=增量+旧容量，如果没有增量则容量变为原来的两倍。
  3. ArrayList为非线程安全的，处理效率上较Vector快，若同时考虑线程安全和效率，可以使用 CopyOnWriteArrayList。

3.1 StringBuffer

初始容量定义：16。

扩容：因为StringBuffer extends AbstractStringBuilder，所以实际上是用的是AbstractStringBuilder的扩容方法，先将新容量扩大到value的长度乘以2加2，如果不够则直接扩充到所需的容量大小minCapacity。如果够则还要进行如下判断，如果比Integer的最大值还要大会抛OOM异常；否则，如果比MAX_ARRAY_SIZE大，则创建新容量为minCapacity；如果比MAX_ARRAY_SIZE小，则新容量为MAX_ARRAY_SIZE。扩容核心源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* The maximum size of array to allocate (unless necessary).
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int newCapacity = (value.length << 1) + 2;
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    return (newCapacity <= 0 || MAX_ARRAY_SIZE - newCapacity < 0)
        ? hugeCapacity(minCapacity)
        : newCapacity;
}

private int hugeCapacity(int minCapacity) {
    if (Integer.MAX_VALUE - minCapacity < 0) { // overflow
        throw new OutOfMemoryError();
    }
    return (minCapacity > MAX_ARRAY_SIZE)
        ? minCapacity : MAX_ARRAY_SIZE;
}

3.2 StringBuilder

同3.1

小结

  1. StringBuilder是jdk1.5引进的，而StringBuffer在1.0就有了。
  2. StringBuilder和StringBuffer都是可变的字符串。能够通过append或者insert等方法改动串的内容。
  3. StringBuffer是线程安全的而StringBuilder不是，因而在多线程的环境下优先使用StringBuffer，而其它情况下推荐使用StringBuilder，由于它更快。
  4. StringBuilder和StringBuffer都继承自AbstractStringBuilder类，AbStractStringBuilder主要实现了扩容、append、insert方法。StrngBuilder和StringBuffer的相关方法都直接调用的父类。
  5. StringBuilder和StringBuffer的初始容量都是16，程序猿尽量手动设置初始值。以避免多次扩容所带来的性能问题。
  6. StringBuilder和StringBuffer的扩容机制是相同的。
坚持原创技术分享，您的支持将鼓励我继续创作！

------本文结束 感谢您的阅读------