自学内容网 自学内容网
自学内容网 > 正文

java溯本求源之基础(二十六)之--List子类源码分析

🕗 发布于 2024-10-10 11:12 java  开发语言  

一、前言

        Java 集合框架（Java Collections Framework）是每个Java开发者必须熟知的基础部分，而List接口是其中最常见的数据结构之一。在实际开发中，List接口的不同实现类被广泛应用于各种场景。本篇文章通过对JDK 1.8版本的List接口源码分析，结合其子类如ArrayList、LinkedList等的实现，探讨其内部工作原理、自动扩容机制以及线程安全问题，帮助开发者更好地理解和优化程序。

二、List接口简介

2.1 List接口的定义

    List是Java集合框架中一个重要的接口，继承自Collection接口，用于存储有序且可重复的元素。List允许我们通过索引访问元素，并定义了常见的集合操作，如增加、删除、修改和遍历等。

List的部分定义如下：

public interface List<E> extends Collection<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    boolean add(E e);
    boolean remove(Object o);
    E get(int index);
    E set(int index, E element);
    void add(int index, E element);
    E remove(int index);
    int indexOf(Object o);
    int lastIndexOf(Object o);
    ListIterator<E> listIterator();
    List<E> subList(int fromIndex, int toIndex);
}
  • 索引访问：List允许通过索引快速访问元素，如get(int index)。
  • 重复元素：List可以存储重复的元素，这与Set接口形成了对比。
  • 有序性：List中的元素按照插入顺序进行存储和访问。

三、ArrayList源码解析及自动扩容机制

3.1 ArrayList的基本概述

    ArrayList是List接口的常用实现类之一，底层使用数组来存储元素。它的特点是通过动态调整数组的大小来应对不断变化的数据量，因此它的存储效率较高，适合频繁读取的场景。

3.2 ArrayList的源码分析

        在ArrayList的源码中，最重要的成员变量是：

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

    elementData是一个动态数组，用来存储ArrayList中的元素。size则表示当前数组中实际存储的元素个数。

3.3 自动扩容机制

   ArrayList的自动扩容机制是其最重要的特性之一。当我们往ArrayList中添加新元素时，如果当前数组容量不足以容纳新增元素，它会自动扩展数组的容量。这个过程由ensureCapacity()和grow()方法负责。

private void ensureCapacityInternal(int minCapacity) {
    // 确保容量足够，调用 ensureExplicitCapacity 方法
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    // 增加修改计数
    modCount++;

    // 溢出意识代码
    // 如果最小容量大于当前数组长度，则扩容
    if (minCapacity - elementData.length > 0) grow(minCapacity);
}

private void grow(int minCapacity) {
    // 溢出意识代码
    int oldCapacity = elementData.length; // 记录旧容量
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量为旧容量的 1.5 倍
    // 如果新容量仍小于最小容量，则设置为最小容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量超过最大数组大小，则调用 hugeCapacity 方法处理
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 最小容量通常接近当前大小，因此这是一个优化：
    elementData = Arrays.copyOf(elementData, newCapacity); // 扩容
}
  • grow()方法通过当前容量的1.5倍来扩展数组容量，这个机制有效地避免了每次添加元素时都要扩容的性能开销。
  • 如果需要的最小容量minCapacity比扩展后的容量大，则直接将容量设置为minCapacity，以确保足够的空间。
3.4 自动扩容的优缺点
  • 优点：在不确定数据量时，ArrayList提供了动态调整数组大小的能力，开发者无需手动管理内存分配。
  • 缺点：每次扩容都需要进行数组复制，可能造成性能开销，尤其是在处理大量数据时。因此，在大规模数据操作中，最好预估所需容量，使用ArrayList的构造函数设置初始容量。

四、LinkedList源码解析

4.1 LinkedList的基本概述

   LinkedList是List接口的另一常见实现类。不同于ArrayList，LinkedList底层采用的是双向链表结构。这使得LinkedList在频繁的插入和删除操作中表现优异，尤其是当操作不涉及随机访问时。

4.2 LinkedList的源码结构

   LinkedList通过内部类Node来维护链表的节点。每个节点包含三个元素：

private static class Node<E> {
    E item;         // 节点存储的元素
    Node<E> next;   // 指向下一个节点
    Node<E> prev;   // 指向上一个节点
}

LinkedList的元素是通过链表的形式串联起来的，通过next和prev指针可以方便地在链表中进行元素的增删改操作。

4.3 LinkedList的操作效率
  • 插入和删除操作：在LinkedList中，插入和删除元素的效率较高，特别是在首尾插入和删除时。因为不需要像ArrayList那样移动其他元素，只需要调整节点指针即可。
  • 随机访问效率低：由于LinkedList的底层是链表结构，随机访问某个元素时需要遍历链表，时间复杂度为O(n)，这使得LinkedList不适合频繁的随机访问。

五、线程安全的考虑

5.1 ArrayList与LinkedList的线程安全问题

ArrayList和LinkedList都是非线程安全的。这意味着当多个线程同时操作它们时，可能会导致数据不一致或抛出异常。解决线程安全问题的常见方法包括：

  • Collections.synchronizedList()：Java提供了Collections.synchronizedList()方法，将List包装成线程安全的版本。
List<String> syncList = Collections.synchronizedList(new ArrayList<>());

  • CopyOnWriteArrayList：CopyOnWriteArrayList是线程安全的List实现类，适合读多写少的场景。在写操作时，它会将整个数组复制一份，进行修改后再替换旧数组，因此适合并发环境下的读操作。
5.2 CopyOnWriteArrayList源码解析

    CopyOnWriteArrayList 是 List 接口的一个线程安全的实现类。它的特点是 “写时复制” 的机制，即每次修改操作（如 add()、set()、remove()）时，不是直接在原有数据结构上进行修改，而是先复制一份原有的数据，然后对新复制的数据进行修改。读操作则不受影响，仍然可以安全地访问原数据。

这种实现机制的优势在于，在并发环境下，多个线程可以安全地读操作，而不需要同步锁来协调。同时，由于写操作是在副本上进行，写操作的线程之间也不会发生竞争。

5.3 CopyOnWriteArrayList 源码分析

首先，CopyOnWriteArrayList 的底层依然是基于数组的结构，其重要的成员变量如下：

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}
  • 在添加元素时，CopyOnWriteArrayList会先对现有数组进行复制，确保在写操作过程中，其他线程仍然可以安全地读取旧数组。
  • 虽然这种机制确保了线程安全，但在写操作频繁的场景中，频繁的数组复制操作可能导致较大的性能开销，因此不适用于写操作较多的场景。

六. ArrayList、LinkedList 和 CopyOnWriteArrayList 的对比

特性ArrayListLinkedListCopyOnWriteArrayList
数据结构动态数组双向链表动态数组，写时复制
访问速度O(1) 随机访问O(n) 随机访问，O(1) 插入和删除O(1) 读取，O(n) 写操作
线程安全非线程安全非线程安全线程安全，读写分离
适用场景适合频繁读取、偶尔修改的场景适合频繁插入、删除操作适合读多写少的场景
性能开销写操作时可能频繁扩容插入和删除效率高，访问效率低写操作内存开销大，读操作性能高
扩容机制自动扩容，1.5倍不需要扩容写时复制，写入时创建新数组

七、List接口下的常用子类及应用场景

7.1 ArrayList
  • 应用场景：适合频繁读取和少量插入、删除操作的场景，尤其是需要随机访问的情况下。
  • 优点：读取操作快，适合做缓存或者需要频繁遍历数据的场景。
  • 缺点：插入、删除元素较慢，尤其是在中间位置操作时。
7.2 LinkedList
  • 应用场景：适合频繁插入、删除操作而随机访问较少的场景，比如队列和双端队列的实现。
  • 优点：插入、删除操作快，尤其是头部和尾
7.3 CopyOnWriteArrayList

   CopyOnWriteArrayList 是 List 接口的一个特殊实现，它通过写时复制的机制实现了线程安全性，特别适合在多线程环境下，读操作远多于写操作的场景。相比之下，ArrayList 和 LinkedList 各有优势：ArrayList 适合频繁的读取操作，而 LinkedList 更适合频繁插入和删除元素。

        在实际项目中，选择哪种 List 实现类取决于具体的应用场景和性能需求。如果你需要线程安全的 List 且写操作较少，CopyOnWriteArrayList 是一个理想的选择。


原文地址：https://blog.csdn.net/weixin_45075231/article/details/142766398

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024