3W 字详解 Java 集合

清疚 2023-09-28 16:48 145阅读 0赞

数据结构作为每一个开发者不可回避的问题，而 Java 对于不同的数据结构提供了非常成熟的实现，这一个又一个实现既是面试中的难点，也是工作中必不可少的工具，在此，笔者经历漫长的剖析，将其抽丝剥茧的呈现出来，在此仅作抛砖引玉，望得诸君高见，若君能有所获则在下甚是不亦乐乎，若有疑惑亦愿与诸君共求之！

本文一共 3.5 W字，25 张图，预计阅读 2h。可以收藏这篇文章，用的时候防止找不到，这可能是你能看到的最详细的一篇文章了。

学习更多JAVA知识与技巧，关注博主学习JAVA 课件，源码，安装包，还有最新大厂面试资料等等等

## *1.* 集合框架 ##

![dfc9396d5fc817269477229bb87a2fc7.png][]

Java整个集合框架如上图所示（这儿不包括Map，Map的结构将放在集合后边进行讲述），可见所有集合实现类的最顶层接口为Iterable和Collection接口，再向下Collection分为了三种不同的形式，分别是List，Queue和Set接口，然后就是对应的不同的实现方式。

### **1.1 顶层接口Iterable** ###

//支持lambda函数接口
    import java.util.function.Consumer;
    public interface Iterable<T> {
      //iterator()方法
        Iterator<T> iterator();
        default void forEach(Consumer<? super T> action) {
            Objects.requireNonNull(action);
            for (T t : this) {
                action.accept(t);
            }
        }
        default Spliterator<T> spliterator() {
            return Spliterators.spliteratorUnknownSize(iterator(), 0);
        }
    }

Iterable接口中只有iterator()一个接口方法，Iterator也是一个接口，其主要有如下两个方法hasNext()和next()方法。

package java.util;
    import java.util.function.Predicate;
    import java.util.stream.Stream;
    import java.util.stream.StreamSupport;
    public interface Collection<E> extends Iterable<E> {
        int size();
        boolean isEmpty();
        boolean contains(Object o);
        Iterator<E> iterator();
        Object[] toArray();
        boolean add(E e);
        boolean remove(Object o);
        boolean containsAll(Collection<?> c);
        boolean removeAll(Collection<?> c);
        default boolean removeIf(Predicate<? super E> filter) {
            Objects.requireNonNull(filter);
            boolean removed = false;
            final Iterator<E> each = iterator();
            while (each.hasNext()) {
                if (filter.test(each.next())) {
                    each.remove();
                    removed = true;
                }
            }
            return removed;
        }
        boolean retainAll(Collection<?> c);
        void clear();
        int hashCode();
        @Override
        default Spliterator<E> spliterator() {
            return Spliterators.spliterator(this, 0);
        }
        default Stream<E> stream() {
            return StreamSupport.stream(spliterator(), false);
        }
        default Stream<E> parallelStream() {
            return StreamSupport.stream(spliterator(), true);
        }
    }

可见Collection的主要接口方法有：

![8817395258419b5e1b11bb9ca4b176cf.png][]

***2.*** **List**

List表示一串有序的集合，和Collection接口含义不同的是List突出有序的含义。

### **2.1 List接口** ###

package java.util;
    
    import java.util.function.UnaryOperator;
    public interface List<E> extends Collection<E> {
        <T> T[] toArray(T[] a);
        boolean addAll(Collection<? extends E> c);
        boolean addAll(int index, Collection<? extends E> c);
        default void replaceAll(UnaryOperator<E> operator) {
            Objects.requireNonNull(operator);
            final ListIterator<E> li = this.listIterator();
            while (li.hasNext()) {
                li.set(operator.apply(li.next()));
            }
        }
        default void sort(Comparator<? super E> c) {
            Object[] a = this.toArray();
            Arrays.sort(a, (Comparator) c);
            ListIterator<E> i = this.listIterator();
            for (Object e : a) {
                i.next();
                i.set((E) e);
            }
        }
        boolean equals(Object o);
        E get(int index);
        E set(int index, E element);
        void add(int index, E element);
        int indexOf(Object o);
        int lastIndexOf(Object o);
        ListIterator<E> listIterator();
        List<E> subList(int fromIndex, int toIndex);
        @Override
        default Spliterator<E> spliterator() {
            return Spliterators.spliterator(this, Spliterator.ORDERED);
        }
    }

可见List其实比Collection多了添加方法add和addAll查找方法**get,indexOf,set**等方法，**并且支持index下标操作**。

**Collection 与 List 的区别？**

a. 从上边可以看出Collection和List最大的区别就是Collection是**无序**的，不支持索引操作，而List是有序的。Collection没有顺序的概念。

b. List中Iterator为ListIterator。

c. 由a推导List可以进行排序，所以List接口支持使用sort方法。

d. 二者的Spliterator操作方式不一样。

**为什么子类接口里重复申明父类接口呢?**

官方解释: 在子接口中重复声明父接口是为了方便看文档。比如在 java doc 文档里，在 List 接口里也能看到 Collecion 声明的相关接口。

### **2.2 List实现ArrayList** ###

### ArrayList是List接口最常用的一个实现类，支持List接口的一些列操作。 ###

#### **2.2.1 ArrayList继承关系** ####

![5ea08bdefef1936debab26eac7998730.png][]

#### **2.2.2 ArrayList组成** ####

private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
    //真正存放元素的数组
    transient Object[] elementData; // non-private to simplify nested class access
    private int size;

一定要记住ArrayList中的transient Object\[\] elementData，该elementData是真正存放元素的容器，可见ArrayList是基于数组实现的。

#### **2.2.3 ArrayList构造函数** ####

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

1. Object\[\] elementData 是ArrayList真正存放数据的数组。

2. ArrayList支持默认大小构造，和空构造，当空构造的时候存放数据的Object\[\] elementData是一个空数组\{\}。

#### **2.2.4 ArrayList中添加元素** ####

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

注意ArrayList中有一个modCount的属性，表示该实例修改的次数。（所有集合中都有modCount这样一个记录修改次数的属性），每次增改添加都会增加一次该ArrayList修改次数，而上边的add(E e)方法是将新元素添加到list尾部。

#### **2.2.4 ArrayList扩容** ####

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //DEFAULT_CAPACITY是10
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

可见当初始化的list是一个空ArrayList的时候，会直接扩容到DEFAULT\_CAPACITY，该值大小是一个默认值10。而当添加进ArrayList中的元素超过了数组能存放的最大值就会进行扩容。

注意到这一行代码

int newCapacity = oldCapacity + (oldCapacity >> 1);

采用右移运算，就是原来的一般，所以是扩容1.5倍。

**比如10的二进制是1010，右移后变成101就是5。**

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);
    }

#### **2.2.5 数组copy** ####

Java 是无法自己分配空间的，是底层C和C++的实现。以 C 为例，我们知道 C 中数组是一个指向首部的指针，比如我们 C 语言对数组进行分配内存。Java 就是通过 arraycopy 这个 native 方法实现的数组的复制。

public static native void arraycopy(Object src, int  srcPos,
                                            Object dest, int destPos,
                                            int length);

p = (int *)malloc(len*sizeof(int));

**这样的好处何在呢？**

Java里内存是由jvm管理的，而数组是分配的连续内存，而arrayList不一定是连续内存，当然jvm会帮我们做这样的事，jvm会有内部的优化，会在后续的例子中结合问题来说明。

#### **2.2.6 why?elementData用transient修饰？** ####

#### 1. transient的作用是该属性不参与序列化。 ####

#### 2. ArrayList继承了标示序列化的Serializable接口 ####

3. 对arrayList序列化的过程中进行了读写安全控制。

**是如何实现序列化安全的呢?**

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 size as capacity for behavioural compatibility with clone()
        s.writeInt(size);
    
        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }
    
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
    
    /**
     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
     * deserialize it).
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;
    
        // Read in size, and any hidden stuff
        s.defaultReadObject();
    
        // Read in capacity
        s.readInt(); // ignored
    
        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            int capacity = calculateCapacity(elementData, size);
            SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
            ensureCapacityInternal(size);
    
            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

在序列化方法writeObject()方法中可以看到，先用默认写方法，然后将size写出，最后遍历写出elementData，因为该变量是transient修饰的，所有进行手动写出，这样它也会被序列化了。那是不是多此一举呢？

protected transient int modCount = 0;

当然不是，其中有一个关键的modCount, 该变量是记录list修改的次数的，当写入完之后如果发现修改次数和开始序列化前不一致就会抛出异常，序列化失败。这样就保证了序列化过程中是未经修改的数据,保证了序列化安全。（java集合中都是这样实现）

### **2.3 LinkedList** ###

众所周知LinkedList是一种链表结构，那么Java里LinkedList是如何实现的呢？

#### **2.3.1 LinkedList继承关系** ####

![6c92bf99c1f6d05862551f21a53e1381.png][]

可见LinkedList既是List接口的实现也是Queue的实现（Deque），故其和ArrayList相比LinkedList支持的功能更多，其可视作队列来使用，当然下文中不强调其队列的实现。

#### **2.3.2 LinkedList的结构** ####

####  ####

transient Node<E> first;
    
    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     * (last.next == null && last.item != null)
     */
    transient Node<E> last;

LinkedList由一个头节点和一个尾节点组成，分别指向链表的头部和尾部。

LinkedList中Node源码如下，由当前值item，和指向上一个节点prev和指向下个节点next的指针组成。并且只含有一个构造方法，按照(prev, item, next)这样的参数顺序构造。

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
    
        Node(Node<E> prev, E element, Node<E> next) {
            this.it

[dfc9396d5fc817269477229bb87a2fc7.png]: https://img-blog.csdnimg.cn/img_convert/dfc9396d5fc817269477229bb87a2fc7.png
[8817395258419b5e1b11bb9ca4b176cf.png]: https://img-blog.csdnimg.cn/img_convert/8817395258419b5e1b11bb9ca4b176cf.png
[5ea08bdefef1936debab26eac7998730.png]: https://img-blog.csdnimg.cn/img_convert/5ea08bdefef1936debab26eac7998730.png
[6c92bf99c1f6d05862551f21a53e1381.png]: https://img-blog.csdnimg.cn/img_convert/6c92bf99c1f6d05862551f21a53e1381.png