资讯专栏INFORMATION COLUMN

Java集合干货——ArrayList源码分析

wupengyu / 2988人阅读

摘要:关于的具体实现,一些基本的都也知道,譬如数组实现,线程不安全等等,但是更加具体的就很少去了解了,例如初始化的长度,扩容等。

前言

在之前的文章中我们提到过ArrayList,ArrayList可以说是每一个学java的人使用最多最熟练的集合了,但是知其然不知其所以然。关于ArrayList的具体实现,一些基本的都也知道,譬如数组实现,线程不安全等等,但是更加具体的就很少去了解了,例如:初始化的长度,扩容等。

本篇主要通过一些对源码的分析,讲解几个ArrayList常见的方法,以及和Vector的区别。

ArrayList 定义
public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable

ArrayList实际上是一个动态数组,容量可以动态的增长,其继承了AbstractList,实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。

RandomAccess接口,标记接口,表明List提供了随机访问功能,也就是通过下标获取元素对象的功能。

1.RandomAccess接口,标记接口,表明List提供了随机访问功能,也就是通过下标获取元素对象的功能。之所以是标记接口,是该类本来就具有某项能力,使用接口对其进行标签化,便于其他的类对其进行识别(instanceof)。
2.ArrayList数组实现,本身就有通过下标随机访问任意元素的功能。那么需要细节上注意的就是随机下标访问和顺序下标访问(LinkedList)的不同了。也就是为什么LinkedList最好不要使用循环遍历,而是用迭代器遍历的原因。
3.实现RandomAccess同时意味着一些算法可以通过类型判断进行一些针对性优化,例子有Collections的shuffle方法,源代码就不粘贴了,简单说就是,如果实现RandomAccess接口就下标遍历,反之迭代器遍历

实现了Cloneable, java.io.Serializable意味着可以被克隆和序列化。

初始化

在使用中我们经常需要new出来各种泛型的ArrayList,那么在初始化过程是怎样的呢?

如下一行代码,创建一个ArrayList对象

List list = new ArrayList<>();

我们来看源码,是如何初始化的,找到构造方法

//无参构造方法
public ArrayList() {
  super();
  this.elementData = EMPTY_ELEMENTDATA;
}

看到这些代码的时候,我也是不解的,elementData和EMPTY_ELEMENTDATA是什么啊?但是很明显EMPTY_ELEMENTDATA是一个常量,追本溯源我们去看一下成员属性。

//如果是无参构造方法创建对象的话,ArrayList的初始化长度为10,这是一个静态常量
private static final int DEFAULT_CAPACITY = 10;

//在这里可以看到我们不解的EMPTY_ELEMENTDATA实际上是一个空的对象数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

//保存ArrayList数据的对象数组缓冲区 空的ArrayList的elementData = EMPTY_ELEMENTDATA 这就是为什么说ArrayList底层是数组实现的了。elementData的初始容量为10,大小会根据ArrayList容量的增长而动态的增长。
    private transient Object[] elementData;
//集合的长度
    private int size;

执行完构造方法,如下图

可以说ArrayList的作者真的是很贴心,连缓存都处理好了,多次new出来的新对象,都指向同一个引用。

添加方法add
add(E e)
 /**
     * Appends the specified element to the end of this list.
     */
//增加元素到集合的最后
public boolean add(E e) {
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  //因为++运算符的特点 先使用后运算  这里实际上是
  //elementData[size] = e
  //size+1
  elementData[size++] = e;
  return true;
}

先不管ensureCapacityInternal的话,这个方法就是将一个元素增加到数组的size++位置上。

再说回ensureCapacityInternal,它是用来扩容的,准确说是用来进行扩容检查的。下面我们来看一下整个扩容的过程

//初始长度是10,size默认值0,假定添加的是第一个元素,那么minCapacity=1 这是最小容量 如果小于这个容量就会报错
//如果底层数组就是默认数组,那么选一个大的值,就是10
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //调用另一个方法ensureExplicitCapacity
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
      //记录修改的次数
        modCount++;

        // overflow-conscious code
      //如果传过来的值大于初始长度 执行grow方法(参数为传过来的值)扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
//真正的扩容
 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
   //新的容量是在原有的容量基础上+50% 右移一位就是二分之一
        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:
   //这里是重点 调用工具类Arrays的copyOf扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

//Arrays
public static  T[] copyOf(U[] original, int newLength, Class newType) {
  T[] copy = ((Object)newType == (Object)Object[].class)
    ? (T[]) new Object[newLength]
    : (T[]) Array.newInstance(newType.getComponentType(), newLength);
  System.arraycopy(original, 0, copy, 0,
                   Math.min(original.length, newLength));
  return copy;
}

add(int index, E element)

添加到指定的位置

public void add(int index, E element) {
  //判断索引是否越界,如果越界就会抛出下标越界异常
  rangeCheckForAdd(index);
//扩容检查
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  //将指定下标空出 具体作法就是index及其后的所有元素后移一位
  System.arraycopy(elementData, index, elementData, index + 1,size - index);
  //将要添加元素赋值到空出来的指定下标处
  elementData[index] = element;
  //长度加1
  size++;
}
//判断是否出现下标是否越界
private void rangeCheckForAdd(int index) {
  //如果下标超过了集合的尺寸 或者 小于0就是越界  
  if (index > size || index < 0)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
remove(int index)

ArrayList支持两种删除元素的方式

remove(int index) 按照下标删除 常用

remove(Object o) 按照元素删除 会删除和参数匹配的第一个元素

下面我们看一下ArrayList的实现

 /**
 移除list中指定位置的元素
     * Removes the element at the specified position in this list.
     所有后续元素左移 下标减1
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *参数是要移除元素的下标
     * @param index the index of the element to be removed
     返回值是被移除的元素
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
public E remove(int index) {
  //下标越界检查
  rangeCheck(index);
//修改次数统计
  modCount++;
  //获取这个下标上的值
  E oldValue = elementData(index);
//计算出需要移动的元素个数 (因为需要将后续元素左移一位 此处计算出来的是后续元素的位数)
  int numMoved = size - index - 1;
  //如果这个值大于0 说明后续有元素需要左移  是0说明被移除的对象就是最后一位元素
  if (numMoved > 0)
    //索引index只有的所有元素左移一位  覆盖掉index位置上的元素
    System.arraycopy(elementData, index+1, elementData, index,numMoved);
 // 将最后一个元素赋值为null  这样就可以被gc回收了
  elementData[--size] = null; // clear to let GC do its work
//返回index位置上的元素
  return oldValue;
}

//移除特定元素
public boolean remove(Object o) {
  //如果元素是null 遍历数组移除第一个null
  if (o == null) {
    for (int index = 0; index < size; index++)
      if (elementData[index] == null) {
        //遍历找到第一个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
}
ArrayList总结

底层数组实现,使用默认构造方法初始化出来的容量是10

扩容的长度是在原长度基础上加二分之一

实现了RandomAccess接口,底层又是数组,get读取元素性能很好

线程不安全,所有的方法均不是同步方法也没有加锁,因此多线程下慎用

顺序添加很方便

删除和插入需要复制数组 性能很差(可以使用LinkindList)

为什么ArrayList的elementData是用transient修饰的?

transient修饰的属性意味着不会被序列化,也就是说在序列化ArrayList的时候,不序列化elementData。

为什么要这么做呢?

elementData不总是满的,每次都序列化,会浪费时间和空间

重写了writeObject 保证序列化的时候虽然不序列化全部 但是有的元素都序列化

所以说不是不序列化 而是不全部序列化。

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
        // Write out array length
       s.writeInt(elementData.length);
    // Write out all elements in the proper order.
for (int i=0; i
ArrayList和Vector的区别
标准答案

ArrayList是线程不安全的,Vector是线程安全的

扩容时候ArrayList扩0.5倍,Vector扩1倍

那么问题来了

ArrayList有没有办法线程安全?

Collections工具类有一个synchronizedList方法

可以把list变为线程安全的集合,但是意义不大,因为可以使用Vector

Vector为什么是线程安全的?

老实讲,抛开多线程 它俩区别没多大,但是多线程下就不一样了,那么Vector是如何实现线程安全的,我们来看几个关键方法

public synchronized boolean add(E e) {
  modCount++;
  ensureCapacityHelper(elementCount + 1);
  elementData[elementCount++] = e;
  return true;
}

public synchronized E remove(int index) {
  modCount++;
  if (index >= elementCount)
    throw new ArrayIndexOutOfBoundsException(index);
  E oldValue = elementData(index);

  int numMoved = elementCount - index - 1;
  if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
  elementData[--elementCount] = null; // Let gc do its work

  return oldValue;
}

就代码实现上来说,和ArrayList并没有很多逻辑上的区别,但是在Vector的关键方法都使用了synchronized修饰。

我不能保证每一个地方都是对的,但是可以保证每一句话,每一行代码都是经过推敲和斟酌的。希望每一篇文章背后都是自己追求纯粹技术人生的态度。

永远相信美好的事情即将发生。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/68232.html

相关文章

  • Java集合干货——ArrayList源码分析

    摘要:关于的具体实现,一些基本的都也知道,譬如数组实现,线程不安全等等,但是更加具体的就很少去了解了,例如初始化的长度,扩容等。 前言 在之前的文章中我们提到过ArrayList,ArrayList可以说是每一个学java的人使用最多最熟练的集合了,但是知其然不知其所以然。关于ArrayList的具体实现,一些基本的都也知道,譬如数组实现,线程不安全等等,但是更加具体的就很少去了解了,例如:...

    Render 评论0 收藏0
  • Java集合干货——LinkedList源码分析

    摘要:前言在上篇文章中我们对对了详细的分析,今天我们来说一说。他们之间有什么区别呢最大的区别就是底层数据结构的实现不一样,是数组实现的具体看上一篇文章,是链表实现的。至于其他的一些区别,可以说大部分都是由于本质不同衍生出来的不同应用。 前言 在上篇文章中我们对ArrayList对了详细的分析,今天我们来说一说LinkedList。他们之间有什么区别呢?最大的区别就是底层数据结构的实现不一样,...

    jsdt 评论0 收藏0
  • net - 收藏集 - 掘金

    摘要:再者,现在互联网的面试中上点的都会涉及一下或者的问题个高级多线程面试题及回答后端掘金在任何面试当中多线程和并发方面的问题都是必不可少的一部分。假如源码分析之掘金概念是中集合的一种实现。 攻破 JAVA NIO 技术壁垒 - 后端 - 掘金现在使用NIO的场景越来越多,很多网上的技术框架或多或少的使用NIO技术,譬如Tomcat,Jetty。学习和掌握NIO技术已经不是一个JAVA攻城狮...

    岳光 评论0 收藏0
  • Java集合源码分析系列-(一)ArrayList源码剖析

    摘要:需要注意的是,通过构造函数定义初始量是动态数组的实际大小。带容量的构造函数新建一个容量为的数组默认构造函数,默认为空构造一个包含指定元素的第一个构造方法使用提供的来初始化数组的大小。 前言 今天介绍经常使用的一个Java集合类——ArrayList(基于JDK1.8.0_121)。ArrayList在工作和日常面试中经常被使用或者提到。总的来说,工作中使用ArrayList主要是因为动...

    Miyang 评论0 收藏0
  • java源码

    摘要:集合源码解析回归基础,集合源码解析系列,持续更新和源码分析与是两个常用的操作字符串的类。这里我们从源码看下不同状态都是怎么处理的。 Java 集合深入理解:ArrayList 回归基础,Java 集合深入理解系列,持续更新~ JVM 源码分析之 System.currentTimeMillis 及 nanoTime 原理详解 JVM 源码分析之 System.currentTimeMi...

    Freeman 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<