正文

揭秘Java集合框架源码：全面解读ArrayList、LinkedList等核心类原理与优化技巧

/0 浏览量
0702

在Java编程语言中，集合框架是处理数据集合的标准方式，它提供了灵活和强大的数据结构。本文将深入探讨Java集合框架的源码，特别是ArrayList和LinkedList这两个核心类的原理，并分享一些优化技巧。

ArrayList原理与优化

ArrayList概述

ArrayList是Java集合框架中一个可调整大小的数组实现。它实现了List接口，允许使用整数索引来访问元素。

ArrayList源码解析

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8683452581122892189L;

    private transient Object[] elementData;
    private int size;

    public ArrayList(int initialCapacity) {
        if (initialCapacity >= 0) {
            this.elementData = new Object[initialCapacity];
        } else {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
    }

    public ArrayList() {
        this(10);
    }

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class) {
                elementData = Arrays.copyOf(elementData, size, Object[].class);
            }
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    public E get(int index) {
        Object[] elementData = this.elementData;
        return (E) elementData[index];
    }

    public E set(int index, E element) {
        Object[] elementData = this.elementData;
        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

    public E remove(int index) {
        rangeCheck(index);
        modCount++;
        E oldValue = (E) elementData[index];

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

        return oldValue;
    }

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureCapacityInternal(int minCapacity) {
        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;
        int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        }
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        }
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }
}

ArrayList优化技巧

  1. 初始化容量：合理初始化ArrayList的容量可以减少扩容的次数，提高性能。
  2. 避免频繁的添加和删除操作：ArrayList在添加和删除元素时，如果操作在中间位置，会导致大量的元素移动，影响性能。
  3. 使用迭代器：当需要遍历ArrayList时，使用迭代器而不是for循环，可以避免在遍历过程中修改集合，导致ConcurrentModificationException。

LinkedList原理与优化

LinkedList概述

LinkedList是Java集合框架中一个双向链表实现。它实现了List接口，但不支持随机访问。

LinkedList源码解析

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8683452581122892189L;

    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(E element, Node<E> prev, Node<E> next) {
            item = element;
            this.prev = prev;
            this.next = next;
        }
    }

    public LinkedList() {
    }

    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    private void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(e, l, null);
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null) {
            throw new NoSuchElementException();
        }
        final E item = f.item;
        f.item = null;
        first = f.next;
        if (first == null) {
            last = null;
        } else {
            first.prev = null;
        }
        size--;
        modCount++;
        return item;
    }

    public E removeLast() {
        final Node<E> l = last;
        if (l == null) {
            throw new NoSuchElementException();
        }
        final E item = l.item;
        l.item = null;
        last = l.prev;
        if (last == null) {
            first = null;
        } else {
            last.next = null;
        }
        size--;
        modCount++;
        return item;
    }
}

LinkedList优化技巧

  1. 避免频繁的随机访问：LinkedList不支持随机访问，因此如果需要频繁访问中间元素，LinkedList的性能会受到影响。
  2. 使用迭代器：与ArrayList类似，使用迭代器可以避免在遍历过程中修改集合。
  3. 合理使用subList方法：LinkedList的subList方法返回的是原始链表的视图，因此对subList的修改会反映到原始链表上。

总结

通过本文的解析，我们可以了解到ArrayList和LinkedList的工作原理和优化技巧。在实际开发中，根据具体需求选择合适的集合类，可以有效地提高程序的性能和可维护性。

-- 展开阅读全文 --