java集合(ArrayList、vector、HashMap、HashTable)源码剖析

时间：2022-09-25 17:52:39

记得很久之前有个朋友说他去面试时面试官问他，ArrayList、vector、HashMap、HashTable初始化不指定容量大小时，默认大小是多少，这四者的两两区别，于是后来便找出了jdk源码，看了看，当时告诉结果给朋友后由于忙一直没有写下来，现在趁着有时间写下来记录记录。

首先先说ArrayList。ArrayList这个对象我一共看几个版本JDK，看到两类，第一类就是在初始化时直接指定默认容量，代码如下：

private transient Object[] elementData;
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}
public ArrayList() {
    this(10);
}

从代码中可以看出，ArrayList底层其实就是一个Object数组，类包含两个构造器，默认不指定初始容量时会通过this(10)来调用有参构造，初始化一个容量为10的数组。说到这个，肯定就会涉及到超过10个时会怎样处理呢？看如下代码： 

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;//获取当前数组长度
        int newCapacity = oldCapacity + (oldCapacity >> 1);//新长度为原长度1.5倍
        if (newCapacity - minCapacity < 0)//新长度还是小于所需长度，则数组长度扩展为所需长度
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)//新长度大于数组最大容量(最大容量Integer.MAX_VALUE - 8，源代码中有体现)时调用下面一个方法，直接取最大值
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);//扩容
    }
private static int hugeCapacity(int minCapacity) {        if (minCapacity < 0) // overflow            throw new OutOfMemoryError();        return (minCapacity > MAX_ARRAY_SIZE) ?            Integer.MAX_VALUE :            MAX_ARRAY_SIZE;    }

这段代码是在数组容量不足时会触发，参数minCapacity即当前所需容量，我写的注释已经很详细了，其中涉及到>>右移位运算符，右移原理不多讲，右移一位相当于原数值除以2并省掉余数，加上原来的，故为1.5倍。

另看到过一版JDK中ArrayList的无参构造器中直接给数组赋了一个空数组，即初始化时容量为0，当第一次调用add()方法时，会触发grow方法，因暂时没有那版JDK，只能靠记忆简述，后续再补上，那个版本定义了一个常量，值为10，在扩容时会有一个分支，如果初始为空数组，则会扩容成常量值长度(即为10)的容量，以此来达到一种懒汉模式的效果。

然后是Vector，vector底层原理其实跟ArrayList一样，只是很多方法中加入了锁，故Vector是线程安全的，当然，效率会低于ArrayList，初始化代码如下：

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

这里可以看到，Vector比ArrayList多了一个两个参数的构造器，但是初始化长度依旧为10，那么那个两个参数的构造器中后一个参数 capacityIncrement是什么呢？看如下代码： 

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                 capacityIncrement : oldCapacity);//此处用到<span style="background-color: rgb(240, 240, 240);">capacityIncrement</span>
if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
    throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
    Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}
代码中注释的部分可以看出，如果初始化 capacityIncrement>0，则Vector扩容时增量为capacityIncrement，即我们构造器的第二个参数，如果不指定，默认为0，则增量为原大小。
接下来就是HashMap，由于本文重点讨论初始化大小，则只关注初始化，其他细节会另写文章做说明，初始化代码如下： 

static final int DEFAULT_INITIAL_CAPACITY = 16;
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    table = new Entry[DEFAULT_INITIAL_CAPACITY];
    init();
}

代码中可以看到，定义了一个常量为16，无参构造是会通过table = new Entry[DEFAULT_INITIAL_CAPACITY];来初始化一个长度为16的元素为链表结构的数组。

最后是HashTable，HashTable也是加入了很多锁，故也是线程安全的，同样会降低效率，代码如下：

public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: "+loadFactor);

    if (initialCapacity==0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new Entry[initialCapacity];
    threshold = (int)(initialCapacity * loadFactor);
}
public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}
public Hashtable() {
    this(11, 0.75f);
}

通过代码可以看到，同样有三个构造器，无参默认初始化长度为11。

今天的内容到此为止，另一版的ArrayList我会找时间补上，大家有什么异议可以提出，互勉才能进步嘛。

标签：

相关文章