基于ArrayList常用方法的源码全面解析

我相信几乎所有的同学在大大小小的笔试、面试过程中都会被问及ArrayList与LinkedList之间的异同点。稍有准备的人这些问题早已烂熟于心,前者基于数组实现,后者基于链表实现;前者随机方法速度快删除和插入指定位置速度慢,后者随机访问速度慢删除和插入指定位置速度快;两者都是线程不安全的;列表与数组之间的区别等等。

列表与数组之间很大的一个区别就是:数组在其初始化就需要给它确定大小不能动态扩容,而列表则可以动态扩容。ArrayList是基于数组实现的,那么它是如何实现的动态扩容呢?

对于ArrayList的初始化有三种方式:

对于第一种默认的构造方法,ArrayList并没有初始化容量大小,而是将列表的元素数据引用指向了一个空数组。

private transient Object[] elementData;
private static final Object[] EMPTY_ELEMENTDATA = {};
//1.ArrayList默认构造方法
public ArrayList() {
  super();
  this.elementData = EMPTY_ELEMENTDATA;
}

与JDK1.6不同的是,JDK1.6即时是在调用默认的构造方法时,也会初始化容量大小,JDK1.7当然会带来一定的好处,如果初始化而不使用就白白浪费了存储空间,等到添加的时候再初始化容量大小即可。

与JDK1.6不同的是,JDK1.6即时是在调用默认的构造方法时,也会初始化容量大小,JDK1.7当然会带来一定的好处,如果初始化而不使用就白白浪费了存储空间,等到添加的时候再初始化容量大小即可。

//JDK1.6 ArrayList
public ArrayList() {
  this(10);
}  

对于第二种构造方法,则直接创建一个指定大小的数组,将列表的元素数组引用指向它。

//2.ArrayList带有初始化大小的构造方法
public ArrayList(int initialCapacity) {
  super();
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal Capacity: "+
                      initialCapacity);
  this.elementData = new Object[initialCapacity];
}

第三种构造方法,能将一个集合作为参数传递,但集合中的元素必须继承自ArrayList中的元素。

//3.可将一个集合作为ArrayList的参数构造成ArrayList
public ArrayList(Collection<? extends E> c) {
  elementData = c.toArray();  //将集合转换为数组
  size = elementData.length;  //集合中的元素大小
  // c.toArray might (incorrectly) not return Object[] (see 6260652) 这里是个bug,参考http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652
  if (elementData.getClass() != Object[].class)
    elementData = Arrays.copyOf(elementData, size, Object[].class);
}

上面提到了一个bug,也就是说将一个集合转换为数组的时候可能错误地不会返回Object[],举例说明。

package com.algorithm.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * bug编号:6260652。toArray有可能不会返回Object[]
 * Created by yulinfeng on 2017/6/26.
 */
public class Test {
  public static void main(String[] args) {
    correctly();
    incorrectly();
  }

  /**
   * 返回Object[]
   */
  private static void correctly() {
    List<String> list = new ArrayList<String>();
    list.add("test");
    System.out.println(list.getClass());
    Object[] objArray = list.toArray();
    System.out.println(objArray.getClass());
  }
  /**
   * 不返回Object[]
   */
  private static void incorrectly() {
    List<String> list = Arrays.asList("test");
    System.out.println(list.getClass());
    Object[] objArray = list.toArray();
    System.out.println(objArray.getClass());
  }
}

运行结果:

上面的这个例子就说明了toArray并不一定总是返回Object[],返回的Object[]时,Object元素就不能插入,故JDK在“6260652”中修复了这个bug。

接下来看元素插入以及删除等其它方法。

//ArrayList#add
public boolean add(E e) {
  ensureCapacityInternal(size + 1); //确保容量是否充足
  elementData[size++] = e;  //将元素添加至数组
  return true;
}
//ArrayList#ensureCapacityInternal
private void ensureCapacityInternal(int minCapacity) {
  if (elementData == EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);   //如果此时还没有初始化列表容量大小,则对其初始化,默认容量为10
  }
  ensureExplicitCapacity(minCapacity); //检查容量是否充足
}
//ArrayList#ensureEcplicitCapacity
private void ensureExplicitCapacity(int minCapacity) {
  modCount++;  //注意此变量
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);  //容量不够则进行扩容
}

在ensureEcplicitCapacity方法中有一个modCount(modify count)变量进行了自增。

protected transient int modCount = 0;

这个变量不仅在add方法中会自增,只要是在增加或者删除等对ArrayList结构产生了变化都会记录加1,这样做的原因和多线程下Iterator迭代器遍历有关。在AbstractList$Itr中也有一个变量与之对应。

//AbstractList$Itr
int expectedModCount = modCount;

在AbstractList$Itr#next中调用了checkForComodification方法。

//AbstractList$Itr#checkForComodification
final void checkForComodification() {
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
}

如果当前运行环境是单线程,不论对列表进行何种操作何时增加、修改、删除等,excpectedModCount总是会等于modCount,但是如果当前运行环境是多线程,很有可能一个线程在迭代遍历,而另一个线程在对其进行新增或者修改等,JDK则不允许这么做,此时则会抛出ConcurrentModificationException异常,这就是modCount变量在此起的作用。

回到ArrayList#add方法,当列表容量不足时,此时会调用grow方法进行扩容。

//ArrayList#grow
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + (oldCapacity >> 1);  //扩容策略为,每次新增容量的大小为旧容量的一半。也就是说如果默认容量为10,则第一次扩容大小为10 / 2 = 5,第二次扩容大小为15 / 2 = 7。
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;  //扩容策略扩得太小
  if (newCapacity - MAX_ARRAY_SIZE > 0)  //扩容策略扩得太大,大于最大数组大小时,最多等于Integer.MAX_VALUE
    newCapacity = hugeCapacity(minCapacity);

  elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayList获取指定索引位置的元素get方法。

public E get(int index) {
  rangeCheck(index);  //检查索引是否越界
  return elementData(index);
}

由于ArrayList是由基于数组实现,故此方法较为简单,判断是否越界,没有则根据数组下标来索引返回元素即可。remove方法删除指定位置的元素。 

//ArrayList#remove
public E remove(int index) {
  rangeCheck(index);  //检查索引是否越界
  modCount++;  //记录modCount,上面已提及
  E oldValue = elementData(index);  //取出指定索引元素
  int numMoved = size - index - 1;  //移动的元素个数
  if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index, numMoved);
  elementData[--size] = null; //将最后一个数组元素置为null,方便GC

  return oldValue;
}

代码比较简单,同样也体现了基于数组实习的ArrayList在删除指定元素时的效率问题。

以上这篇基于ArrayList常用方法的源码全面解析就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • JAVA ArrayList详细介绍(示例)

    第1部分 ArrayList介绍ArrayList 是一个数组队列,相当于 动态数组.与Java中的数组相比,它的容量能动态增长.它继承于AbstractList,实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口.ArrayList 继承了AbstractList,实现了List.它是一个数组队列,提供了相关的添加.删除.修改.遍历等功能.ArrayList 实现了RandmoAccess接口,即提供了随机访问功能.Randmo

  • Java中ArrayList类的源码解析

    前言:在前面我们提到数据结构的线性表.那么今天我们详细看下Java源码是如何实现线性表的,这一篇主要讲解顺序表ArrayList链式表下一篇在提及. 1:ArrayList结构图 2:关于Collection和List的区别 最好的比对就是查看他们的源码我们先看Collection的所有接口 public interface Collection<E> extends Iterable<E> { int size(); boolean contains(Object o); Ite

  • Java中ArrayList类的用法与源码完全解析

    System.Collections.ArrayList类是一个特殊的数组.通过添加和删除元素,就可以动态改变数组的长度. 一.优点 1. 支持自动改变大小的功能 2. 可以灵活的插入元素 3. 可以灵活的删除元素 二.局限性 跟一般的数组比起来,速度上差些 三.添加元素 1.publicvirtualintAdd(objectvalue); 将对象添加到ArrayList的结尾处 ArrayList aList = new ArrayList(); aList.Add("a"); a

  • 基于ArrayList常用方法的源码全面解析

    我相信几乎所有的同学在大大小小的笔试.面试过程中都会被问及ArrayList与LinkedList之间的异同点.稍有准备的人这些问题早已烂熟于心,前者基于数组实现,后者基于链表实现:前者随机方法速度快删除和插入指定位置速度慢,后者随机访问速度慢删除和插入指定位置速度快:两者都是线程不安全的:列表与数组之间的区别等等. 列表与数组之间很大的一个区别就是:数组在其初始化就需要给它确定大小不能动态扩容,而列表则可以动态扩容.ArrayList是基于数组实现的,那么它是如何实现的动态扩容呢? 对于Arr

  • Spring启动流程refresh()源码深入解析

    一.Spring容器的refresh() spring  version:4.3.12  ,尚硅谷Spring注解驱动开发-源码部分 //refresh():543, AbstractApplicationContext (org.springframework.context.support) public void refresh() throws BeansException, IllegalStateException { synchronized (this.startupShutdo

  • Java OkHttp框架源码深入解析

    目录 1.OkHttp发起网络请求 可以通过OkHttpClient发起一个网络请求 通过Retrofit发起一个OkHttp请求 2.OkHttp的连接器 1.OkHttp发起网络请求 可以通过OkHttpClient发起一个网络请求 //创建一个Client,相当于打开一个浏览器 OkHttpClient okHttpClient = new OkHttpClient.Builder().build(); //创建一个请求. Request request = new Request.Bui

  • Flink 侧流输出源码示例解析

    目录 Flink 侧流输出源码解析 源码解析 TimestampedCollector#collect CountingOutput#collect BroadcastingOutputCollector#collect RecordWriterOutput#collect ProcessOperator#ContextImpl#output CountingOutput#collect BroadcastingOutputCollector#collect RecordWriterOutput

  • 【MyBatis源码全面解析】MyBatis一二级缓存介绍

    MyBatis缓存 我们知道,频繁的数据库操作是非常耗费性能的(主要是因为对于DB而言,数据是持久化在磁盘中的,因此查询操作需要通过IO,IO操作速度相比内存操作速度慢了好几个量级),尤其是对于一些相同的查询语句,完全可以把查询结果存储起来,下次查询同样的内容的时候直接从内存中获取数据即可,这样在某些场景下可以大大提升查询效率. MyBatis的缓存分为两种: 一级缓存,一级缓存是SqlSession级别的缓存,对于相同的查询,会从缓存中返回结果而不是查询数据库 二级缓存,二级缓存是Mapper

  • 基于ZooKeeper实现队列源码

    实现原理 先进先出队列是最常用的队列,使用Zookeeper实现先进先出队列就是在特定的目录下创建PERSISTENT_EQUENTIAL节点,创建成功时Watcher通知等待的队列,队列删除序列号最小的节点用以消费.此场景下Zookeeper的znode用于消息存储,znode存储的数据就是消息队列中的消息内容,SEQUENTIAL序列号就是消息的编号,按序取出即可.由于创建的节点是持久化的,所以不必担心队列消息的丢失问题. 队列(Queue) 分布式队列是通用的数据结构,为了在 Zookee

  • thinkphp3.2.0 setInc方法 源码全面解析

    我们先来看一下setInc的官方示例: 需要一个字段和一个自增的值(默认为1) 我们通过下面这个例子来一步步分析他的底层是怎么实现的: <?php namespace Home\Controller; use Think\Controller; class TestController extends Controller { public function test() { $tb_test = M('test'); $tb_test->where(['id'=>1])->set

  • LRU算法及Apache LRUMap源码实例解析

    目录 1. 什么是LRU 1.1 自定义实现LRU的要求 1.2 Apache LRUMap示例 1.2.1 pom依赖 1.2.2 demo 2. 源码解析 2.1 设计 2.2 数据结构 2.3 方法解析put get remove 2.3.1 get方法 2.3.2 remove方法 2.3.3 put方法 3. 总结 1. 什么是LRU LRU(least recently used) : 最近最少使用 LRU就是一种经典的算法,在容器中,对元素定义一个最后使用时间,当新的元素写入的时候

  • ahooks useRequest源码精读解析

    目录 前言 架构图 源码解析 Fetch onBefore onRequest onSuccess onFinally onError 其它 API 小结 plugins usePollingPlugin useRetryPlugin 小结 useRequest 对自定义 hook 的思考 总结 前言 自从 React v16.8 推出了 Hooks API,前端框架圈并开启了新的逻辑复用的时代,不再需要在意 HOC 的无限套娃导致性能差的问题,也解决了 mixin 的可阅读性差的问题.当然对于

  • Vue源码cached解析

    目录 前言 参数解释 传入参数 返回参数 源码解释 实验解释 源码疑问 前言 创建一个纯函数的缓存版本 主要用途:优化性能——对于之前运算过一次的内容,利用闭包原理,缓存起来,避免重复调用,造成性能的浪费 /** * Create a cached version of a pure function. */ function cached (fn) { var cache = Object.create(null); return (function cachedFn (str) { var

随机推荐