【不失业计划】 Java常见集合扩容机制

Java集合扩容机制

- - - 1、ArrayList
    - 2、Vector
    - 3、Stack
    - 4、HashMap

为什么需要扩容？即当前集合能容纳的数据量达到一个饱和状态(饱和状态和加载因子有关)之后，集合需要申请新的存储空间，即扩容。

常见的需要扩容的集合一般是底层基于数组实现的，链表不涉及扩容问题，因此LinkedList等无扩容，常见的有ArrayList、Vector、Stack、HashMap。

加载因子：集合中元素填满的程度，例如ArrayList加载因子为1，初始容量为10，则当当前元素>=10*1需要进行扩容；HashMap加载因子为0.75，初始容量为16，当当前元素>=16 * 0.75=12时进行扩容。

1、ArrayList

查看ArrayList源码可以看到，在ArrayList初始化时，内部表示为一个object类型的数组，默认初始容量为10，加载因子为1；

private static final int DEFAULT_CAPACITY = 10;	//默认大小为10
private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
transient Object[] elementData;	//ArrayList 在内部的表示即为一个Object类型的数组

初始化ArrayList时，会涉及到两个构造器：

无参构造器：构造一个初始容量为 10 的空列表。

public ArrayList() {
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

有参构造器：构造一个具有指定初始容量的空列表。

//当传入的值大于0时，数组的大小即为传入的值大小，为0时，则为EMPTY_ELEMENTDATA(即0)，小于0则抛出异常。
//initialCapacity不是ArrayList的size()，initialCapacity表示初始容量，size则是实际存放对象的数量。
public ArrayList(int initialCapacity) 
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else {
        if (initialCapacity != 0) {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

此外在源码中还有另一个构造器，该构造器一般用于构造一个包含指定 collection 的元素的列表，元素按照该 collection 的迭代器返回它们的顺序排列。

public ArrayList(Collection<? extends E> c) {
    this.elementData = c.toArray();
    if ((this.size = this.elementData.length) != 0) {
        if (this.elementData.getClass() != Object[].class) {
            this.elementData = Arrays.copyOf(this.elementData, this.size, Object[].class);
        }
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

扩容时，先进行当前容量长度和元素数量比较，需要扩容即调用grow()方法进行扩容。

public void ensureCapacity(int minCapacity) {
    if (minCapacity > this.elementData.length && (this.elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA || minCapacity > 10)) {		//判断当前的长度大于了elementData长度，即需要进行扩容。
        ++this.modCount;
        this.grow(minCapacity);	//调用grow方法进行扩容，传入参数为当前需要长度
    }
}

private Object[] grow(int minCapacity) {
    return this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity));//调用newCapacity()， 将当前数组中的内容传给新的数组
}
private Object[] grow() {
    return this.grow(this.size + 1);
}

//扩容核心方法
private int newCapacity(int minCapacity) {
    int oldCapacity = this.elementData.length;
    //对当前数组长度进行扩容：扩容后长度 = 当前长度 + 当前长度二进制进位1(即当前长的1/2)；
    //因此初始化默认长度为10时，后面的每一次扩容后容量为 10、15、22、33、49...
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    if (newCapacity - minCapacity <= 0) {
        if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(10, minCapacity);
        } else if (minCapacity < 0) {
            throw new OutOfMemoryError();
        } else {
            return minCapacity;
        }
    } else {
        return newCapacity - 2147483639 <= 0 ? newCapacity : hugeCapacity(minCapacity);
    }
}

2、Vector

Vector与ArrayList一样，是存储在数组结构中，加载因子为1，初始容量为10。

public Vector(int initialCapacity, int capacityIncrement) {
    if (initialCapacity < 0) {
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    } else {
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
}
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

//初始容量10
public Vector() {
    this(10);
}

扩容时，有两种不同的方式

//判断进行扩容
public synchronized void ensureCapacity(int minCapacity) {
    if (minCapacity > 0) {
        ++this.modCount;
        if (minCapacity > this.elementData.length) {
            this.grow(minCapacity);	
        }
    }
}

private Object[] grow(int minCapacity) {
    return this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity));//将当前的数组复制给扩容后数组
}

private Object[] grow() {
    return this.grow(this.elementCount + 1);
}

扩容时会先对capacityIncrement参数进行判断

private int newCapacity(int minCapacity) {
    int oldCapacity = this.elementData.length;
    //判断capacityIncrement是否大于0：大于0则扩容为当前长度加capacityIncrement的大小，否则扩容为当前长度的2倍
    int newCapacity = oldCapacity + (this.capacityIncrement > 0 ? this.capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity <= 0) {
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        } else {
            return minCapacity;
        }
    } else {
        return newCapacity - 2147483639 <= 0 ? newCapacity : hugeCapacity(minCapacity);
    }
}
//例如 Vector<String> v = new Vector<String>(); 扩容大小则为10、20、40、80....
//例如 Vector<String> v = new Vector<String>(8,4); 扩容大小则为8、12、16、20、24....

3、Stack

stack继承自Vector，所以Stack的扩容机制等同于Vector的默认情况，也就是2倍速度扩容，加载因子也为1。

public class Stack<E> extends Vector<E> {
    private static final long serialVersionUID = 1224463164541339165L;

    public Stack() {
    }
    //......
    
}

4、HashMap

HashMap的底层实现根据jdk版本的不同有两种不同的实现方式，但是共同点是都有数组+链表的形式，HashMap默认初始容量为16，加载因子为0.75.

static final int DEFAULT_INITIAL_CAPACITY = 16;	//初始容量
static final float DEFAULT_LOAD_FACTOR = 0.75F; //加载因子

哈希表的扩容方法主要在put新值的时候进行判断并执行，因此在他的put方法中，由于本地JDK版本为1.8，在1.8中扩容中，初始化后首次插入，先扩容再插入，后面容量达到容量*加载因子时，先插入，再扩容；但是在1.7之前，扩容方式是先判断进行扩容，再插入数据。

public V put(K key, V value) {
    return this.putVal(hash(key), key, value, false, true);//运用到putVal方法
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    HashMap.Node[] tab;
    int n;
    if ((tab = this.table) == null || (n = tab.length) == 0) {
        n = (tab = this.resize()).length;
    }

    Object p;
    int i;
    //插入数据
    if ((p = tab[i = n - 1 & hash]) == null) {
        tab[i] = this.newNode(hash, key, value, (HashMap.Node)null);
    } else {
       //.....
    }
	//判断扩容
    ++this.modCount;
    if (++this.size > this.threshold) {
        //size空间不足时，进行resize扩容
        this.resize();
    }

    this.afterNodeInsertion(evict);
    return null;
}

扩容核心在于resize()方法

//resize()是进行扩容的核心函数
final HashMap.Node<K, V>[] resize() {
    HashMap.Node<K, V>[] oldTab = this.table;
    int oldCap = oldTab == null ? 0 : oldTab.length;
    int oldThr = this.threshold;
    int newThr = 0;
    int newCap;
    if (oldCap > 0) {
        if (oldCap >= 1073741824) {
            this.threshold = 2147483647;
            return oldTab;
        }
		//扩容大小为原来的两倍，二进制左移一位，原容量的2倍
        if ((newCap = oldCap << 1) < 1073741824 && oldCap >= 16) {
            newThr = oldThr << 1;
        }
    } else if (oldThr > 0) {
        newCap = oldThr;
    } else {
        newCap = 16;
        newThr = 12;
    }
	//扩容时机
    if (newThr == 0) {
        float ft = (float)newCap * this.loadFactor;
        newThr = newCap < 1073741824 && ft < 1.07374182E9F ? (int)ft : 2147483647;
    }

    this.threshold = newThr;
    HashMap.Node<K, V>[] newTab = new HashMap.Node[newCap];
    this.table = newTab;
    if (oldTab != null) {
        //这部分代码目前还没搞懂，个人觉得是扩容后两个容器之间数据的拷贝，1.8这部分涉及到红黑树，目前红黑树还是懵逼状态
    }
    return newTab;
}

【不失业计划】 Java常见集合扩容机制

Java集合扩容机制

1、ArrayList

2、Vector

3、Stack

4、HashMap

继续阅读

关于Gradle配置的小结

Java小案例——随机数猜测随机数猜测

nginx location中斜线的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method