Java源码阅读之ArrayList - JDK1.8
阅读优秀的源码是提升编程技巧的重要手段之一。 如有不对的地方，欢迎指正~ 转载请注明出处https://blog.lzoro.com。 前言 当你对某件事情很感兴趣的时候，时间的流逝在感知中都模糊了（是不是很文艺，绕口得都快听不懂了），通俗来说，就是时间过得很快。 而且，只有感兴趣才能驱动你继续下去，不然读源码，写解析博客这么高(Ku)大(Zao)上的事，是很难坚持的。 详细地写一篇源码解析博客少则半天一天，比如本篇，多则几天，比如红黑树在Java - HashMap中的应用，又要画图又要注释，还要排版，时不时要加点表情，开个车什么的，你说要是没兴趣，怎么坚持呢，还不如吃个鸡实在(啊，暴露了我是吃鸡选手)。 image 闲话少说，打开你的IDE，挽起袖子，开撸代码，加上注释，总计1461行代码。 基本介绍 常量 相比HashMap来说，ArrayList的常量算是短小精悍了，只有几个。 其中包含一个默认容量和两个空数组等，如下。 /** * 默认初始化容量 */ private static final int DEFAULT_CAPACITY = 10; /** * 空数组共享实例 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 缺省大小的空数组共享实例 * 与 EMPTY_ELEMENTDATA 区分开来，以便知道第一个元素添加时如何扩容 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 最大可分配大小 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 成员变量 成员变量也是简单到令人发指，一个负责实际存储的缓冲数组和一个表示大小的变量。 /** * 实际负责存储的缓冲数组 * ArrayList的容量就是缓冲数组的长度 * * 空的ArrayList(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)在第一个元素添加时将会以默认容量扩容 */ transient Object[] elementData; // 非私有，以简化嵌套类的访问 /** * 大小 */ private int size; 构造函数 三个构造函数，分别是利用默认初始容量/给定初始容量/给定特定集合来构造ArrayList。 /** * 根据给定初始容量构造一个空的list * * @param initialCapacity list的初始容量 * @throws IllegalArgumentException 当给定的初始容量非负时抛异常 */ 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); } } /** * 按默认初始容量(10)构造一个空的list */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 根据给定集合构造一个list，将按集合迭代的顺序存储 * * @param c 集合 * @throws NullPointerException 集合为null时抛异常 */ public ArrayList(Collection<? extends E> c) { //集合转数组后赋值给缓冲数组 elementData = c.toArray(); //判断大小 if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) //c.toArray方法可能不会返回Object[]形式的数组 //下面做一层判断 if (elementData.getClass() != Object[].class) //做拷贝操作 elementData = Arrays.copyOf(elementData, size, Object[].class); } else { //如果是空集合，则替换成共享空数组实例 // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } } 功能 看完了基本介绍，应该会觉得Just so so。 接下来就要逐一介绍各个功能的具体实现了。 ArrayList中，我们常用的功能有add/remove/get等。 无外乎增删改查，下面一一介绍~ add 在ArrayList中，添加操作还分为几种 从尾部添加元素 指定位置添加元素 从尾部添加集合 从指定位置添加集合 /** * 从尾部添加指定元素 * * @param e 元素 * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { //确保内部容量，有一系统调用链但不复杂，下面分析 ensureCapacityInternal(size + 1); // Increments modCount!! //存储元素 elementData[size++] = e; return true; } /** * 在指定位置插入元素 * 移动当前位置的元素 (如果存在) 和后继元素到右边 * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ public void add(int index, E element) { //判断边界，可能会产生数组越界 rangeCheckForAdd(index); //确保内部容量，同上 ensureCapacityInternal(size + 1); // Increments modCount!! //调用效率较高的System.arraycopy进行数组复制 //目的是为了空出指定位置 System.arraycopy(elementData, index, elementData, index + 1, size - index); //指定位置上放入指定元素 elementData[index] = element; //容量+1 size++; } 在添加的元素的时候，有一个关键方法ensureCapacityInternal是来确保内部缓存数组的容量，当容量不够时进行扩容，下面具体看下这个方法的调用链 /** * 私有方法 */ private void ensureCapacityInternal(int minCapacity) { //判断是否是默认空实例，如果是的话，计算扩容容量 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } //调用ensureExplicitCapacity ensureExplicitCapacity(minCapacity); } ... private void ensureExplicitCapacity(int minCapacity) { //操作计算+1 modCount++; // overflow-conscious code //只有当容量不够时才扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * 缓冲数组扩容以确保能够存储给定元素 * * @param minCapacity 期望的最小容量 */ private void grow(int minCapacity) { // overflow-conscious code //现有元素长度 int oldCapacity = elementData.length; //新容量为 旧容量 + 旧容量的一半 //如 10 + 5 = 15 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: //最小扩容容量通常是接近size的，所以这是一场胜利 //这么臭美的吗 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; } set 这里的set其实可以理解为修改，将指定位置的元素替换为新元素。 /** * 修改指定位置的元素 * * @param index index of the element to replace * @param element element to be stored at the specified position * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */ public E set(int index, E element) { //范围检查 rangeCheck(index); //取出旧值用以返回 E oldValue = elementData(index); //放入新的值 elementData[index] = element; return oldValue; } remove 数组的移除和添加一样，也分为几种方式 根据下标移除 根据对象移除 根据集合移除 根据过滤器移除 根据范围移除(受保护的方法) /** * 删除指定位置的元素，后继元素左移(前移) * * @param index 下标 * @return the 被移除的元素 * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { //下标检查 rangeCheck(index); //操作计数 + 1 modCount++; //获取指定位置的元素(用以返回) E oldValue = elementData(index); int numMoved = size - index - 1; //用system.arraycopy的方式移动元素 //相当于是index位置后的元素前移 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); //最后一个数组元素引用置为null，方便GC elementData[--size] = null; // clear to let GC do its work //返回 return oldValue; } /** * 当元素存在的时候，删除第一个找到的指定元素 * * 如果元素不存在，则list不会变动 * * @param o element to be removed from this list, if present * @return <tt>true</tt> if this list contained the specified element */ public boolean remove(Object o) { //o是否是null元素(数组允许存储null) if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { //调用内部的fastRemove方法，后面分析 fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) //这里跟上面不一样的是，是用equals来比较，而不是比较地址 if (o.equals(elementData[index])) { //同上 fastRemove(index); return true; } } return false; } /** * 根据给定的集合，将list中与集合相同的元素全部删除 * * @param c collection containing elements to be removed from this list * @return {@code true} if this list changed as a result of the call * @throws ClassCastException if the class of an element of this list * is incompatible with the specified collection * (<a href="Collection.html#optional-restrictions">optional</a>) * @throws NullPointerException if this list contains a null element and the * specified collection does not permit null elements * (<a href="Collection.html#optional-restrictions">optional</a>), * or if the specified collection is null * @see Collection#contains(Object) */ public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); //调用批量删除，后续分析 return batchRemove(c, false); } /** * 通过一个过滤器接口实现，来实现删除 */ @Override public boolean removeIf(Predicate<? super E> filter) { Objects.requireNonNull(filter); // figure out which elements are to be removed // any exception thrown from the filter predicate at this stage // will leave the collection unmodified int removeCount = 0; //用bitset来存储哪些下标对应的元素要删除，哪些下标对应的元素要保存 //这里不清楚BitSet的用法的，可以先行了解一下 final BitSet removeSet = new BitSet(size); //判断并发修改用 final int expectedModCount = modCount; final int size = this.size; //按顺序遍历且没有并发修改 for (int i=0; modCount == expectedModCount && i < size; i++) { @SuppressWarnings("unchecked") final E element = (E) elementData[i]; //利用过滤器匹配元素，如果匹配，则删除计数+1，并将下标进行存储 if (filter.test(element)) { removeSet.set(i); removeCount++; } } //判断是否存在并发修改 if (modCount != expectedModCount) { //抛出并发修改异常 throw new ConcurrentModificationException(); } // shift surviving elements left over the spaces left by removed elements //判断是否有要删除的元素 final boolean anyToRemove = removeCount > 0; if (anyToRemove) { final int newSize = size - removeCount; for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { //下一个要保存的元素 i = removeSet.nextClearBit(i); //存放到新数组 elementData[j] = elementData[i]; } //把实际要保存的元素之后的全部置为null，用以GC //实际上，上面的操作已经将要保留的元素全部前移了，后面的元素都是不保留的，所以要置为null来帮助gc for (int k=newSize; k < size; k++) { elementData[k] = null; // Let gc do its work } //设置size this.size = newSize; //判断是否并发修改 if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; } return anyToRemove; } /** * 删除list中指定范围的元素 * * Shifts any succeeding elements to the left (reduces their index). * This call shortens the list by {@code (toIndex - fromIndex)} elements. * (If {@code toIndex==fromIndex}, this operation has no effect.) * * @throws IndexOutOfBoundsException if {@code fromIndex} or * {@code toIndex} is out of range * ({@code fromIndex < 0 || * fromIndex >= size() || * toIndex > size() || * toIndex < fromIndex}) */ protected void removeRange(int fromIndex, int toIndex) { modCount++; //范围删除时，其实数组被分成三个部分 //分别为[保留区 - 删除区 - 保留区] //实际操作，则是计算出最后那部分保留区的长度 //利用arraycopy拷贝到第一个保留区的后面 //然后置空多余部分，帮助GC int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // clear to let GC do its work int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; } //最后，来看一下批量删除这个私有方法 /** * 批量删除 */ 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++) //这里其实有可能抛异常的 //complement //为false时，则证明下标r的元素不在删除集合c中，所以这个时候存储的是不删除的元素 //为true时，则证明下标r的元素在删除集合c中，所以这个时候存储的是要删除的元素 //这个布尔值的设计很巧妙。所以本方法可以供removeAll、retainAll两个方法来调用 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; } //如果有需要删除的元素的话，则证明有一部分位置需要只为null，来帮助GC //并且设置是否有修改的标志为true 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; } 至此，删除相关的方法都已经分析完毕。 有几个比较有意思的应用 BitSet 标志哪些下标要删除，哪些不删除 batchRemove 方法中的布尔值很巧妙 get 作为数组型的list，获取方法时比较简单的，只需要根据给定下标，读取指定下标的数组元素即可。 public E get(int index) { //范围检查 rangeCheck(index); return elementData(index); } contains 当前list是否包含指定元素 /** * 返回布尔值表示是否包含 */ public boolean contains(Object o) { //实际上是判断下标是否存在 return indexOf(o) >= 0; } /** * 指定元素在list中首次出现的下标，不存在则返回-1 */ public int indexOf(Object o) { //通过遍历的方式查找 if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; } //另外，还有一个，最后一次出现的下标 public int lastIndexOf(Object o) { //跟上面的类似，只不过遍历方式是从尾部开始 if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; } clear 清空缓冲数组。 public void clear() { //修改计数 + 1 modCount++; // clear to let GC do its work //全部置为null，帮助GC for (int i = 0; i < size; i++) elementData[i] = null; //size设置为0 size = 0; } 以上相关方法基本都已经介绍完毕。 总结 Array相比其他集合框架，如Map、Set之类的，还是比较简单的。 只需要了解相关方法的应用和原理，注意下标越界问题，以及内部的缓冲数组是如何扩容的，基本上就OK了。 溜了溜了。有帮助的话给格子点个赞呗~3Q 我的博客即将入驻“云栖社区”，诚邀技术同仁一同入驻。
