您现在的位置是:首页 > 文章详情

Java源码阅读之ArrayList - JDK1.8

日期:2018-09-02点击:427

阅读优秀的源码是提升编程技巧的重要手段之一。
如有不对的地方,欢迎指正~
转载请注明出处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

我的博客即将入驻“云栖社区”,诚邀技术同仁一同入驻。

原文链接:https://yq.aliyun.com/articles/635251
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章