Java基础——ArrayList详解

Java基础——ArrayList详解
  • ArrayList 内部是以动态数组的形式来存储数据的。这里的动态数组不是意味着去改变原有内部生成的数组的长度、而是保留原有数组的引用、将其指向新生成的数组对象、这样会造成数组的长度可变的假象。
  • ArrayList 具有数组所具有的特性、通过索引支持随机访问、所以通过随机访问ArrayList中的元素效率非常高、但是执行插入、删除时效率比较底下
  • ArrayList 实现了 Serializable 接口,因此它支持序列化,能够通过序列化传输,实现了 RandomAccess 接口,支持快速随机访问,实际上就是通过下标序号进行快速访问,实现了 Cloneable 接口,能被克隆。
  • ArrayList 不是线程安全的,只能用在单线程环境下,多线程环境下可以考虑用 Collections.synchronizedList(List l) 函数返回一个线程安全的 ArrayList 类,也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。

基础属性

ArrayList部分源码如下:

public class ArrayList<E> 
        extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable,java.io.Serializable{
        
    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    private transient Object[] elementData;
    
    private int size;

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    protected transient int modCount = 0;
}
复制代码
  • DEFAULT_CAPACITY:默认初始容量
  • EMPTY_ELEMENTDATA:一个空数组,方便使用,主要用于带参构造函数初始化和读取序列化对象等
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA:用于默认大小的空实例的共享空数组实例
    • DEFAULTCAPACITY_EMPTY_ELEMENTDATA 和EMPTY_ELEMENTDATA 的区别
    • 仅仅是为了区别用户带参为0的构造和默认构造的惰性初始模式对象。
    • 当用户带参为0的构造,第一次add时,数组容量grow到1。
    • 当用户使用默认构造时,第一次add时,容量直接grow到DEFAULT_CAPACITY(10)。
  • elementData:当前数据对象存放地方,当前对象不参与序列化
  • size:当前数组中元素的个数
  • MAX_ARRAY_SIZE:数组最大可分配容量
  • modCount:集合数组修改次数的标识(由AbstractList继承下来)

构造方法

//方法一
public ArrayList(int initialCapacity)
//方法二
public ArrayList()
//方法三
public ArrayList(Collection<? extends E> c){
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}
复制代码
  • 方法一:表示接受指定地容量值,初始化创建数组,建议在可估算数组大小时,创建ArrayList可指定
  • 方法二:是默认的构造方法,它将创建一个空数组
  • 方法三:接收一个 Collection 类的实例,将该 Collection 实例转换为 ArrayList 对象

add(E e)

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
复制代码

向ArrayList集合添加元素,最重要的方法是扩容数组

//方法一
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//方法二
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
//方法三
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
复制代码
  • 方法一:在第一次向ArrayList添加元素时,设置容量扩容到多少
  • 方法二:如果 当前数组容量<需要的最小容量,则准备给数组扩容
  • 方法三:扩容方法:
    • 扩容原理:
    • 获取当前数组容量
    • 扩容后新数组容量 newCapacity 为旧数组的1.5倍
    • 若值 newCapacity 比传入值 minCapacity 还要小,则使用传入 minCapacity ,若 newCapacity 比设定的最大数组容量大,则使用最大整数值
    • 使用 Arrays.copyof(elementData, newCapacity) 进行扩容

于此,add方法走的流程就是:先扩容,再赋值,然后返回true

add(int index, E element)

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,size - index);
    elementData[index] = element;
    size++;
}
复制代码

向指定位置添加元素:

rangeCheckForAdd

扩容方法总结

ArrayList在每次增加元素(可能是1个,也可能是一组)时,都要调用该方法来确保足够的容量。当容量不足以容纳当前的元素个数时,就设置新的容量为旧的容量的1.5倍加1,如果设置后的新容量还不够,则直接新容量设置为传入的参数(也就是所需的容量),而后用Arrays.copyof()方法将元素拷贝到新的数组。当容量不够时,每次增加元素,都要将原来的元素拷贝到一个新的数组中,这个操作代价很高,因此最好在创建ArrayList对象时就指定大概的容量大小,减少扩容操作的次数,或者使用LinkedList

ArrayList总结

  • ArrayList基于数组方式实现,无容量的限制(会扩容)
  • 添加元素时可能要扩容(所以最好预判一下),删除元素时不会减少容量(若希望减少容量可以使用trimToSize()),删除元素时,将删除掉的位置元素置为null,下次gc就会回收这些元素所占的内存空间
  • 线程不安全
  • add(int index, E element):添加元素到数组中指定位置的时候,需要将该位置及其后边所有的元素都整块向后复制一位
  • get(int index):获取指定位置上的元素时,可以通过索引直接获取(O(1))
  • remove(Object o)需要遍历数组
  • remove(int index)不需要遍历数组,只需判断index是否符合条件即可,效率比remove(Object o)高 contains(E)需要遍历数组

原文 

https://juejin.im/post/5f1c4089f265da22d46717f4

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » Java基础——ArrayList详解

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址