了不起的厂长 2019-06-27
毕业两个星期了,开始成为一名正式的java码农了。
一直对偏底层比较感兴趣,想着深入自己的java技能,看书、读源码、总结、造轮子实践都是付诸行动的方法。
说到看源码,就应该由简入难,逐渐加深,那就从jdk的源码开始看起吧。
ArrayList和Vector是java标准库提供的一种比较简单的数据结构,也是最常用的一种。
<!-- more -->
表这种抽象概念指的是一种存放数据的容器,其中数据A1, A2, A3, ..., Ai, ... AN有序排列。
那么在表这一抽象的数据结构模型中:
它的操作有:
表有两种实现方式,数组实现和链表实现。这两种实现方式各有优劣,其中这里所说的ArrayList是数组实现方式。
线性表的实现中是将元素放到数组中的。如果是C的数组,那其实是一块连续的内存。
在java中也是java的原生数组,内存布局中逻辑上是连续的,物理上不一定。印象中有的jvm实现为了解决内存碎片搞类似逻辑内存的这种操作。
往线性表取出数据或拿出元素都能很直接对应到原生数组中去。
但是,线性表插入数据的这一操作要求表是能够动态增长的,但是原生数组的大小是固定的。
线性表实现的一大重点是实现表动态增长这一要求,将其转换、化归到固定大小的原生数据上去。思路是,当线性表内部保存数据的数组如果不够用了,就申请一个更大的数组,将原来数组的数据拷贝进去。
如上图所示,在设计上,它的结构应该理解成 ArrayList
--> List
--> Collection
--> Iterable
:
List
接口表示抽象的表,也就是上面所说的表。Collection
接口表示抽象的容器,能放元素的都算。Iterable
接口表示可迭代的对象。也即该容器内的元素都能够通过迭代器迭代。但是在继承结构上,ArrayList
继承了AbstractList
。这是java中通用的一种技巧,由于java8之前的接口无法指定默认方法,如果你要实现List
接口,你需要实现其中的所有方法。
但是,List
接口中的所有方法是大而全的,有大量方法是为了方便调用者使用而设计的衍生方法,并非实现该接口的必须方法。比如说,isEmpty
方法就可以化归到size
方法上。
所以,java对于List接口会提供一个AbstractList
抽象类,里面提供了部分方法的默认实现,而继承该类的只需要实现一组最小的必须方法即可。
总而言之一句话,AbstractList
的作用是给List
接口提供某些方法的默认实现。
先看ArrayList内部保存的属性和状态。
private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; // non-private to simplify nested class access private int size;
其中,最关键的为elementData
和size
。 elementData
也即真正存储元素的java原生数组。
由于ArrayList中实际保存的元素个数是少于elementData
数组的大小的,也即会有部分空间的浪费,因此size
属性是用来保存ArrayList
存储的元素个数。
值得注意的是,elementData
没有访问修饰符,我们知道默认是对包内可见的。这样做的目的是:
构造函数一共有三个,下面是其中两个。第三个是从其它容器初始化,没什么好看的地方。
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } /** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
第一个带参数的构造函数,行为上这个都知道,创建出来的依然是个空表,看代码也可发现执行完后size
属性为0。initialCapacity
的含义是指定内部存储数据的原生数组的初始化大小。
代码逻辑很简单,initialCapacity
大于0时对elementData
分配该大小的原生数组。但是问题是,initialCapacity
为0时,并不是直接new一个大小为0的数组,而是使用静态变量EMPTY_ELEMENTDATA
来代替。
为什么?EMPTY_ELEMENTDATA
是静态变量,所有实例共享,个人猜测应该是为了省点内存吧。可是这个占不了多大的内存啊,这个理由可能说服力不太强。
第二个默认构造函数,这个函数行为上也是创建空表。但是会预先将存储数据的原生数组的大小设置为DEFAULT_CAPACITY
,也就是默认值10。这样,能避免在大小较小时频繁扩容带来性能损耗。
按照这个思路,代码应该长这样才对:
public ArrayList() { this.elementData = new Object[DEFAULT_CAPACITY]; }
但是实际上,我们发现DEFAULTCAPACITY_EMPTY_ELEMENTDATA
其实是个空表,也是静态变量,多实例共享的。
这实际上也可以认为是一种优化手段,因为很多场景都是直接默认构造的一个空表在哪里放着,为了节约内存,jdk实现先不实际分配空间,仅仅做一个类似标记作用的操作,之后真正使用了才会分配空间,达到一个类似“延迟分配”的效果。这些思路在扩容相关的代码中有所体现。
get和set没什么好说的,实际上是直接操作内部的原生数组。
不过,从下面的代码中可以看到,在get和set之前,会做越界检查。
private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } public E get(int index) { rangeCheck(index); return elementData(index); } E elementData(int index) { return (E) elementData[index]; } public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }
下面再来看插入元素。插入有两种:
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
思路都特别显然,主要是在操作之前,调用了ensureCapacityInternal
函数,这个函数调用完毕后会保证内部数组的空间能存储下这么多元素。
此外,void add(int, E)
函数还做了越界检查。
接下来看ensureCapacityInternal
函数,相关实现涉及到四个函数。
这个函数的目的是保证执行完后,内部的原生数组至少能容纳minCapacity
个元素。
之前所说的那种“延迟分配”操作在这里就体现出来了。分析代码流程不难发现,当elementData
为DEFAULTCAPACITY_EMPTY_ELEMENTDATA
,也即前面所说到的那个标记,那么之后扩容后的原生数组空间一定不小于DEFAULT_CAPACITY
,也就是前面定义处的10。
private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } 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); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
再看具体的扩容逻辑,也即grow
函数。逻辑还不单一。首先扩容尝试按照原来大小的1.5倍扩容,为了性能,这里除以2优化成了右移运算。
如果1.5倍不够怎么办?如果是我,我可能会优雅的递归再扩大,然而,jdk的做法是如果1.5倍不够的话直接按照需要的大小扩容。
最后,如果实在太大,也要做一下限制,最大可达到的大小为Integer.MAX_VALUE
,否则就超过了int的范围,溢出了。
下面是移除相关的函数,有两个:
E remove(int)
是通过索引移除。boolean remove(Object)
是通过元素移除。public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work }
按索引移除的的思路很简单,首先把需要移除的元素拿出来,然后后面的都往前挪一个,通过数据拷贝实现。
但是,有个 特别需要注意的地方是,假设删除之后的表大小为N,往前挪一个后,elementData[N - 1]
和elementData[N]
都指向了最后一个元素。这时elementData[N]
仍然持有对该元素的引用。如果之后试图移除表中最后一个元素,它可能不会及时的被gc干掉,造成无意义的额外内存占用。
按元素移除的思路也很显然,先是找到该元素的索引,然后按索引移除。fastRemove
的代码几乎和remove(int)
一模一样,不知道为什么复用一下。。。
最后,从代码可以看到一点,表内元素会被移除,但是jdk对ArrayList的实现只会扩容表,而不会缩小表以减小内存占用。不过,它提供了一个trimToSize
方法,将表中原生数组的空闲空间去掉:
public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }
很明显,它重新分配一个正好合适的原生数组,然后拷贝过去。
这两个函数很好理解:
这两个函数算法几乎一模一样,因此抽象出一个函数batchRemove
来实现。
public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); } public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); } private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; }
核心在于try中的那三行代码。这个算法简化了就是这样:
有两个数组data和isRemove,isRemove[i]为true表示data[i]应该被移除。
要求在O(n)时间复杂度,O(1)空间复杂度,将data中isRemove[i]为true的元素移除。
算法这种东西,思路我能在脑子里想象出来画面,但是说不清楚。。。 大学里学习算法时候都写过,就不多说了。
感觉写的有点多。。。以上是和ArrayList
操作密切相关的,其它的简单总结下吧。
SubList
中。Itr
。基本都是一些包装代码。Arrays.sort
实现的,所以,具体的排序算法要看Arrays.sort
。还有一个没有看懂的问题,即在AbstractList中有一个modCount
字段,ArrayList
的实现中多次操作该字段。但是仍然没有理解该字段的作用。
Vector提供的容器模型和ArrayList几乎一模一样,只不过它是线程安全的。
它的代码思路上和ArrayList差不多,但是有一些实现细节上的小区别。
首先,它有一个参数capacityIncrement
,能够控制扩容的细节,看构造函数:
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); }
如果不指定的话,这个initialCapacity
默认值为0。在内部使用属性capacityIncrement
保存。
其次,再看控制扩容的核心函数grow
,研究下扩容逻辑是不是有什么差异:
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
可以发现,capacityIncrement
控制的是扩容的步长。
如果没有指定步长,那么则是按照两倍扩容,这是与ArrayList
不同的地方。
总体上,它相当于synchronized同步过的ArrayList,也即它对线程安全的实现非常暴力,并未用到太多的技巧。很显然,在并发环境下,对vector的操作直接锁住整个vector,相当于操作vector的线程是串行操作vector,性能不高。