本次的笔记主要记录了集合的底层实现原理的基本概念。先总结了List集合中的ArrayList集合和LinkedList集合的底层数据结构实现和源码分析。

一、集合的分类

二、集合的基本概念

1、Collection单列集合概述

（1）是单列集合的顶层接口，他表示一组对象，这些对象也成为Collection的元素。

（2）JDK不提供此接口的任何直接实现，他提供更具体的子接口（如set和list）实现。

2、Map双列集合概述

（1）将键映射到值的对象，不包含重复的键，每个键可以映射到最多一个值。

三、集合底层详解

1、ArrayList集合详解

1.1 基本概念

ArrayList是List接口的可变数组非同步实现，底层使用数组保存所有元素。其操作基本上是对数组的操作。

1	private transient Object[] elementData;

该集合是可变长度的数组，数组扩容时，会将老数组中的元素拷贝一份到新数组中！每次数组扩容的大小是原容量的1.5倍。

private void grow(int minCapacity) {
    int oldCapacity = elementData.length; // 旧容量
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量为旧容量的1.5倍
    if (newCapacity - minCapacity < 0) // 新容量小于参数指定容量，修改新容量
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 新容量大于最大容量
        newCapacity = hugeCapacity(minCapacity); // 指定新容量
    // 拷贝扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

1.2 源码分析

1.2.1 类的继承关系

ArrayList继承AbstractList抽象父类。实现了List接口。RandomAccess（可随机访问）、Cloneable（可拷贝）、Serializable （可序列化）。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 版本号
    private static final long serialVersionUID = 8683452581122892189L;
    // 缺省容量
    private static final int DEFAULT_CAPACITY = 10;
    // 空对象数组（核心属性，被标记为transient，序列化的时候此字段不会被序列化）
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 缺省空对象数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 元素数组
    transient Object[] elementData;
    // 实际元素大小，默认为0
    private int size;
    // 最大数组容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

1.2.2 ArrayList类的构造器

1.2.2.1 ArrayList（int）型构造函数

public ArrayList(int initialCapacity) {
       if (initialCapacity > 0) { // 初始容量大于0
           this.elementData = new Object[initialCapacity]; // 初始化元素数组
       } else if (initialCapacity == 0) { // 初始容量为0
           this.elementData = EMPTY_ELEMENTDATA; // 为空对象数组
       } else { // 初始容量小于0，抛出异常
           throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
       }
   }

1.2.2.2 ArrayList()型构造函数

public ArrayList() { 
       // 无参构造函数，设置元素数组为空 
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }

1.2.2.3 ArrayList(Collection<? extends E>)型构造函数

public ArrayList(Collection<? extends E> c) { // 集合参数构造函数
       elementData = c.toArray(); // 转化为数组
       if ((size = elementData.length) != 0) { // 参数为非空集合
           if (elementData.getClass() != Object[].class) // 是否成功转化为Object类型数组
               elementData = Arrays.copyOf(elementData, size, Object[].class); // 不为Object数组的话就进行复制
       } else { // 集合大小为空，则设置元素数组为空
           this.elementData = EMPTY_ELEMENTDATA;
       }
   }

1.2.3 常用核心方法分析

1.2.3.1 add函数：向数组中添加元素

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

ensureCapacityInternal此函数可以理解为确保elementData数组有合适的大小。

ensureCapacityInternal方法的实现方法如下。

private void ensureCapacityInternal(int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 判断元素数组是否为空数组
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 取较大值
       }
       
       ensureExplicitCapacity(minCapacity);
   }

ensureExplicitCapacity函数也是为了确保elemenData数组有合适的大小。ensureExplicitCapacity的具体函数如下

private void ensureExplicitCapacity(int minCapacity) {
       // 结构性修改加1
       modCount++;
       if (minCapacity - elementData.length > 0)
           grow(minCapacity);
   }

最后又调用了grow（）方法，该方法才是真正扩容数组的方法，正常情况下会扩容1.5倍。特殊情况下（新的数组大小已经达到最大值）则只取最大值。

1.2.3.2 set函数：通过下标索引设置相应位置处的值

public E set(int index, E element) {
    // 检验索引是否合法
    rangeCheck(index);
    // 旧值
    E oldValue = elementData(index);
    // 赋新值
    elementData[index] = element;
    // 返回旧值
    return oldValue;
}

1.2.3.3 indexOf函数：从首开始查找数组里面是否存在指定元素

// 从首开始查找数组里面是否存在指定元素
    public int indexOf(Object o) {
        if (o == null) { // 查找的元素为空
            for (int i = 0; i < size; i++) // 遍历数组，找到第一个为空的元素，返回下标
                if (elementData[i]==null)
                    return i;
        } else { // 查找的元素不为空
            for (int i = 0; i < size; i++) // 遍历数组，找到第一个和指定元素相等的元素，返回下标
                if (o.equals(elementData[i]))
                    return i;
        } 
        // 没有找到，返回空
        return -1;
    }

从头开始查找与指定元素相等的元素，注意，是可以查找null元素的，意味着ArrayList中可以存放null元素的。与此函数对应的lastIndexOf，表示从尾部开始查找。

1.2.3.4 get函数：通过下标索引获取相应位置处的值

public E get(int index) {
    // 检验索引是否合法
    rangeCheck(index);

    return elementData(index);
}

get函数会检查索引值是否合法（只检查是否大于size，而没有检查是否小于0），值得注意的是，在get函数中存在element函数，element函数用于返回具体的元素，具体函数如下　

1
2
3

E elementData(int index) {
    return (E) elementData[index];
}

返回的值都经过了向下转型（Object -> E），这些是对我们应用程序屏蔽的小细节。

1.2.3.5 remove函数：通过下表索引删除数组中相应位置的值

public E remove(int index) {
    // 检查索引是否合法
    rangeCheck(index);
    
    modCount++;
    E oldValue = elementData(index);
    // 需要移动的元素的个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 赋值为空，有利于进行GC
    elementData[--size] = null; 
    // 返回旧值
    return oldValue;
}

1.3 ArrayList总结

ArrayList由于底层是数组实现的，所以相较于LinkedList，ArrayList集合查询、修改速度快，但是在指定位置删除和添加元素时由于需要移动指定位置之后的元素所以速度相比较慢。

2、LinkedList集合详解

2.1 基本概念

LinkedList底层的数据结构是双向循环链表，头结点不存放元素

2.2 源码分析

2.2.1 类的继承关系

1 2	public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的。

2.2.2 内部类（结点类）

private static class Node<E> {
    E item; // 数据域
    Node<E> next; // 后继
    Node<E> prev; // 前驱
    
    // 构造函数，赋值前驱后继
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

用于构建链表的组成对象（结点）

2.2.3 LinkedList的属性

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 实际元素个数
    transient int size = 0;
    // 头结点
    transient Node<E> first;
    // 尾结点
    transient Node<E> last;
}

2.2.4 LinkedList的构造器

2.2.4.1 LinkedList()型构造函数

1 2	public LinkedList() { }

创建一个空的头结点。

2.2.4.2 LinkedList(Collection<? extends E>)型构造函数

public LinkedList(Collection<? extends E> c) {
    // 调用无参构造函数
    this();
    // 添加集合中所有的元素
    addAll(c);
}

这个构造方法的参数是一个集合，可以将这个集合中的所有元素信息存入双向链表。

2.2.5 常用核心方法分析

2.2.5.1 add函数：向链表的末尾添加进一个结点对象

public boolean add(E e) {
    // 添加到末尾
    linkLast(e);
    return true;
}

该方法添加到末尾的具体逻辑是由linkLast函数完成，linkLast方法的具体实现如下：

void linkLast(E e) {
    // 保存尾结点，l为final类型，不可更改
    final Node<E> l = last;
    // 新生成结点的前驱为l,后继为null
    final Node<E> newNode = new Node<>(l, e, null);
    // 重新赋值尾结点
    last = newNode;    
    if (l == null) // 尾结点为空
        first = newNode; // 给头节点赋值
    else // 尾结点不为空
        l.next = newNode; // 尾结点的后继为新生成的结点（尾结点）
    // 大小加1    
    size++;
    // 结构性修改加1
    modCount++;
}

2.2.5.2 addAll函数

addAll有两个重载函数，addAll(Collection<? extends E>)型和addAll(int, Collection<? extends E>)型，我们平时习惯调用的addAll(Collection<? extends E>)型会转化为addAll(int, Collection<? extends E>)型，所以着重分析此函数即可。

// 添加一个集合
    public boolean addAll(int index, Collection<? extends E> c) {
        // 检查插入的的位置是否合法
        checkPositionIndex(index);
        // 将集合转化为数组
        Object[] a = c.toArray();
        // 保存集合大小
        int numNew = a.length;
        if (numNew == 0) // 集合为空，直接返回
            return false;

        Node<E> pred, succ; // 前驱，后继
        if (index == size) { // 如果插入位置为链表末尾，则后继为null，前驱为尾结点
            succ = null;
            pred = last;
        } else { // 插入位置为其他某个位置
            succ = node(index); // 寻找到该结点
            pred = succ.prev; // 保存该结点的前驱
        }

        for (Object o : a) { // 遍历数组
            @SuppressWarnings("unchecked") E e = (E) o; // 向下转型
            // 生成新结点
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null) // 表示在第一个元素之前插入(索引为0的结点)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        if (succ == null) { // 表示在最后一个元素之后插入
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }
        // 修改实际元素个数
        size += numNew;
        // 结构性修改加1
        modCount++;
        return true;
    }

参数中的index表示在索引下标为index的结点（实际上是第index + 1个结点）的前面插入。在addAll函数中，addAll函数中还会调用到node函数，get函数也会调用到node函数，此函数是根据索引下标找到该结点并返回，具体代码如下

Node<E> node(int index) {
        // 判断插入的位置在链表前半段或者是后半段
        if (index < (size >> 1)) { // 插入位置在前半段
            Node<E> x = first; 
            for (int i = 0; i < index; i++) // 从头结点开始正向遍历
                x = x.next;
            return x; // 返回该结点
        } else { // 插入位置在后半段
            Node<E> x = last; 
            for (int i = size - 1; i > index; i--) // 从尾结点开始反向遍历
                x = x.prev;
            return x; // 返回该结点
        }
    }

2.2.5.3 unlink函数

在调用remove移除结点时，会调用到unlink函数（将指定的结点从链表中断开，不再累赘），unlink函数具体如下：　

E unlink(Node<E> x) {
       // 保存结点的元素
       final E element = x.item;
       // 保存x的后继
       final Node<E> next = x.next;
       // 保存x的前驱
       final Node<E> prev = x.prev;
       
       if (prev == null) { // 前驱为空，表示删除的结点为头结点
           first = next; // 重新赋值头结点
       } else { // 删除的结点不为头结点
           prev.next = next; // 赋值前驱结点的后继
           x.prev = null; // 结点的前驱为空，切断结点的前驱指针
       }

       if (next == null) { // 后继为空，表示删除的结点为尾结点
           last = prev; // 重新赋值尾结点
       } else { // 删除的结点不为尾结点
           next.prev = prev; // 赋值后继结点的前驱
           x.next = null; // 结点的后继为空，切断结点的后继指针
       }

       x.item = null; // 结点元素赋值为空
       // 减少元素实际个数
       size--; 
       // 结构性修改加1
       modCount++;
       // 返回结点的旧元素
       return element;
   }

2.3 LinkedList总结

LinkedList的底层数据结构是循环双向链表，但由于实现了多个接口所以当需要使用栈、队列等操作时，可以考虑该结构。

ArrayList参考文献：

[https://www.cnblogs.com/leesf456/p/5308358.html]:

LinkedList参考文献：

[[](https://www.cnblogs.com/leesf456/p/5308843.html)]:
[[](https://www.cnblogs.com/ITtangtang/p/3948610.html#a4)]:

集合底层原理（ArrayList和LinkedList）