java集合中ArrayList源码解析是怎样的

发布时间:2021-09-30 10:32:13 作者:柒染
来源:亿速云 阅读:210
# Java集合中ArrayList源码解析是怎样的

## 一、ArrayList概述

### 1.1 ArrayList基本特性
ArrayList是Java集合框架中最常用的动态数组实现,位于`java.util`包中。作为List接口的可变数组实现,它提供了所有可选的列表操作,并允许存储所有元素(包括null)。

主要特点:
- **动态扩容**:容量自动增长以适应新增元素
- **非线程安全**:多线程环境下需要外部同步
- **快速随机访问**:基于数组实现,get/set操作时间复杂度O(1)
- **插入删除成本高**:平均时间复杂度O(n)

### 1.2 类继承关系
```java
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

关键接口实现: - RandomAccess:标记接口,支持快速随机访问 - Cloneable:支持浅克隆 - Serializable:支持序列化

二、核心数据结构

2.1 底层存储结构

transient Object[] elementData; // 实际存储元素的数组
private int size; // 当前元素数量

2.2 容量与大小

三、关键源码解析

3.1 构造方法

无参构造

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

指定初始容量

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException(...);
    }
}

3.2 扩容机制

添加元素时的扩容

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

private Object[] grow() {
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(
            oldCapacity,
            minCapacity - oldCapacity, // 最小增长量
            oldCapacity >> 1); // 默认增长50%
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

扩容策略: 1. 首次添加元素时扩容到DEFAULT_CAPACITY(10) 2. 后续每次扩容为原容量的1.5倍 3. 使用Arrays.copyOf进行数组复制

3.3 常用操作

添加元素

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index, elementData, index + 1, s - index);
    elementData[index] = element;
    size = s + 1;
}

删除元素

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;
    
    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);
    
    return oldValue;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null; // 清除引用,帮助GC
}

3.4 迭代器实现

private class Itr implements Iterator<E> {
    int cursor;       // 下一个元素索引
    int lastRet = -1; // 最后返回的元素索引
    int expectedModCount = modCount;
    
    public boolean hasNext() {
        return cursor != size;
    }
    
    @SuppressWarnings("unchecked")
    public E next() {
        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();
    }
}

快速失败机制通过比较modCountexpectedModCount实现

四、性能优化要点

4.1 初始化容量

4.2 批量操作

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    System.arraycopy(a, 0, elementData, s, numNew);
    size = s + numNew;
    return true;
}

4.3 空间回收

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

五、线程安全替代方案

5.1 同步包装

List list = Collections.synchronizedList(new ArrayList<>());

5.2 CopyOnWriteArrayList

六、与Vector的对比

特性 ArrayList Vector
线程安全 非线程安全 线程安全
扩容策略 增长50% 增长100%
迭代器 快速失败 安全失败
性能 更高 较低

七、典型应用场景

  1. 随机访问频繁:索引操作多的场景
  2. 尾部操作为主:添加删除主要在列表末尾
  3. 内存敏感环境:相比LinkedList更节省内存

八、总结

ArrayList作为Java集合框架的核心实现: 1. 基于动态数组实现,支持快速随机访问 2. 自动扩容机制平衡了空间和时间效率 3. 非线程安全设计带来了更好的单线程性能 4. 合理的初始化容量能显著提升性能

理解其底层实现有助于: - 正确选择和使用集合类 - 编写更高效的Java代码 - 在面试中展现扎实的基础知识

本文基于JDK 17源码分析,不同版本实现可能略有差异 “`

注:由于篇幅限制,这里提供的是精简后的核心内容框架。实际5400字文章需要: 1. 补充更多方法实现的详细解析 2. 增加性能测试数据对比 3. 添加更多使用示例和注意事项 4. 扩展与其他集合类的对比分析 5. 增加内存布局和GC影响的讨论

需要完整长文可告知具体扩展方向。

推荐阅读:
  1. ArrayList、LinkedList和Vector的源码解析,带你走近List的世界
  2. ArrayList的源码分析

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

java arraylist

上一篇:JavaScript反调试技巧是怎样的

下一篇:Twitter.com在用哪些JavaScript框架

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》