为了账号安全,请及时绑定邮箱和手机立即绑定
慕课专栏

目录

已到底部

面试官系统精讲Java源码及大厂真题

原价 ¥ 68.00

立即订阅
05 ArrayList 源码解析和设计思路
更新时间:2020-06-03 16:03:19
耐心和恒心总会得到报酬的。——爱因斯坦

引导语

ArrayList 我们几乎每天都会使用到,但真正面试的时候,发现还是有不少人对源码细节说不清楚,给面试官留下比较差的印象,本小节就和大家一起看看面试中和 ArrayList 相关的源码。

1 整体架构

ArrayList 整体架构比较简单,就是一个数组结构,比较简单,如下图:
图片描述图中展示是长度为 10 的数组,从 1 开始计数,index 表示数组的下标,从 0 开始计数,elementData 表示数组本身,源码中除了这两个概念,还有以下三个基本概念:

  • DEFAULT_CAPACITY 表示数组的初始大小,默认是 10,这个数字要记住;
  • size 表示当前数组的大小,类型 int,没有使用 volatile 修饰,非线程安全的;
  • modCount 统计当前数组被修改的版本次数,数组结构有变动,就会 +1。

类注释

看源码,首先要看类注释,我们看看类注释上面都说了什么,如下:

  • 允许 put null 值,会自动扩容;
  • size、isEmpty、get、set、add 等方法时间复杂度都是 O (1);
  • 是非线程安全的,多线程情况下,推荐使用线程安全类:Collections#synchronizedList;
  • 增强 for 循环,或者使用迭代器迭代过程中,如果数组大小被改变,会快速失败,抛出异常。

除了上述注释中提到的 4 点,初始化、扩容的本质、迭代器等问题也经常被问,接下来我们从源码出发,一一解析。

2 源码解析

2.1 初始化

我们有三种初始化办法:无参数直接初始化、指定大小初始化、指定初始数据初始化,源码如下:

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//无参数直接初始化,数组大小为空
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//指定初始数据初始化
public ArrayList(Collection<? extends E> c) {
    //elementData 是保存数组的容器,默认为 null
    elementData = c.toArray();
    //如果给定的集合(c)数据有值
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        //如果集合元素类型不是 Object 类型,我们会转成 Object
        if (elementData.getClass() != Object[].class) {
            elementData = Arrays.copyOf(elementData, size, Object[].class);
        }
    } else {
        // 给定集合(c)无值,则默认空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

除了源码的中文注释,我们补充两点:

1:ArrayList 无参构造器初始化时,默认大小是空数组,并不是大家常说的 10,10 是在第一次 add 的时候扩容的数组值。

2:指定初始数据初始化时,我们发现一个这样子的注释 see 6260652,这是 Java 的一个 bug,意思是当给定集合内的元素不是 Object 类型时,我们会转化成 Object 的类型。一般情况下都不会触发此 bug,只有在下列场景下才会触发:ArrayList 初始化之后(ArrayList 元素非 Object 类型),再次调用 toArray 方法,得到 Object 数组,并且往 Object 数组赋值时,才会触发此 bug,代码和原因如图:
图片描述官方查看文档地址:https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652 ,问题在 Java 9 中被解决。

2.2 新增和扩容实现

新增就是往数组中添加元素,主要分成两步:

  • 判断是否需要扩容,如果需要执行扩容操作;
  • 直接赋值。

两步源码体现如下:

public boolean add(E e) {
  //确保数组大小是否足够,不够执行扩容,size 为当前数组的大小
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  //直接赋值,线程不安全的
  elementData[size++] = e;
  return true;
}

我们先看下扩容(ensureCapacityInternal)的源码:

private void ensureCapacityInternal(int minCapacity) {
  //如果初始化数组大小时,有给定初始值,以给定的大小为准,不走 if 逻辑
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  //确保容积足够
  ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
  //记录数组被修改
  modCount++;
  // 如果我们期望的最小容量大于目前数组的长度,那么就扩容
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}
//扩容,并把现有数据拷贝到新的数组里面去
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  // oldCapacity >> 1 是把 oldCapacity 除以 2 的意思
  int newCapacity = oldCapacity + (oldCapacity >> 1);

  // 如果扩容后的值 < 我们的期望值,扩容后的值就等于我们的期望值
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

  // 如果扩容后的值 > jvm 所能分配的数组的最大值,那么就用 Integer 的最大值
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
 
  // 通过复制进行扩容
  elementData = Arrays.copyOf(elementData, newCapacity);
}

注解应该比较详细,我们需要注意的四点是:

  • 扩容的规则并不是翻倍,是原来容量大小 + 容量大小的一半,直白来说,扩容后的大小是原来容量的 1.5 倍;

  • ArrayList 中的数组的最大值是 Integer.MAX_VALUE,超过这个值,JVM 就不会给数组分配内存空间了。

  • 新增时,并没有对值进行严格的校验,所以 ArrayList 是允许 null 值的。

从新增和扩容源码中,下面这点值得我们借鉴:

  • 源码在扩容的时候,有数组大小溢出意识,就是说扩容后数组的大小下界不能小于 0,上界不能大于 Integer 的最大值,这种意识我们可以学习。

扩容完成之后,赋值是非常简单的,直接往数组上添加元素即可:elementData [size++] = e。也正是通过这种简单赋值,没有任何锁控制,所以这里的操作是线程不安全的,对于新增和扩容的实现,画了一个动图,如下:
图片描述

2.3 扩容的本质

扩容是通过这行代码来实现的:Arrays.copyOf(elementData, newCapacity);,这行代码描述的本质是数组之间的拷贝,扩容是会先新建一个符合我们预期容量的新数组,然后把老数组的数据拷贝过去,我们通过 System.arraycopy 方法进行拷贝,此方法是 native 的方法,源码如下:

/**
 * @param src     被拷贝的数组
 * @param srcPos  从数组那里开始
 * @param dest    目标数组
 * @param destPos 从目标数组那个索引位置开始拷贝
 * @param length  拷贝的长度 
 * 此方法是没有返回值的,通过 dest 的引用进行传值
 */
public static native void arraycopy(Object src, int srcPos,
                                    Object dest, int destPos,
                                    int length);

我们可以通过下面这行代码进行调用,newElementData 表示新的数组:

System.arraycopy(elementData, 0, newElementData, 0,Math.min(elementData.length,newCapacity))

2.4 删除

ArrayList 删除元素有很多种方式,比如根据数组索引删除、根据值删除或批量删除等等,原理和思路都差不多,我们选取根据值删除方式来进行源码说明:

public boolean remove(Object o) {
  // 如果要删除的值是 null,找到第一个值是 null 的删除
  if (o == null) {
    for (int index = 0; index < size; index++)
      if (elementData[index] == null) {
        fastRemove(index);
        return true;
      }
  } else {
    // 如果要删除的值不为 null,找到第一个和要删除的值相等的删除
    for (int index = 0; index < size; index++)
      // 这里是根据  equals 来判断值相等的,相等后再根据索引位置进行删除
      if (o.equals(elementData[index])) {
        fastRemove(index);
        return true;
      }
  }
  return false;
}

我们需要注意的两点是:

  • 新增的时候是没有对 null 进行校验的,所以删除的时候也是允许删除 null 值的;
  • 找到值在数组中的索引位置,是通过 equals 来判断的,如果数组元素不是基本类型,需要我们关注 equals 的具体实现。

上面代码已经找到要删除元素的索引位置了,下面代码是根据索引位置进行元素的删除:

private void fastRemove(int index) {
  // 记录数组的结构要发生变动了
  modCount++;
  // numMoved 表示删除 index 位置的元素后,需要从 index 后移动多少个元素到前面去
  // 减 1 的原因,是因为 size 从 1 开始算起,index 从 0开始算起
  int numMoved = size - index - 1;
  if (numMoved > 0)
    // 从 index +1 位置开始被拷贝,拷贝的起始位置是 index,长度是 numMoved
    System.arraycopy(elementData, index+1, elementData, index, numMoved);
  //数组最后一个位置赋值 null,帮助 GC
  elementData[--size] = null;
}

从源码中,我们可以看出,某一个元素被删除后,为了维护数组结构,我们都会把数组后面的元素往前移动,下面动图也演示了其过程:
图片描述

2.5 迭代器

如果要自己实现迭代器,实现 java.util.Iterator 类就好了,ArrayList 也是这样做的,我们来看下迭代器的几个总要的参数:

int cursor;// 迭代过程中,下一个元素的位置,默认从 0 开始。
int lastRet = -1; // 新增场景:表示上一次迭代过程中,索引的位置;删除场景:为 -1。
int expectedModCount = modCount;// expectedModCount 表示迭代过程中,期望的版本号;modCount 表示数组实际的版本号。

迭代器一般来说有三个方法:

  • hasNext 还有没有值可以迭代
  • next 如果有值可以迭代,迭代的值是多少
  • remove 删除当前迭代的值

我们来分别看下三个方法的源码:

hasNext

public boolean hasNext() {
  return cursor != size;//cursor 表示下一个元素的位置,size 表示实际大小,如果两者相等,说明已经没有元素可以迭代了,如果不等,说明还可以迭代
}

next

public E next() {
  //迭代过程中,判断版本号有无被修改,有被修改,抛 ConcurrentModificationException 异常
  checkForComodification();
  //本次迭代过程中,元素的索引位置
  int i = cursor;
  if (i >= size)
    throw new NoSuchElementException();
  Object[] elementData = ArrayList.this.elementData;
  if (i >= elementData.length)
    throw new ConcurrentModificationException();
  // 下一次迭代时,元素的位置,为下一次迭代做准备
  cursor = i + 1;
  // 返回元素值
  return (E) elementData[lastRet = i];
}
// 版本号比较
final void checkForComodification() {
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
}

从源码中可以看到,next 方法就干了两件事情,第一是检验能不能继续迭代,第二是找到迭代的值,并为下一次迭代做准备(cursor+1)。

remove

public void remove() {
  // 如果上一次操作时,数组的位置已经小于 0 了,说明数组已经被删除完了
  if (lastRet < 0)
    throw new IllegalStateException();
  //迭代过程中,判断版本号有无被修改,有被修改,抛 ConcurrentModificationException 异常
  checkForComodification();

  try {
    ArrayList.this.remove(lastRet);
    cursor = lastRet;
    // -1 表示元素已经被删除,这里也防止重复删除
    lastRet = -1;
    // 删除元素时 modCount 的值已经发生变化,在此赋值给 expectedModCount
    // 这样下次迭代时,两者的值是一致的了
    expectedModCount = modCount;
  } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
  }
}

这里我们需要注意的两点是:

  • lastRet = -1 的操作目的,是防止重复删除操作
  • 删除元素成功,数组当前 modCount 就会发生变化,这里会把 expectedModCount 重新赋值,下次迭代时两者的值就会一致了

2.6 时间复杂度

从我们上面新增或删除方法的源码解析,对数组元素的操作,只需要根据数组索引,直接新增和删除,所以时间复杂度是 O (1)。

2.7 线程安全

我们需要强调的是,只有当 ArrayList 作为共享变量时,才会有线程安全问题,当 ArrayList 是方法内的局部变量时,是没有线程安全的问题的。

ArrayList 有线程安全问题的本质,是因为 ArrayList 自身的 elementData、size、modConut 在进行各种操作时,都没有加锁,而且这些变量的类型并非是可见(volatile)的,所以如果多个线程对这些变量进行操作时,可能会有值被覆盖的情况。

类注释中推荐我们使用 Collections#synchronizedList 来保证线程安全,SynchronizedList 是通过在每个方法上面加上锁来实现,虽然实现了线程安全,但是性能大大降低,具体实现源码:

public boolean add(E e) {
    synchronized (mutex) {// synchronized 是一种轻量锁,mutex 表示一个当前 SynchronizedList
        return c.add(e);
    }
}

总结

本文从 ArrayList 整体架构出发,落地到初始化、新增、扩容、删除、迭代等核心源码实现,我们发现 ArrayList 其实就是围绕底层数组结构,各个 API 都是对数组的操作进行封装,让使用者无需感知底层实现,只需关注如何使用即可。

立即订阅 ¥ 68.00

你正在阅读课程试读内容,订阅后解锁课程全部内容

精选留言 48
欢迎在这里发表留言,作者筛选后可公开显示
  • 时间复杂度说的太简单了
    0
    回复
    2021-06-09
  • abstractList中已经有迭代器了,为什么还要ArraysList还要在实现一次?
    0
    回复
    2021-02-19
  • 一直搞不清迭代器里版本号的判断有何作用,还有就是删除的时候lastRet要赋值为-1,以防重复删除,那如果我要删除几个元素,当我删完第一个的时候lastRet就已经是-1了,那我删第二个时lastRet=-1那就不是不能删了吗
    1
    回复
    2020-09-27
    • next方法,会给lastRet = cursor 且 cursor = cursor+1,从而保证了 有元素的情况下,lastRet 不会是-1
      回复
      2020-10-14 13:44:21
    • 为了防止在迭代过程中,list被修改,可以做快速报错
      回复
      2020-10-30 17:27:04
    • 可以去了解一下快速失败机制,如果迭代过程中,发生了并发修改。modCount和预期值不同,就会直接失败,不会继续迭代。即快速失败,
      回复
      2020-11-11 17:25:29
  • 初始化时,“指定大小初始化”和“指定初始化数据初始化”有什么区别吗?
    1
    回复
    2020-09-20
    • 指定大小初始化是指你要定义多大的数组, 指定初始化数据初始化是指你给定数组,大小根据数组元素的个数来定
      回复
      2020-09-22 11:38:42
  • remove操作中为什么没有缩容操作?比如当前元素个数小于数组大小的二分之一,创建一个大小为原来二分之一的新数组,然后将元素拷贝到新数组中。
    0
    回复
    2020-08-27
    • ArrayList没有自动缩容操作,trimToSize()可以手动缩容,具体可以看这篇 https://juejin.im/post/6844904195812753415
      回复
      2020-11-11 17:26:43
  • 线程安全的推荐使用使用JUC中的CopyOnWriteArrayList类进行替换。具体详情可参考JUC框架。不推荐用Collections#synchronizedList;synchronize锁是悲观锁,粒度太大!
    1
    回复
    2020-08-21
    • 也是要分场景的吧
      回复
      2020-12-18 16:37:33
    • Collections#synchronizedList 虽然会阻塞操作,但是至少能保证读到的数据是一致的 , CopyOnWriteArrayList在写操作没完成的时候虽然不会阻塞读操作,但是读到的数据可能不是最新的.
      回复
      2021-06-22 14:33:01
  • 指定初始数据初始化时,没有调用add方法前,size是不是等于Capacity?
    1
    回复
    2020-07-22
  • 我比较好奇的是,在 remove 时需要判断 modCount,然后可能抛 ConcurrentModificationException 异常,这个有啥作用嘛?比较疑惑这个 modCount 有啥实际意义嘛?
    1
    回复
    2020-03-31
    • 一般都是用增强for循环遍历集合,增强for只是个语法糖,本质上还是迭代器遍历。modCount和expectedModCount其实就是个版本号,通过modCount和expectedModCount能感知到ArrayList是否被并发读写,ArrayList是非线程安全的,并发读写极有可能出错,于是JDK直接提供了快速失败机制,省的你出现奇怪的错误。通过这个快速失败机制也能看出来,JDK就是要告诉你ArrayList不能并发读写,就算你能容忍并发读写带来的错误也不行,人家的设计理念就不允许你这么做。
      回复
      2020-04-12 23:54:01
    • 明白了,谢谢~
      回复
      2020-04-15 08:58:02
    • 我还有一个问题,在 ArrayList 的 iterator() 方法返回的迭代器对象里,判断 hasNext 是 cursor != size;,不应该是 cursor &lt; size; 更好理解嘛? 我看 LinkedList 的 listIterator 迭代器里面的 hasNext 就是这样写的。
      回复
      2020-04-15 09:04:27
    点击展开后面 4
  • 如果我们不指定位置直接添加元素时(add(E element)),元素会默认会添加在最后,不会触发底层数组的复制,不考虑底层数组自动扩容的话,时间复杂度为O(1) ,在指定位置添加元素(add(int index, E element)),需要复制底层数组,根据最坏打算,时间复杂度是O(n)。
    10
    回复
    2020-03-03
    点击展开后面 1
  • remove 元素后,为何要将 numMoved 的元素向前移动再将 --size 的元素赋值为 null,而不是直接将被删除元素索引位置赋值为 null 呢?是为了让数组看起来更连续吗? [1,2,3,4,5,6] -> [1,2,3,5,6,null] 为何不是 [1,2,3,null,5,6]。
    1
    回复
    2020-02-27
    点击展开后面 2
  • 老师您好,请问remove()方法的使用情境是什么样的啊,已经有了删除指定元素,和删除指定位置的元素,这个无参数的remove()方法什么时候使用呢?
    0
    回复
    2020-02-13
    • 你看下这个方法是怎么用的就知道啦
      回复
      2020-03-19 07:28:41
    • 无参remove你说的是迭代器里面的吧?ArrayList.this.remove(lastRet);,直接移除当前迭代的值
      回复
      2020-04-12 23:56:22
  • if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); 在ArrayList迭代器的next方法中第一个if判断 i如果不大于 size说明是合法的 i,那么第二个if不就没有必要判断是否大于数组长度了吗,如果 i小于size肯定也小于 elementData.length啊(siz不是永远小于elementData.length的吗)。如果 i大于等于 size,第一个if直接就抛出异常了,第二个 if貌似永远不会被执行
    0
    回复
    2020-02-13
    • elementData.length的长度是有可能大于size的,在remove方法当中,最后一步elementData[--size] = null;将size-1,但是elementData.length在此时还没有-1,只是将最后一位置null. 还有一个方法public void trimToSize() { modCount++; if (size &lt; elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }可以去看看源码
      回复
      2020-03-12 21:13:09
    • 看错你的意思了...抱歉,好像确实这第二个if没有存在的意义
      回复
      2020-03-12 21:33:30
    • 应该判断的情况是多线程情况下的,在计算完size以后,如果有别的线程删除了元素的话,那么length是会变小,而这种情况下size就可能大于length,所以后面再判断一次.只是猜想,不知道是不是这样
      回复
      2020-03-12 21:57:25
    点击展开后面 2
  • Arrays.asList 本身是 Arrays 内部实现,这个 BUG 我感觉太难出现了
    2
    回复
    2020-02-12
  • MAX_ARRAY_SIZE 不是Integer.MAX_VALUE。而是MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    4
    回复
    2020-02-10
  • ArrayList中add方法的时间复杂度不是O(1)吧? 源码中的解释是这样的呀:“The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. ”
    0
    回复
    2020-02-06
    • 作者此处应该是特指在ArrayList尾部加入1个元素。
      回复
      2020-02-08 21:06:15
    • 新增或删除方法的源码解析,对数组元素的操作,只需要根据数组索引,直接新增和删除,所以时间复杂度是 O (1)。这里没有考虑保证顺序连续,元素迁移的情况。
      回复
      2020-11-15 12:55:36
  • ArrayList testBatchInsert 调换单个循环和批量循环时间顺序显示结果刚好相反,单独放入到两个方法执行,显示结果差距不是很大,希望老师能够抽时间答疑解惑
    1
    回复
    2020-01-06
  • arraylist 在初始化的时候,有两个构造函数。一个无参,一个有参。 我有个问题,无参的时候给了一个空数组;有参情况下,参数为 0 的时候,也是给空数组。 但是代码里面设置的两个空数组,为何不用同一个呢?
    0
    回复
    2019-12-17
    • 为什么有两个空数组,看源码注释 /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
      回复
      2020-01-07 18:23:15
    • 用来区分第一次add元素时怎样给数组扩容
      回复
      2020-03-12 20:59:43
  • private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;这个 -8 是为什么?
    1
    回复
    2019-12-07
    • 一些vm在数组中保留一些头字。尝试分配较大的数组可能会导致OutOfMemory错误:请求的数组大小超过了虚拟机限制
      回复
      2020-02-18 20:30:46
  • synchronized 是一种轻量锁 。。。 synchronized 不是重量锁么。。。
    1
    回复
    2019-12-07
    点击展开后面 1
  • 迭代器的意义是什么?迭代器中的功能用for循环也完全都能简单实现吧
    1
    回复
    2019-12-05
    • foreach增强就是靠着迭代器实现的。 迭代器里还有安全的remove方法。
      回复
      2019-12-07 01:37:12
    • 迭代器是一种同一的集合调用机制,调用方式都一样的,就如同接口一样,有一个统一的如口
      回复
      2019-12-07 15:58:32
    • 下面几个同学回答的都非常好,我理解这可能就是一种抽象的思想,比如我们想要 List 循环时,我们给 List 写 for 循环,想要 Set 循环时,我们给 Set 写 for 循环,如果再来 Map 呢?这时候我们会发现这些循环基本都是重复代码,而且还有一些坑在里面,这时候我们就可以把循环这种行为抽象成迭代器,这样也方便容器的扩展,比如以后新建一个容器后,只要容器实现了迭代器的规范,自然就拥有的了迭代的功能,这就是我们平时工作中经常要到的方法论:先复制粘贴,然后再把公用的抽象,最后经过验证后,把抽象的接口提供给其他程序使用。
      回复
      2019-12-08 13:41:07
  • 老师,elementData设置成了transient,那ArrayList是怎么把元素序列化的呢?
    1
    回复
    2019-11-02
    • 同学你好,这个问题其实自己 debug 一下基本就能发现问题,多多 debug。 和序列化工具关系很大,我用的是阿里的 fastjson 进行序列化,debug 在 com.alibaba.fastjson.serializer.ListSerializer 68行左右,会把 List 里面每个值拿出来 append 到 SerializeWriter(可以理解成 StringBuffer的缓冲区) 上,最后输出一定格式的字符串,如果是其他序列化工具的话,可能又是其他的方式了,transient 关键字用途是好的,但序列化方式很多,两者没有太大的关系。
      回复
      2019-11-04 10:44:10
    • 他自己实现了那个接口啊
      回复
      2019-11-05 12:39:26
    • ArrayList里面的readObject和writeObject方法了解一下??
      回复
      2019-11-16 11:30:53
  • 大佬,ArrayList中存储数据的数组为啥是Object[],而不是E[]。是因为泛型在1.5才引入,而ArrayList在1.2就有了吗?
    1
    回复
    2019-10-28
    • 你分析的很有道理的。
      回复
      2019-10-31 12:55:27
    • 也许还有另外一个原因,Java是不支持创建泛型数组的 。 当然可以创建Object数组然后强转为E[]。
      回复
      2019-11-20 19:31:58
  • size 不是当前数组的大小吧,而是元素的个数
    0
    回复
    2019-10-24
    • 是的 在所有的列表中都有Capacity 和 size 两个字段 Capacity是指容量 size 是指目前列表中元素个数
      回复
      2019-12-05 21:48:36
    • 请问 elementData.length 和size 有什么关系呢?两者相等么 if (minCapacity - elementData.length &gt; 0) grow(minCapacity); 如果两者相等,那么minCapacity 总是 size + 1, 总是大于elementData.length, 那么总会执行grow方法
      回复
      2020-03-12 22:37:55
    • size是数组元素的个数,elementData.length是数组的大小,一般来说size会小于等于elementData.length
      回复
      2020-05-08 15:31:01
  • int oldCapacity = elementData.length; // oldCapacity >> 1 是把 oldCapacity 除以 2 的意思 int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果扩容后的值 < 我们的期望值,扩容后的值就等于我们的期望值 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; newCapacity已经是oldCapacity除以2再加上oldCapacity了 那无论如何都是不存在的newCapacity小于oldCapacity if (newCapacity - minCapacity < 0) newCapacity = minCapacity; 为什么还要这么写?
    2
    回复
    2019-10-21
    • 同学你好,你可以看下 allAll 方法,这个方法引起的扩容,minCapacity 有可能非常大,甚至大于 minCapacity,就会出现 newCapacity - minCapacity 的情况。
      回复
      2019-10-21 22:03:54
    • 参考07节List源码会问那些问面试 1.2.3 就有这种CASE
      回复
      2019-11-18 16:12:47
  • 向末尾插入数据的时候,确实是o(1),如果刚好在需要扩容的临界点进行添加和删除,那么不就是o(n)了么
    3
    回复
    2019-10-19
    • 是的,正好碰到扩容时候是的。
      回复
      2019-10-21 22:00:13
    • 根据均摊时间复杂度分析,当我们添加到最后一个元素时,如果此时再往里添加一个元素,那么就将进行数组的扩容操作。这次扩容的算法复杂度为O(n),此时我们就要用到均摊复杂度分析法,前面n次操作耗费时间总共为n,第n+1次操作耗费时间为n,相当于执行n+1次操作耗费的时间为2n,那么平均来看,我们每次操作其实耗费的时间为2,他仍然是一个O(1)级别的算法。在这里我把一次线性操作(第n+1次)的复杂度均摊到前面n次操作中。
      回复
      2019-11-18 15:23:12
    • 那如果我在扩容以后立马缩容。就在这个临界点来回添加删除,那时间复杂度不就变成了on了么
      回复
      2019-11-18 16:36:02
    点击展开后面 4
  • 老师,如果数组刚好处于扩容的临界点,这时候进行数组的增加,再减少,每次的复杂度都会为o(n),并不是所说的o(1)呀
    3
    回复
    2019-10-19
    • ArrayList根本就没有缩容这回事情啊,你remove数据,只是移动数据并没有改变数组的大小,所以只有扩容,没有缩容
      回复
      2019-12-10 23:10:14
    • 你吃了,如果扩容和缩容倍数相乘为1才有这种情况,ArrayList的扩容是1.5倍,不会出现这种边界情况的。如果扩容是2倍,缩容是0.5,才会有这种情况
      回复
      2020-03-03 11:16:00
  • 老师,想问您一个问题: 就是我们担心的并发下的数据安全问题,有2个概念想跟老师确认下,1、如果不是操作数据库的数据 是那些共享数据 ,此时并发下,多个线程操作它就会存在线程安全问题, 然后如果是在方法内,并发的情况下,多个线程去操作方法内的变量,就不会出现线程安全问题,此时相当于每个线程操作的其实是自己内存里面的东西; 2、第二个的话就是操作数据库中的数据 那么是不是我们想控制线程执行的顺序,来保证数据的安全,一方面是要加上事务去管理, 另外的话可能要一些数据库的锁 , 如 for update排他锁这些,来实现我们的需要; 3、所以java层面的如sychronized(轻量锁)等 和 数据事务锁其实是2个概念吧,一个是Java层面的,一个是数据库层面的,2者并没有啥联系, 所以,老师,请教您一下,我分析的概念对嘛?
    2
    回复
    2019-10-18
    • 分析对的哈,不过我们很少使用 for update 锁,数据库资源本来就很紧张,使用数据库会加剧数据库资源紧张的局面,一般我们都用分布式 redis 锁 + 数据库版本号来解决并发请求的问题。
      回复
      2019-10-19 10:40:34
    • 懂了,谢谢老师,哈哈
      回复
      2019-10-19 13:56:44
  • 迭代器中remove方法不能单独调用的,必须先调用next方法才能给lastRet变量赋值。好像场景正常也都是先next取出值,满足条件才remove的,源码的设计真的是返璞归真
    3
    回复
    2019-10-12
  • 老师,2.7有个疑问。当ArrayList是方法内的局部变量时,是没有线程安全的问题的,但我在学JVM内存模型中有学到对象实例都是存在线程共享的JAVA堆中的,修改的都是同一个对象实例,这样也没有线程安全问题吗?或者说老师能具体举一下具体情境ArrayList下线程安全的例子吗?
    1
    回复
    2019-10-08
    • 同学你好,方法中的局部变量是肯定没有安全的问题的,除非你把局部变量用引用传值给多个子线程。 方法中的局部变量是属于每个线程栈,线程栈之间都是隔离的,所以不会共享资源,也不会有线程安全问题,论证的话,也很简单,你看高并发的互联网公司,方法中的局部变量使用时从不加锁,也不考虑其线程安全就清楚了哈。 具体场景你看下 《18 场景集合:并发 List、Map 的应用场景》这章,其中的 flowMap 是共享变量,有线程安全的问题。
      回复
      2019-10-08 19:21:32
    • 明白了~谢谢老师:)
      回复
      2019-10-09 10:31:49
    • 虽然对象实例放在堆中,堆也是共享的,但是线程栈中的局部变量只存在栈帧中的局部变量表中,和其他线程是隔离的,所以其他线程中的变量是引用不到堆中的该对象实例的。
      回复
      2020-03-17 11:07:08
  • ArrayList删除元素的时间复杂度怎么能是O(1)呢?他不是有元素的移动吗?
    2
    回复
    2019-09-25
    • 应该是O(n)吧
      回复
      2019-09-26 07:44:47
    • 我也觉得老师讲错了吧这块,还有如果扩容的话,要copy数组,怎么会是o(1)<br />
      回复
      2019-09-28 06:10:20
    • 同学你好,这个在下面的回复中有提到哈,文中的表达是:只需要根据数组索引,直接新增和删除,所以时间复杂度是 O (1),说的是可以直接根据数组的索引,找到数组的位置,这个时间复杂度是 O (1)。
      回复
      2019-10-08 11:50:33
    点击展开后面 2
  • 3、还是newCapacity方法 if (minCapacity < 0) // overflow throw new OutOfMemoryError(); 这种情况是Integer循环回去了吗,比如到达Integer.MAX_VALUE,继续增加,就会变成负数 4、既然jvm只能分配MAX_ARRAY_SIZE个长度,那hugeCapacity(int minCapacity)方法中为什么又做了 (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE这样的判断 本来想一次贴代码来着,结果留言有字数限制,问题还分了两次提问,所以代码就不贴了,麻烦老师了
    1
    回复
    2019-09-16
    • 3:不是循环回去了,Integer.MAX_VALUE 的值是 2147483647,继续 +1 就会变成 -2147483648。 4:Integer.MAX_VALUE 是 int 类型的大小限制,不是 JVM 限制,判断只是正常的业务校验哈。
      回复
      2019-09-17 18:50:55
    • 第四个问题:那ArrayList的最大长度就是Integer.MAX_VALUE,不是MAX_ARRAY_SIZE吧,这样理解对吗
      回复
      2019-09-17 21:44:16
    • 是的,最大能到 Integer.MAX_VALUE
      回复
      2019-09-18 21:28:00
    点击展开后面 6
  • 老师,请教几个问题: 1.9中 1、grow方法【line241~243】为什么要将size+1呢 代码: private Object[] grow() { return grow(size + 1); } 2、newCapacity方法中【line254~268】 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA),这种情况下minCapacity肯定是1呀,Math.max(DEFAULT_CAPACITY, minCapacity)这行代码使用max方法的作用是什么,感觉完全可以不用呀
    1
    回复
    2019-09-16
    • 第一个问题,你说的源码我完全找不到哈。第二个问题,当使用入参数是 Collection&lt;? extends E&gt; c 的构造器的时候,minCapacity 不一定是 1哦。
      回复
      2019-09-17 18:41:29
    • 第二个问题:满足if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)这个条件的只有无参构造的list吧,如果是指定元素的构造public ArrayList(Collection&lt;? extends E&gt; c) ,elementData是不满足这个条件的
      回复
      2019-09-17 21:42:35
    • 你好 同学,是的哈。
      回复
      2019-09-18 21:24:38
  • 钻个牛角尖: 在使用迭代器或增强for循环时, 如果数组大小被改变未必会抛异常.比如在迭代器中使用迭代器的remove()方法, 或在增强for循环中增删元素后就结束了当前循环
    5
    回复
    2019-09-12
  • 准确的说成员变量size并不是表示当前数组的大小, 它表示的是当前集合元素的个数.举个例子:第一次向集合中插入一个元素后, 数组大小为10, 而size值为1
    0
    回复
    2019-09-12
  • 在GitHub中,文章源代码 ArrayListDemo中testBatchInsert 注释没有修改,应该是单个新增和批量新增
    0
    回复
    2019-09-10
    • 收到,demo 注释已修改,代码已提交。
      回复
      2019-09-11 12:37:10
    • 请问github源码 在哪里可以找到呢? url路径是啥呢
      回复
      2019-09-13 18:37:36
  • 老师厉害哦,学到很多。
    3
    回复
    2019-09-07
  • 内容细致,条理也比较清晰,真心不错。
    2
    回复
    2019-09-05
  • 「初始化时,如果你给定的大小 < 10,那么初始化大小是按照 10 计算的,并不是你给定的值;」 代码备注改了,总结没改噢
    0
    回复
    2019-09-03
  • "所以当你在初始化数组大小时,如果你给定的初始化大小是 4,其实还是拿着 10 去计算的"这个地方不太理解,这部分的if条件是elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA。如果给定初始化大小的话那么elementData就不会是DEFAULTCAPACITY_EMPTY_ELEMENTDATA了。
    3
    回复
    2019-09-02
    • 火眼金睛,感谢,已订正,快微信联系我,给你发个大红包。
      回复
      2019-09-03 09:39:21
  • 这里似乎是不对的 【如果你给定的初始化大小是 4,其实还是拿着 10 去计算的】 文档内的代码: 【【【 private void ensureCapacityInternal(int minCapacity) { //如果是空数组,就从最小容量和默认容量10之间取最大值 //所以当你在初始化数组大小时,如果你给定的初始化大小是 4,其实还是拿着 10 去计算的 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ...省略... } 】】】 这里如果初始化大小为4, 上面的if不会执行(此时 elementData = new Object[4]), 之后扩容还是到6, 9, 14...
    1
    回复
    2019-09-02
    • 火眼金睛,感谢,已订正,快微信联系我,给你发个大红包。
      回复
      2019-09-03 09:39:18
  • 如果我构造函数中传递的参数是4 this.elementData = new Object[initialCapacity]; 而这个时候size 值不应该变成4么 只是上面的数组里面存储的都是null而已
    1
    回复
    2019-09-01
  • 老师,没有看懂这段代码,为什么要!= Object[].class? if (elementData.getClass() != Object[].class) { elementData = Arrays.copyOf(elementData, size, Object[].class); }
    0
    回复
    2019-08-28
    • 这是因为 elementData 是个 Object 的数组哈。但入参的 Collection&lt;? extends E&gt; c 却不定是 Object 的数组,所以需要转化下。
      回复
      2019-08-31 09:05:39
  • 请问什么时候能更新完呀
    0
    回复
    2019-08-28
    • 同学你好 本专栏是每周二、周四进行更新,感谢支持 ^^
      回复
      2019-09-02 15:48:24
  • 04章,是不是还没发布?
    0
    回复
    2019-08-28
  • 老师,remove时后面的元素不是都向前移吗,最坏不应该是O(n)级复杂度吗,为什么文中说是O(1)
    1
    回复
    2019-08-28
    点击展开后面 2
  • 初始化那边是不是少了一个指定大小初始化的 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);
    0
    回复
    2019-08-28
  • 正在准备面试中,刷下源码对于技术面还可以放心一点,还挺全面的,工作中经常用到的知识点都能了解到
    2
    回复
    2019-08-27
    • 嗯嗯,基本都是工作中常用的点,希望你面试成功,平步青云。
      回复
      2019-08-27 19:18:03
  • 一直对于各个底层的实现很好奇,我觉得线程池、线程、集合、队列现在用的很多,看着老师这门课程写的很实用了,学到了 打卡~~
    2
    回复
    2019-08-27

点击展开剩余评论

千学不如一看,千看不如一练

手机
阅读

扫一扫 手机阅读

面试官系统精讲Java源码及大厂真题
立即订阅 ¥ 68.00

举报

0/150
提交
取消