java ArrayList和HashMap 扩容

2016-09-12 本文已影响260人 else05

网上搜索"ArrayList扩容机制"可以找到很多内容，但是多看几遍博文后会发现有些文章描述的知识点不同步。这里可能的原因是JDK版本不同，JDK6和JDK7+的内容有所不同。

ArrayList
JDK6

// JDK6的扩容机制
public void ensureCapacity(int minCapacity) {  
    modCount++;  
    int oldCapacity = elementData.length;  
    if (minCapacity > oldCapacity) {  
        Object oldData[] = elementData;  
        int newCapacity = (oldCapacity * 3)/2 + 1;  
            if (newCapacity < minCapacity)  
                newCapacity = minCapacity;  
      // minCapacity is usually close to size, so this is a win:  
      elementData = Arrays.copyOf(elementData, newCapacity);  
    }  
}

// 默认容量大小是10
public ArrayList() {  
    this(10);  
}

JDK7+

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
//  用位运算，相当于扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

/** JDK7+ 默认的容量表面上是0，其实还是10 
 *，只是使用懒加载，当使用add方法添加一个元素时，容量会被扩成10  ，
 *这算是一个优化，如果实例化后没有添加元素，容量是0，节约空间，否则为10
 */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 当添加元素时，这里有懒加载设置容量 ，
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

HashMap
JDK7：

暂没安装jdk7的环境，引用别人的结论：
- 容量默认16，负载因子默认0.75
- 当初次扩充为：数量大于容量时扩充；第二次及以后为：当数量大于容量 * 负载因子时扩充。

JDK8：（以后补充，有部分是位运算，自己还没完全明白JDK8中的具体情况）

总结：

扩容其实就是数组的复制，把旧数组复制到一个新的数组中，所有尽可能减少数组的扩容对性能的优化是有必要的。
在知道数组容量的情况下应该在实例化时指定容量。

参考：

java ArrayList和HashMap 扩容

猜你喜欢

热点阅读