Java常见源码解析

环境搭建

• 克隆jdk项目：git clone https://github.com/openjdk/jdk.git / https://gitee.com/zhijiantianya/jdk
• 编译

数组ArrayList

ArrayList ，基于 [] 数组实现的，支持自动扩容的动态数组。

实现了 4 个接口，分别是：

• java.util.List 接口，提供数组的添加、删除、修改、迭代遍历等操作。
• java.util.RandomAccess 接口，表示 ArrayList 支持快速的随机访问。
• java.io.Serializable 接口，表示 ArrayList 支持序列化的功能。
• java.lang.Cloneable 接口，表示 ArrayList 支持克隆。

继承了 java.util.AbstractList 抽象类，而 AbstractList 提供了 List 接口的骨架实现，大幅度的减少了实现迭代遍历相关操作的代码。可能这样表述有点抽象，点到 java.util.AbstractList 抽象类中看看，例如说 #iterator()、#indexOf(Object o) 等方法。

😈 不过实际上，在下面中我们会看到，ArrayList 大量重写了 AbstractList 提供的方法实现。所以，AbstractList 对于 ArrayList 意义不大，更多的是 AbstractList 其它子类享受了这个福利。

ArrayList 的属性

• elementData 属性：元素数组。
• size 属性：数组大小。注意，size 代表的是 ArrayList 已使用 elementData 的元素的数量，对于开发者看到的 #size() 也是该大小。并且，当我们添加新的元素时，恰好其就是元素添加到 elementData 的位置（下标）。当然，我们知道 ArrayList 真正的大小是 elementData 的大小。

// ArrayList.java

/**
 * 元素数组。
 *
 * 当添加新的元素时，如果该数组不够，会创建新数组，并将原数组的元素拷贝到新数组。之后，将该变量指向新数组。
 */
transient Object[] elementData; // non-private to simplify nested class access 不使用 private 修复，方便内嵌类的访问。

/**
 * 已使用的数组大小
 *
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

构造方法

① #ArrayList(int initialCapacity) ，根据传入的初始化容量，创建 ArrayList 数组。

② #ArrayList(Collection<? extends E> c) 使用传入的 c 集合，作为 ArrayList 的 elementData

③ #ArrayList() 无参数构造方法

// ArrayList.java

/**
 * 共享的空数组对象。
 *
 * 在 {@link #ArrayList(int)} 或 {@link #ArrayList(Collection)} 构造方法中，
 * 如果传入的初始化大小或者集合大小为 0 时，将 {@link #elementData} 指向它。
 *
 * Shared empty array instance used for empty instances.
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

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

// ArrayList.java

public ArrayList(Collection<? extends E> c) {
    // 将 c 转换成 Object 数组
    elementData = c.toArray();
    // 如果数组大小大于 0
    if ((size = elementData.length) != 0) {
        // defend against c.toArray (incorrectly) not returning Object[]
        // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
        // <X> 如果集合元素不是 Object[] 类型，则会创建新的 Object[] 数组，并将 elementData 赋值到其中，最后赋值给 elementData 。
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    // 如果数组大小等于 0 ，则使用 EMPTY_ELEMENTDATA 。
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

// ArrayList.java

/**
 * 默认初始化容量
 *
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 共享的空数组对象，用于 {@link #ArrayList()} 构造方法。
 *
 * 通过使用该静态变量，和 {@link #EMPTY_ELEMENTDATA} 区分开来，在第一次添加元素时。
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

• 在我们学习 ArrayList 的时候，一直被灌输了一个概念，在未设置初始化容量时，ArrayList 默认大小为 10 。但是此处，我们可以看到初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这个空数组。这是为什么呢？ArrayList 考虑到节省内存，一些使用场景下仅仅是创建了 ArrayList 对象，实际并未使用。所以，ArrayList 优化成初始化是个空数组，在首次添加元素时，才真正初始化为容量为 10 的数组。
• 那么为什么单独声明了 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空数组，而不直接使用 EMPTY_ELEMENTDATA 呢？在下文中，我们会看到 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 首次扩容为 10 ，而 EMPTY_ELEMENTDATA 按照 1.5 倍扩容从 0 开始而不是 10 。😈 两者的起点不同

添加单个元素

// ArrayList.java

@Override
public boolean add(E e) {
    // <1> 增加数组修改次数
    modCount++;
    // 添加元素
    add(e, elementData, size);
    // 返回添加成功
    return true;
}

private void add(E e, Object[] elementData, int s) {
    // <2> 如果容量不够，进行扩容
    if (s == elementData.length)
        elementData = grow();
    // <3> 设置到末尾
    elementData[s] = e;
    // <4> 数量大小加一
    size = s + 1;
}

数组扩容

#grow() 方法，扩容数组，并返回它。整个的扩容过程，首先创建一个新的更大的数组，一般是 1.5 倍大小，然后将原数组复制到新数组中，最后返回新数组。代码如下：

// ArrayList.java

private Object[] grow() {
    // <1>
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // <2> 如果原容量大于 0 ，或者数组不是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，计算新的数组大小，并创建扩容
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    // <3> 如果是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 数组，直接创建新的数组即可。
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

链表LinkedList

LinkedList ，基于节点实现的双向链表的 List ，每个节点都指向前一个和后一个节点从而形成链表。

LinkedList 实现的接口

• java.util.List 接口
• java.io.Serializable 接口
• java.lang.Cloneable 接口
• java.util.Deque 接口 提供双端队列的功能，LinkedList 支持快速的在头尾添加元素和读取元素

属性

• 通过 Node 节点指向前后节点，从而形成双向链表。
• first 和 last 属性：链表的头尾指针
• size 属性：链表的节点数量。通过它进行计数，避免每次需要 List 大小时，需要从头到尾的遍历。

// LinkedList.java

/**
 * 链表大小
 */
transient int size = 0;

/**
 * 头节点
 *
 * Pointer to first node.
 */
transient Node<E> first;

/**
 * 尾节点
 *
 * Pointer to last node.
 */
transient Node<E> last;

/**
 * 节点
 *
 * @param <E> 元素泛型
 */
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;
    }

}

构造方法

LinkedList()

public LinkedList(Collection<? extends E> c)

添加单个元素

// LinkedList.java

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

void linkLast(E e) {
    // <1> 记录原 last 节点
    final Node<E> l = last;
    // <2> 创建新节点
    // 第一个参数表示，newNode 的前一个节点为 l 。
    // 第二个参数表示，e 为元素。
    // 第三个参数表示，newNode 的后一个节点为 null 。
    final Node<E> newNode = new Node<>(l, e, null);
    // <3> last 指向新节点
    last = newNode;
    // <4.1> 如果原 last 为 null ，说明 first 也为空，则 first 也指向新节点
    if (l == null)
        first = newNode;
    // <4.2> 如果原 last 非 null ，说明 first 也非空，则原 last 的 next 指向新节点。
    else
        l.next = newNode;
    // <5> 增加链表大小
    size++;
    // <6> 增加数组修改次数
    modCount++;
}

链表扩容

LinkedList 不存在扩容的需求，因为通过 Node 的前后指向即可。

哈希表HashMap

HashMap ，是一种散列表，用于存储 key-value 键值对的数据结构，一般翻译为“哈希表”，提供平均时间复杂度为 O(1) 的、基于 key 级别的 get/put 等操作。

HashMap 实现的接口、继承的抽象类

• 实现 java.util.Map 接口，并继承 java.util.AbstractMap 抽像类。
• 实现 java.io.Serializable 接口。
• 实现 java.lang.Cloneable 接口。

HashMap 的实现原理

HashMap 所提供的 O(1) 是平均时间复杂度，大多数情况下保证 O(1) 。其实极端情况下，有可能退化为 O(N) 的时间复杂度

HashMap 其实是在数组的基础上实现的

key 并不是一个整数，可以放入指向数组中的指定下标

通过 hash(key) 的过程，我们可以将 key 成功的转成一个整数。但是，hash(key) 可能会超过数组的容量，所以我们需要 hash(key) % size 作为下标，放入数组的对应位置。

• 1、hash(key) 计算出来的哈希值，并不能保证唯一；
• 2、hash(key) % size 的操作后，即使不同的哈希值，也可能变成相同的结果。

这样，就导致我们常说的“哈希冲突”。那么怎么解决呢？方法有两种：

1、开放寻址法

2、链表法

在 Java HashMap 中，采用了链表法

通过将数组的每个元素对应一个链表，我们将相同的 hash(key) % size 放到对应下标的链表中即可。

如果我们放入的 N 个 key-value 键值对到 HashMap 的情况：

• 1、每个 key 经过 hash(key) % size 对应唯一下标，则 get 时间复杂度是 O(1) 。
• 2、k 个 key 经过 hash(key) % size 对应唯一下标，那么在 get 这 k 个 key 的时间复杂度是 O(k) 。
• 3、在情况 2 的极端情况下，k 恰好等于 N ，那么是不是就出现我们在上面说的 O(N) 的时间复杂度的情况。

为了解决最差 O(N) 的时间复杂度的情况，我们可以将数组的每个元素对应成其它数据结构，例如说：1）红黑树；2）跳表。它们两者的时间复杂度是 O(logN) ，这样 O(N) 就可以缓解成 O(logN) 的时间复杂度。

• 在 JDK7 的版本中，HashMap 采用“数组 + 链表”的形式实现。
• 在 JDK8 开始的版本，HashMap 采用“数组 + 链表 + 红黑树”的形式实现，在空间和时间复杂度中做取舍。

我们是希望 HashMap 尽可能能够达到 O(1) 的时间复杂度，链表法只是我们解决哈希冲突的无奈之举。

在 HashMap 的 key-value 键值对数量达到阀值后，就会进行扩容。

假设 HashMap 的数组容量为 capacity ，key-value 键值对数量为 size ，负载因子为 loadFactor 。那么，当 capacity / size > loadFactor 时，也就是使用的数组大小到达 loadFactor 比例时，我们就需要进行扩容。

属性

/**
 * 底层存储的数组
 */
transient Node<K,V>[] table;

/**
 * 调用 `#entrySet()` 方法后的缓存
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * key-value 的键值对数量
 */
transient int size;

/**
 * HashMap 的修改次数
 */
transient int modCount;

/**
 * 阀值，当 {@link #size} 超过 {@link #threshold} 时，会进行扩容
 */
int threshold;

/**
 * 扩容因子
 */
final float loadFactor;

// HashMap.java#Node.java

static class Node<K,V> implements Map.Entry<K,V> {

    /**
     * 哈希值
     */
    final int hash;
    /**
     * KEY 键
     */
    final K key;
    /**
     * VALUE 值
     */
    V value;
    /**
     * 下一个节点
     */
    Node<K,V> next;

    // ... 省略实现方法

}

• hash + key + value 属性，定义了 Node 节点的 3 个重要属性。
• next 属性，指向下一个节点。通过它可以实现 table 数组的每一个位置可以形成链表。
• TreeNode ，定义在 HashMap 中，红黑树节点。通过它可以实现 table 数组的每一个位置可以形成红黑树。

构造方法

① #HashMap() 创建一个初始化容量为 16 的 HashMap 对象

• 初始化 loadFactor 为 DEFAULT_LOAD_FACTOR = 0.75 。

• 在该构造方法上，我们并没有看到 table 数组的初始化。它是延迟初始化，在我们开始往 HashMap 中添加 key-value 键值对时，在 #resize() 方法中才真正初始化。

② #HashMap(int initialCapacity) 初始化容量为 initialCapacity 的 HashMap 对象

调用3

③ #HashMap(int initialCapacity, float loadFactor) 初始化容量为 initialCapacity 、加载因子为 loadFactor 的 HashMap 对象

调用 #tableSizeFor(int cap) 方法，返回大于 cap 的最小 2 的 N 次方。例如说，cap = 10 时返回 16 ，cap = 28 时返回 32 。

为什么这里的 threshold 要返回大于等于 initialCapacity 的最小 2 的 N 次方呢？

在 put 方法中，计算 table 数组对应的位置，逻辑是 (n - 1) & hash ，这个和我们预想的 hash % (n - 1) 的有差别。这两者在 n 是 2 的 N 次方情况下是等价的。那么考虑到性能，我们会选择 & 位操作。这样，就要求数组容量 n 要尽可能是 2 的 N 次方。

而在 #resize() 扩容方法中，我们会看到 HashMap 的容量，一直能够保证是 2 的 N 次方。

如此，#tableSizeFor(int cap) 方法，也需要保证返回的是 2 的 N 次方。

**③ #HashMap(Map<? extends K, ? extends V> m)**创建 HashMap 对象，并将 c 集合添加到其中

• 整个过程分成 <1> 和 <2> 的两个步骤。
• <1> 处，保证 table 容量足够，分成了 table 是否为空有不同的处理。table 为空的情况的处理？因为此时 table 未初始化，我们只需要保证 threshold 大于数组大小即可，在 put key-value 键值的时候，在去真正的初始化 table 就好咧。
• <2> 处，遍历 m 集合，逐个调用 #putVal(hash, key, val, onlyIfAbsent, evict) 方法，添加到 HashMap 中。

// HashMap.java

/**
 * 默认的初始化容量
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * 默认加载因子为 0.75
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;


//1
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

//2
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//3
/**
 * 最大的容量为 2^30 。
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

public HashMap(int initialCapacity, float loadFactor) {
    // 校验 initialCapacity 参数
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // 避免 initialCapacity 超过 MAXIMUM_CAPACITY
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 校验 loadFactor 参数
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    // 设置 loadFactor 属性
    this.loadFactor = loadFactor;
    // <X> 计算 threshold 阀值
    this.threshold = tableSizeFor(initialCapacity);
}

static final int tableSizeFor(int cap) {
    // 将 cap 从最高位（最左边）第一个为 1 开始的位开始，全部设置为 1 。
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    // 因为 n 已经是 0..01..1 的情况，那么 n + 1 就能满足 cap 的最小 2 的 N 次方
    // 在 cap 为 0 和 1 的时候，n 会为 -1 ，则此时最小 2 的 N 次方为 2^0 = 1 。
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

//4
public HashMap(Map<? extends K, ? extends V> m) {
    // 设置加载因子
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    // <X> 批量添加到 table 中
    putMapEntries(m, false);
}

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    // <1>
    if (s > 0) {
        // 如果 table 为空，说明还没初始化，适合在构造方法的情况
        if (table == null) { // pre-size
            // 根据 s 的大小 + loadFactor 负载因子，计算需要最小的 tables 大小
            float ft = ((float)s / loadFactor) + 1.0F; // + 1.0F 的目的，是因为下面 (int) 直接取整，避免不够。
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            // 如果计算出来的 t 大于阀值，则计算新的阀值
            if (t > threshold)
                threshold = tableSizeFor(t);
        // 如果 table 非空，说明已经初始化，需要不断扩容到阀值超过 s 的数量，避免扩容
        } else {
            // Because of linked-list bucket constraints, we cannot
            // expand all at once, but can reduce total resize
            // effort by repeated doubling now vs later
            while (s > threshold && table.length < MAXIMUM_CAPACITY)
                resize(); // 扩容
        }

        // <2> 遍历 m 集合，逐个添加到 HashMap 中。
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

哈希函数

• 性能足够高。因为基本 HashMap 所有的操作，都需要用到哈希函数。
• 对于计算出来的哈希值足够离散，保证哈希冲突的概率更小。

// HashMap.java

static final int hash(Object key) {
    int h;
    // h = key.hashCode() 计算哈希值
    // ^ (h >>> 16) 高 16 位与自身进行异或计算，保证计算出来的 hash 更加离散
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

^ (h >>> 16) 保证“hash 更加离散”

这段代码叫“扰动函数”

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

添加单个元素

#put(K key, V value) 方法

public V put(K key, V value) {
    // hash(key) 计算哈希值
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; // tables 数组
    Node<K,V> p; // 对应位置的 Node 节点
    int n; // 数组大小
    int i; // 对应的 table 的位置
    // <1> 如果 table 未初始化，或者容量为 0 ，则进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize() /*扩容*/ ).length;
    // <2> 如果对应位置的 Node 节点为空，则直接创建 Node 节点即可。
    if ((p = tab[i = (n - 1) & hash] /*获得对应位置的 Node 节点*/) == null)
        tab[i] = newNode(hash, key, value, null);
    // <3> 如果对应位置的 Node 节点非空，则可能存在哈希冲突
    else {
        Node<K,V> e; // key 在 HashMap 对应的老节点
        K k;
        // <3.1> 如果找到的 p 节点，就是要找的，则则直接使用即可
        if (p.hash == hash && // 判断 hash 值相等
            ((k = p.key) == key || (key != null && key.equals(k)))) // 判断 key 真正相等
            e = p;
        // <3.2> 如果找到的 p 节点，是红黑树 Node 节点，则直接添加到树中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // <3.3> 如果找到的 p 是 Node 节点，则说明是链表，需要遍历查找
        else {
            // 顺序遍历链表
            for (int binCount = 0; ; ++binCount) {
                // `(e = p.next)`：e 指向下一个节点，因为上面我们已经判断了最开始的 p 节点。
                // 如果已经遍历到链表的尾巴，则说明 key 在 HashMap 中不存在，则需要创建
                if ((e = p.next) == null) {
                    // 创建新的 Node 节点
                    p.next = newNode(hash, key, value, null);
                    // 链表的长度如果数量达到 TREEIFY_THRESHOLD（8）时，则进行树化。
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break; // 结束
                }
                // 如果遍历的 e 节点，就是要找的，则则直接使用即可
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break; // 结束
                // p 指向下一个节点
                p = e;
            }
        }
        // <4.1> 如果找到了对应的节点
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 修改节点的 value ，如果允许修改
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 节点被访问的回调
            afterNodeAccess(e);
            // 返回老的值
            return oldValue;
        }
    }
    // <4.2>
    // 增加修改次数
    ++modCount;
    // 如果超过阀值，则进行扩容
    if (++size > threshold)
        resize();
    // 添加节点后的回调
    afterNodeInsertion(evict);
    // 返回 null
    return null;
}

扩容

#resize() 方法，两倍扩容 HashMap 初始化数组

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // <1> 开始：
    // <1.1> oldCap 大于 0 ，说明 table 非空
    if (oldCap > 0) {
        // <1.1.1> 超过最大容量，则直接设置 threshold 阀值为 Integer.MAX_VALUE ，不再允许扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // <1.1.2> newCap = oldCap << 1 ，目的是两倍扩容
        // 如果 oldCap >= DEFAULT_INITIAL_CAPACITY 满足，说明当前容量大于默认值（16），则 2 倍阀值。
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // <1.2.1>【非默认构造方法】oldThr 大于 0 ，则使用 oldThr 作为新的容量
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // <1.2.2>【默认构造方法】oldThr 等于 0 ，则使用 DEFAULT_INITIAL_CAPACITY 作为新的容量，使用 DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY 作为新的容量
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 1.3 如果上述的逻辑，未计算新的阀值，则使用 newCap * loadFactor 作为新的阀值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // <2> 开始：
    // 将 newThr 赋值给 threshold 属性
    threshold = newThr;
    // 创建新的 Node 数组，赋值给 table 属性
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 如果老的 table 数组非空，则需要进行一波搬运
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            // 获得老的 table 数组第 j 位置的 Node 节点 e
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 置空老的 table 数组第 j 位置
                oldTab[j] = null;
                // <2.1> 如果 e 节点只有一个元素，直接赋值给新的 table 即可
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // <2.2> 如果 e 节点是红黑树节点，则通过红黑树分裂处理
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // <2.3> 如果 e 节点是链表
                else { // preserve order
                    // HashMap 是成倍扩容，这样原来位置的链表的节点们，会被分散到新的 table 的两个位置中去
                    // 通过 e.hash & oldCap 计算，根据结果分到高位、和低位的位置中。
                    // 1. 如果结果为 0 时，则放置到低位
                    // 2. 如果结果非 1 时，则放置到高位
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 这里 do while 的原因是，e 已经非空，所以减少一次判断。细节~
                    do {
                        // next 指向下一个节点
                        next = e.next;
                        // 满足低位
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 满足高位
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 设置低位到新的 newTab 的 j 位置上
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 设置高位到新的 newTab 的 j + oldCap 位置上
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

1）计算新的容量和扩容阀值，并创建新的 table 数组；2）将老的 table 复制到新的 table 数组中。

树化

#treeifyBin(Node<K,V>[] tab, int hash) 方法，将 hash 对应 table 位置的链表，转换成红黑树。

/**
 * 每个位置链表树化成红黑树，需要的链表最小长度
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * HashMap 允许树化最小 key-value 键值对数
 */
static final int MIN_TREEIFY_CAPACITY = 64;

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // <1> 如果 table 容量小于 MIN_TREEIFY_CAPACITY(64) ，则选择扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // <2> 将 hash 对应位置进行树化
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 顺序遍历链表，逐个转换成 TreeNode 节点
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        // 树化
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

哈希表LinkedHashMap

HashMap 提供的访问，是无序的

有序访问的 HashMap 有两种选择：

• TreeMap ：按照 key 的顺序。
• LinkedHashMap ：按照 key 的插入和访问的顺序。

LinkedHashMap ，在 HashMap 的基础之上，提供了顺序访问的特性。而这里的顺序，包括两种：

按照 key-value 的插入顺序进行访问。

按照 key-value 的访问顺序进行访问。通过这个特性，我们实现基于 LRU 算法的缓存。

LinkedHashMap 可以理解成是 LinkedList + HashMap 的组合

• 实现 Map 接口。
• 继承 HashMap 类。

属性

// LinkedHashMap.java

/**
 * 头节点。
 * 越老的节点，放在越前面。所以头节点，指向链表的开头
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * 尾节点
 * 越新的节点，放在越后面。所以尾节点，指向链表的结尾
 */
transient LinkedHashMap.Entry<K,V> tail;

/**
 * 是否按照访问的顺序。
 * true ：按照 key-value 的访问顺序进行访问。
 * false ：按照 key-value 的插入顺序进行访问。
 */
final boolean accessOrder;

构造方法

LinkedHashMap 一共有 5 个构造方法，其中四个和 HashMap 相同，只是多初始化 accessOrder = false 。所以，默认使用插入顺序进行访问。

另外一个 #LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 构造方法，允许自定义 accessOrder 属性。

// LinkedHashMap.java

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

创建节点

#put(K key, V value) 方法

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    // <1> 创建 Entry 节点
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<>(hash, key, value, e);
    // <2> 添加到结尾
    linkNodeLast(p);
    // 返回
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    // 记录原尾节点到 last 中
    LinkedHashMap.Entry<K,V> last = tail;
    // 设置 tail 指向 p ，变更新的尾节点
    tail = p;
    // 如果原尾节点 last 为空，说明 head 也为空，所以 head 也指向 p
    if (last == null)
        head = p;
    // last <=> p ，相互指向
    else {
        p.before = last;
        last.after = p;
    }
}

LinkedHashMap 实现 LRU 算法的缓存

class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private final int CACHE_SIZE;

    /**
     * 传递进来最多能缓存多少数据
     *
     * @param cacheSize 缓存大小
     */
    public LRUCache(int cacheSize) {
        // true 表示让 LinkedHashMap 按照访问顺序来进行排序，最近访问的放在头部，最老访问的放在尾部。
        super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
        CACHE_SIZE = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当 map 中的数据量大于指定的缓存个数的时候，就自动删除最老的数据。
        return size() > CACHE_SIZE;
    }

}

哈希集合HashSet

HashSet ，基于 HashMap 的 Set 实现类。在业务中，如果我们有排重的需求，一般会考虑使用 HashSet 。

• 实现 java.util.Set 接口，并继承 java.util.AbstractSet 抽像类。
• 实现 java.io.Serializable 接口。
• 实现 java.lang.Cloneable 接口。

属性

// HashSet.java

private transient HashMap<E, Object> map;

• map 的 key ，存储 HashSet 的每个 key 。
• map 的 value ，因为 HashSet 没有 value 的需要，所以使用一个统一的 PRESENT 即可。

// HashSet.java

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

构造方法

// HashSet.java

public HashSet() {
    map = new HashMap<>();
}

public HashSet(Collection<? extends E> c) {
    // 最小必须是 16 。
    // (int) (c.size()/.75f) + 1 避免扩容
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    // 批量添加
    addAll(c);
}

public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor); // 注意，这种情况下的构造方法，创建的是 LinkedHashMap 对象
}

• 在构造方法中，会创建 HashMap 或 LinkedHashMap 对象。

添加单个元素

// HashSet.java

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

• map 的 value 值，就是我们看到的 PRESENT 。

TreeMap

按照 key 的顺序的 Map 实现类

可以用在签名生成算法 按照请求参数的 key 排序，然后拼接后加密

• 实现 java.util.Map 接口，并继承 java.util.AbstractMap 抽像类。
• 直接实现 java.util.NavigableMap 接口，间接实现 java.util.NavigableMap 接口
• 实现 java.io.Serializable 接口。
• 实现 java.lang.Cloneable 接口。

原理

HashMap 的数组，每个桶的链表在元素过多的情况下，会转换成红黑树。而 TreeMap 也是基于红黑树实现的，并且只是一棵红黑树。

所以 TreeMap 可以理解成 HashMap 数组中的一个转换成红黑树的桶。

红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

• 有序性：红黑树是一种二叉查找树，父节点的 key 小于左子节点的 key ，大于右子节点的 key 。这样，就完成了 TreeMap 的有序的特性。
• 高性能：红黑树会进行自平衡，避免树的高度过高，导致查找性能下滑。这样，红黑树能够提供 logN 的时间复杂度。

属性

// TreeMap.java

/**
 * key 排序器
 */
private final Comparator<? super K> comparator;

/**
 * 红黑树的根节点
 */
private transient Entry<K,V> root;

/**
 * key-value 键值对数量
 */
private transient int size = 0;

/**
 * 修改次数
 */
private transient int modCount = 0;

Entry 是 TreeMap 的内部静态类

// TreeMap.java

/**
 * 颜色 - 红色
 */
private static final boolean RED   = false;
/**
 * 颜色 - 黑色
 */
private static final boolean BLACK = true;

static final class Entry<K,V> implements Map.Entry<K,V> {

    /**
     * key 键
     */
    K key;
    /**
     * value 值
     */
    V value;
    /**
     * 左子节点
     */
    Entry<K,V> left;
    /**
     * 右子节点
     */
    Entry<K,V> right;
    /**
     * 父节点
     */
    Entry<K,V> parent;
    /**
     * 颜色
     */
    boolean color = BLACK;
    
    // ... 省略一些
    
}

构造方法

① #TreeMap()

② #TreeMap(Comparator<? super K> comparator)

③ #TreeMap(SortedMap<K, ? extends V> m)

④ #TreeMap(Map<? extends K, ? extends V> m)

//默认构造方法，不使用自定义排序，所以此时 comparator 为空。
public TreeMap() {
    comparator = null;
}

//可传入 comparator 参数，自定义 key 的排序规则。
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

//传入已经排序的 m ，然后构建出 TreeMap 。
public TreeMap(SortedMap<K, ? extends V> m) {
    // <1> 设置 comparator 属性
    comparator = m.comparator();
    try {
        // <2> 使用 m 构造红黑树
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
    }
}

private void buildFromSorted(int size, Iterator<?> it,
                             java.io.ObjectInputStream str,
                             V defaultVal)
    throws  java.io.IOException, ClassNotFoundException {
    // <1> 设置 key-value 键值对的数量
    this.size = size;
    // <2> computeRedLevel(size) 方法，计算红黑树的高度
    // <3> 使用 m 构造红黑树，返回根节点
    root = buildFromSorted(0, 0, size - 1, computeRedLevel(size),
                           it, str, defaultVal);
}


//传入 m 的是 Map 类型，构建成初始的 TreeMap 
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    // 添加所有元素
    putAll(m);
}

因为 TreeMap 是基于树的结构实现，所以无需考虑扩容问题。

TreeSet

如果我们有排重+ 排序的需求，一般会考虑使用 TreeSet 。

属性

// TreeSet.java

private transient NavigableMap<E,Object> m;

构造方法

// TreeSet.java

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

public TreeSet() {
    this(new TreeMap<>());
}

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

public TreeSet(Collection<? extends E> c) {
    this();
    // 批量添加
    addAll(c);
}

public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    // 批量添加
    addAll(s);
}

// TreeSet.java

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}