Java 常用数据结构的底层实现

发表于 2024-04-24 更新于 2024-07-30 分类于 Java基础

ArrayList、LinkedList、HashMap、ConcurrentHashMap 的底层源码剖析

ArrayList

ArrayList 的底层是数组队列，相当于动态数组。

与数组相比，它的容量能动态增长。
与 Vector 相比，它的底层使用 Object[] 存储，适用于频繁的查找工作，线程不安全

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
    void add(int, E);
    E set(int, E);
    E get(int);
    E remove(int);
}

List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
RandomAccess ：这是一个标志接口，表明实现这个接口的 List 集合是支持 快速随机访问 ,可以通过元素的序号快速获取元素对象list.get(i)。
Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。
Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。

扩容机制

初始化时默认空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

添加元素时，先判断需要扩容的最小扩容量大小（DEFAULT_CAPACITY 默认是 10）

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

如果需要扩容，就会进入扩容方法 grow()，扩容效果是小于等于 1.5 倍的（因为 int 取整）

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

如果扩容长度超过定义的数组的最大长度 MAX_ARRAY_SIZE = Integer.MAX_VALUE-8，就会触发最大值限制，防止 size 溢出

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

将旧数组移动到新数组

public static int[] copyOf(int[] original, int newLength) {
    int[] copy = new int[newLength];
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

手动扩容，可以在需要插入大量数据前手动扩容

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

与 LinkedList 的异同

都不保证线程安全；
ArrayList 底层使用的是 Object[] 数组；LinkedList 底层使用的是 Node+双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环）
插入和删除是否受元素位置的影响：
- ArrayList 将指定的元素追加到此列表的末尾，时间复杂度 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)），时间复杂度 O(n)。
- LinkedList 头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、 removeLast()），时间复杂度 O(1)；指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o),remove(int index)），时间复杂度为 O(n) 。
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList（实现了 RandomAccess 接口）支持。
内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素 Node 都需要消耗比 ArrayList 更多的空间

LinkedList

需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，而且性能会更好。头尾插入或者删除元素的时候时间复杂度近似 O(1)，其他情况增删元素的平均时间复杂度都是 O(n) 。

public class LinkedList<E> extends AbstractSequentialList<E> 
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    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;
        }
    }
}

List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
Deque ：继承自 Queue 接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构。

常用方法

实现 List 接口
- get、set
实现 Collection 接口
- 判断是否存在：contains
实现 Queue 接口（通过 Deque 接口）
- 报错：add、remove、element
- 不报错：offer、poll、peek
实现 Deque 接口
- addFirst [push]、addLast [add]：无返回，容量超出限制会报错
- offerFirst、offerLast [offer]：返回 Boolean 表示是否加入成功
- removeFirst [remove\pop]、removeLast：队列为空报错
- pollFirst [poll]、pollLast：队列为空返回 null
- getFirst [element]、getLast：队列为空报错
- peekFirst [peek]、peekLast：队列为空返回 null
  - 【注意】队列头部为 null 和队列为空时，都会返回 null
- removeFirstOccurrence [remove]、removeLastOccurrence
- push、pop、peek：作为栈

HashMap

JDK1.8 之前 HashMap 采用“拉链法”处理冲突，由数组+链表组成； JDK1.8 以后，若Table长度大于 64，会将链表转化为红黑树。

key 和 value 可以为 null，但 null 作为 key 只能有一个，而 null 作为 value 可以有多个
非线程安全的

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认的负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当桶上的结点数大于等于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8;
    // 当桶上的结点数小于等于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的 table 的最小容量
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储桶（bin）的数组，永远是 2 的幂次倍
    transient Node<k,v>[] table;
    // 一个包含了映射中所有键值对的集合视图
    // 先遍历数组 bin，再通过 Entry.next 遍历每个 bin
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数，注意这个不等于数组的长度
    transient int size;
    // 阈值=容量*负载因子，当实际大小超过阈值时，会进行扩容
    int threshold;
    // 负载因子
    final float loadFactor;
    
    static class Node<K,V> implements Map.Entry<K,V>{
        final int hash;
        final K key;
        V value;
        // 链表的下一个元素
        Node<K,V> next;
    }
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>{
        Entry<K,V> before, after;
        TreeNode<K,V> parent;  // 红黑树链
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // 需要在下次删除时解除链接
        boolean red;
    }
}

entrySet 通过Node的next属性遍历元素，keySet()、values()基于entrySet实现，用于遍历访问所有 Node 元素，还支持元素的删除操作【不确定，entrySet不存储数据，只是数据对外的操作接口】。
TreeNode 继承了 LinkedHashMap.Entry ，有指向前后节点的指针

jdk 1.8 Key 计算 hash 值的方法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

扩容机制

何时触发 resize() 扩容

要插入数据前，发现table 中的 bin 为空
要插入数据后，发现HashMap的 size 超过 threshold
table 长度小于 MIN_TREEIFY_CAPACITY时，某 Node 上的链长度超过 TREEIFY_THRESHOLD

resize() 扩容，会将 table 中的节点数量 << 1，并重新 hash 映射所有节点（因为 table 变大了，每个节点对应的 bin 下标发生了变化 newTab[e.hash & (newCap - 1)] = e，newCap为 table 的新大小）

链表何时变成红黑树？

该 bin 上的链长度binCount 大于等于 TREEIFY_THRESHOLD 且 table 中 bin 数量大于等于 MIN_TREEIFY_CAPACITY

如果链表转红黑树的时候，又有数据要插入，会发生什么？

线程不安全。在树结构替换链表最终阶段会校验树结构，在此过程中的插入会使该树结构不满足红黑树和双链表的特性，导致报异常 assert checkInvariants(root);

ConcurrentHashMap

Java7 中 ConcurrentHashMap 使用的是分段锁，每一个 Segment 上同时只有一个线程可以操作，结构上时 Segment 数组 + HashEntry 数组 + 链表。Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，Segment继承ReentrantLock实现分段锁。

Java8 中的 ConcurrentHashMap 通过 Synchronized 锁加 CAS 保证多线程安全，结构上是 Node 数组 + 链表 / 红黑树。

如果链表转红黑树，又有数据要插入，会发生什么。

treeifyBin 通过 synchronized 把 bin 加锁，后续数据插入会因为无法竞争到资源而阻塞
链表开始转红黑树前，会将 Node 头节点置为 ForwardingNode，ForwardingNode 的 hash 是 Moved 表示正在转换为红黑树，此时会自旋等待转换完成后插入（大概是这样的）

如果数组扩容，又有数据要插入，会发生什么。

扩容前，会将 Node 头节点置为 ForwardingNode，ForwardingNode 的 hash 是 Moved 表示正在扩容。
扩容时，插入数据的线程若发现 hash 值为负，会去协助扩容，扩容完成后再插入数据。

什么时候触发扩容？

在调用 addCount 方法增加集合元素计数后发现当前集合元素个数到达扩容阈值时就会触发扩容
扩容状态下其他线程对集合进行插入、修改、删除、合并、compute 等操作时遇到 ForwardingNode 节点会触发扩容（帮助扩容）
putAll 批量插入或者插入节点后发现存在链表长度达到 8 个或以上，但数组长度为 64 以下时会触发扩容。

同 HashMap：桶上链表长度达到 8 个或者以上，并且数组长度为 64 以下时只会触发扩容而不会将链表转为红黑树

LinkedHashMap

LinkedHashMap 内部维护了一个双向链表，确保其迭代顺序是和插入顺序或访问顺序是一致的，通过重写 get、newNode、afterNodeAccess、afterNodeInsertion、afterNodeRemoval 等方法实现，最近插入或访问的节点位于链表尾部。

可以按照插入顺序遍历 entry（accessOrder=false）

也可以按照访问顺序遍历 entry（accessOrder=true），即 LRU

可用于实现 LRU，即迭代顺序==访问顺序

每次修改都将元素删除后重新插入
将 accessOrder 设置为 true 并重写 removeEldestEntry 方法当链表大小超过容量时返回 true

CopyOnWriteList

并发安全的 List，针对读多写少的场景，类比读写锁的思想，实现 读读不互斥、读写不互斥、写写互斥 的写时复制 Copy-On-Write 策略。此外还有 Collections.synchronizedList ，可以将任何List包装成一个线程安全的List

add 方法内部用到了 ReentrantLock 加锁，避免了多线程写的时候会复制出多个副本，导致并发问题

写时复制的缺点

写操作资源占用多，复制数据时占用内存
数据一致性问题，修改后需要等到赋值给原数组才能访问到修改

写多读少的场景下，应该用什么数据结构实现并发数组？

分段读写锁 ReadWriteLock（由于 Arrays.copyOf() 是操作系统实现，数据量少的话依然可用写时复制）

ArrayList

扩容机制

与 LinkedList 的异同

LinkedList

常用方法

HashMap

扩容机制

ConcurrentHashMap

LinkedHashMap

CopyOnWriteList

PriorityQueue