Java 集合 源码

Java集合源码学习

源码阅读笔记

Posted by John Mactavish on July 29, 2020

前言

暑假闲来无事，看看 Java 标准库源码。直接看下载的源码当然优先级排最后，毕竟真正的源码 可能受性能、边界条件等因素影响搞出一些不明所以的东西出来破坏阅读体验（所幸看的是 Java 的……）， 同时为了梳理代码的架构设计可能还要非常麻烦地动用 SourceInsight （我没用过）之类的东西， 即使如此得到的静态类、接口层次结构中也可能包含各种 AbstractClass 之类的对理解没有帮助的中间层次。 所以我理所当然地选择了跟着 Github 上现有的源码阅读项目走，毕竟中国“课代表”向来有着记笔记与分享笔记的 好习惯。目前跟的是这个， 其中集合模块在这。 上面有的基本不会复读，博文主要记录自己的发现与感悟，可能会引用一些内容和源码以保证结构完整。

2020-07-30 更新：今天我更新 LinkedList 部分的时候发现上面的那个集合模块笔记里的代码用的 好像是 JDK 1.6 里面的源码（我想要 JDK 8）……无语， 现在跟着这一个仓库。

集合主要框架

Java 集合工具包位于 java.util 中，主要有 4 个部分：List、Set、Map 和 工具类(Iterator、Enumeration、Arrays 与 Collections)。 包括接口在内的层次结构用一张图足以说明：

collection

有关 UML 的类图(class diagram)可以在这里找到简单教程。 继承、实现关系对应哪些 Java 语法不言而喻；至于依赖关系，它指的是一个类的字段或方法局部变量、参数、 返回值中用到了另一个类。比如说图中的 Collection 的实现类都要实现 iterator() 函数， 返回一个 Iterator 对象，那我们认为 Collection 依赖于 Iterator。

ArrayList

ArrayList 是线程不安全的支持随机访问功能的泛型动态数组，是 Java 集合中最常被用到的类之一。

构造函数

// 默认构造函数
ArrayList()

// capacity是ArrayList的默认容量大小。当由于增加数据导致容量不足时，容量会添加上一次容量大小的一半。
ArrayList(int capacity)

// 创建一个包含collection的ArrayList
ArrayList(Collection<? extends E> collection)

继承关系与类声明

java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractList<E>
               ↳     java.util.ArrayList<E>

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

类字段与方法

字段有：

    // 序列版本号
    private static final long serialVersionUID = 8683452581122892189L;

    // 保存ArrayList中数据的数组
    private transient Object[] elementData;

    // ArrayList中实际数据的数量
    private int size;

注意 elementData 前的 transient(易失) 关键字，它表示这个字段不会在对象序列化时被存储。 记得我们上面提到了 ArrayList 是可序列化的类（实现了 java.io.Serializable）， 那么 elementData 不是 ArrayList 具体存放元素的地方吗？对象序列化时为什么不要了？ 原来 ArrayList 为序列化的两个方法提供了自己的实现:

// 将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();

    // 写入“数组的容量”
    s.writeInt(elementData.length);

    // 写入“数组的每一个元素”
    for (int i=0; i< size; i++)
        s.writeObject(elementData[i]);

    if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
    }
}

// 先将ArrayList的“容量”读出，然后将“所有的元素值”读出
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // 从输入流中读取ArrayList的“容量”
    int arrayLength = s.readInt();
    Object[] a = elementData = new Object[arrayLength];

    // 从输入流中将“所有的元素值”读出
    for (int i=0; i< size; i++)
        a[i] = s.readObject();
}

而不使用默认实现的原因是 elementData 只是一个缓存数组，它通常会预留一些容量， 那里没有实际存储元素，直接序列化整个数组会浪费空间和时间。注意自己的实现中 ArrayList 的 size 即为实际存储的元素的个数，而 capacity 则需要单独记录下来。

ArrayList 的一个构造器实现如下：

// ArrayList 带容量大小的构造函数。
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    // 新建一个数组
    this.elementData = new Object[initialCapacity];
}

它检查了参数的有效性，并为无效参数抛出自己的异常，这是库代码的一个 best practice。 如果用户使用库时触发了 IndexOutOfBoundException 这类底层异常而不得不开始阅读库代码寻找答案， 那么这个库的设计就很有问题，它没有构建好自己的抽象层。

trimToSize 方法调用 Arrays.copyOf 新建一个长度刚好为 size 的副本代替原来的缓存数组； 因为 ArrayList 的容量就是缓存数组的长度，而 Java 中数组长度不可以改变，所以只有 新建副本一条路可走。因此，无疑这个方法的时间复杂度为 O(n)（具体参考 这个问题， native 方法会有优化，比自己写 for 循环快，但肯定还是 O(n)），开销有一点反直觉，还是不要 闲着没事经常用为好。

// 将当前容量值设为等于实际元素个数
public void trimToSize() {
    modCount++;
    int oldCapacity = elementData.length;
    if (size < oldCapacity) {
        elementData = Arrays.copyOf(elementData, size);
    }
}

ensureCapacity(int minCapacity) 调用后保证 capacity 至少为 minCapacity。 可以猜到如果 capacity 足够大，方法会立即返回； 但是注意它没说“如果 capacity 较小，则把它扩充到 minCapacity”。事实上，源码表明， 它首先尝试设置“新的容量=(原始容量 x3)/2 + 1”，假如这还不够，它才会把 capacity 扩充到 minCapacity。 当然，只要改变了 capacity，就会导致内部缓存数组的复制。其实，ArrayList 中其他添加元素 的方法使用的都是这个 public 方法，也就是这里的扩容策略决定了 ArrayList 的扩容策略。

// 确定ArrarList的容量。
// 若ArrayList的容量不足以容纳当前的全部元素，设置 新的容量=“(原始容量x3)/2 + 1”
public void ensureCapacity(int minCapacity) {
    // 将“修改统计数”+1
    modCount++;
    int oldCapacity = elementData.length;
    // 若当前容量不足以容纳当前的元素个数，设置 新的容量=“(原始容量x3)/2 + 1”
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
            newCapacity = minCapacity;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

contains 内部实现用的是 indexOf 方法，这并不意外。

// 返回ArrayList是否包含Object(o)
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

关于 toArray 方法，我一年前写过一篇文章简单提过， 难以想象我一年前水平竟然如此之低，不忍直视……今天再来详细讲一讲。

// 返回ArrayList的Object数组
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

// 返回ArrayList的模板数组。所谓模板数组，即可以将T设为任意的数据类型
public <T> T[] toArray(T[] a) {
    // 若数组a的大小 < ArrayList的元素个数；
    // 则新建一个T[]数组，数组大小是“ArrayList的元素个数”，并将“ArrayList”全部拷贝到新数组中
    if (a.length < size)
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());

    // 若数组a的大小 >= ArrayList的元素个数；
    // 则将ArrayList的全部元素都拷贝到数组a中。
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

对于第一个重载方法，还是借用一年前的例子：

ArrayList<String> list=new ArrayList<String>();
for (int i = 0; i < 10; i++) {
    list.add(""+i);
}
String[] array= (String[]) list.toArray();

// Exception in thread "main" java.lang.ClassCastException: 
// [Ljava.lang.Object; cannot be cast to [Ljava.lang.String;

这个会报错的原因是 Java 数组不支持逆变，Object[] 变量不能强制转为 String[]，即使它 确实应该是 String[]（当然，数组可以协变，所以反过来总是可以的，具体参考 上一篇文章）。

至于第二个重载方法，就比较有意思了。它把 ArrayList 转化为特定类型的数组，如果传入的 数组足够大，它会把 ArrayList 里的内容写进这个数组，否则会创建一个新数组。 我相信你一定和我当初一样，好奇为什么需要传入一个数组作为参数，它不能自己新建一个并返回吗。 答案是类型擦除。而关键在于返回的是数组，倘若是其他泛型类就无所谓了，反正大家用的其实 都是 Object，而数组在创建时需要知道它内部元素的具体类型。那就得想办法给它类型信息喽。 数组参数的意义更在于它的类型(a.getClass())而不是数组本身。当然了，更现代化的写法是:

public <T> T[] toArray(Class<T> elementType)

这样写明确指出了我们要的是类型信息，不过，为了兼容性只能够妥协，继续沿用以前的方法签名。

另外注意 toArray(T[] a) 是怎么定义的：

class ArrayList<T>{
  // ...
    public T[] toArray(T[] a){
      // ...
    }
}

class ArrayList<T>{
  // ...
    public <T> T[] toArray(T[] a){
      // ...
    }
}

class ArrayList<T>{
  // ...
    public <E> E[] toArray(E[] a){
      // ...
    }
}

前两者是不一样的，第一个 toArray 的类型参数 T 与 ArrayList<T> 中的 T 是同一的。但 第二个使用尖括号语法定义了一个新的 T，隐藏(hide)了 ArrayList<T> 中的 T,它实际上与 第三个是相同的。换句话说，泛型方法的类型参数与泛型类的类型参数无关。这样设计是为了把数组类型 的选择权交给使用者，毕竟使用者未必就想要把 ArrayList<Integer> 变成 Integer[],也许 要的是 Number[] 或者 Object[]。

ArrayList<Integer> list; // ArrayList<T> 的 T 是 Integer
Integer[] array = list.toArray(new Integer[0]); 
Number[] array = list.toArray(new Number[0]); // 泛型方法的 T 是 Number
Object[] array = list.toArray(new Object[0]); // 泛型方法的 T 是 Object

ArrayList 里的 remove 方法用到了下面这个辅助方法：

// 快速删除第 index 个元素
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    // 从"index+1"开始，用后面的元素替换前面的元素。
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                          numMoved);
    // 将最后一个元素设为null
    elementData[--size] = null; // Let gc do its work
}

它和其他的多个方法一样，使用

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

令参数 src 与 dest 为同一个数组，在其上覆盖元素以完成删除功能，整体偏移元素以为待添加元素腾出空间。

clear 会将 size 置 0，同时把元素都置 null(O(n)时间复杂度)，以便于 GC 回收。它不会修改 capacity。

// 清空ArrayList，将全部的元素设为null
public void clear() {
    modCount++;

    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

ArrayList 是并发不安全的，但是它提供了 fail-fast 机制来检测不安全状态并抛出异常。 比如说，当通过 iterator 去遍历某集合时，若该集合的内容在期间被改变了， 那么 iterator 下一次访问集合时，就会抛出 ConcurrentModificationException 异常。 结合源码即可了解它的原理。

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {

    ...

    // AbstractList中唯一的属性
    // 用来记录List修改的次数：每修改一次(添加/删除等操作)，将modCount+1
    protected transient int modCount = 0;

    // 返回List对应迭代器。实际上，是返回Itr对象。
    public Iterator<E> iterator() {
        return new Itr();
    }

    // Itr是Iterator(迭代器)的实现类
    private class Itr implements Iterator<E> {
        int cursor = 0;

        int lastRet = -1;

        // 修改数的记录值。
        // 每次新建Itr()对象时，都会保存新建该对象时对应的modCount；
        // 以后每次遍历List中的元素的时候，都会比较expectedModCount和modCount是否相等；
        // 若不相等，则抛出ConcurrentModificationException异常，产生fail-fast事件。
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size();
        }

        public E next() {
            // 获取下一个元素之前，都会判断“新建Itr对象时保存的modCount”和“当前的modCount”是否相等；
            // 若不相等，则抛出ConcurrentModificationException异常，产生fail-fast事件。
            checkForComodification();
            try {
                E next = get(cursor);
                lastRet = cursor++;
                return next;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        public void remove() {
            if (lastRet == -1)
                throw new IllegalStateException();
            checkForComodification();

            try {
                AbstractList.this.remove(lastRet);
                if (lastRet < cursor)
                    cursor--;
                lastRet = -1;
                expectedModCount = modCount; // 更新
            } catch (IndexOutOfBoundsException e) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

    ...
}

注意三点：第一，fail-fast 发生的时机是在尝试读不安全状态时而非破坏正常状态（并发修改集合）时； 第二，fail-fast 机制是“尽力而为”的，它不保证总可以检测到不安全状态；

From Java Docs

The iterators returned by this class’s iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

第三，fail-fast 是 iterator 支持的，它不仅仅可以检测多线程并发导致的不安全状态， 看下面的来自 Stack Overflow 的例子：

for(Iterator<String> itpendingmsgs = pendingmsgs.iterator(); itpendingmsgs.hasNext();) {
    String pendingmsg = itpendingmsgs.next();
    String dest = pendingmsg.substring(4);              
    if (protocol.author.equals(dest)) {
        sendMsg(msg);
        pendingmsgs.remove(pendingmsg); // WRONG
        // itpendingmsgs.remove(); // CORRECT
        // use iterator's own remove or add methods
    }
}

另外看一下下面的例子：

public static void main(String[] args) {
    ArrayList<Integer> li = new ArrayList<>();
    li.add(0);li.add(1);li.add(2);li.add(3);li.add(4);

    // 增强型 for 循环是 iterator 的语法糖
    for (var e: li) { // java.util.ConcurrentModificationException
        li.remove(e); 
    }
    System.out.println(li);
}

public static void main(String[] args) {
    ArrayList<Integer> li = new ArrayList<>();
    li.add(0);li.add(1);li.add(2);li.add(3);li.add(4);

    for (int i = 0; i < li.size(); i++) {
        li.remove(i); // 删除元素导致其他元素索引变化
    }
    System.out.println(li); // 输出 [1, 3]
}

所以，唯一一个可以安全地边遍历边修改集合的方法是显式使用 iterator 和它的 remove 或者 add 方法。

LinkedList

构造函数

// 默认构造函数：创建一个空的链表
LinkedList()

// 包含“集合”的构造函数:创建一个包含“集合”的LinkedList
LinkedList(Collection<? extends E> c)

继承关系与类声明

java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractList<E>
               ↳     java.util.AbstractSequentialList<E>
                     ↳     java.util.LinkedList<E>

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; // 指向尾结点

注意一个重要的内部类 Node，它代表双向链表的一个结点，所以 LinkedList 就是一个双向链表。

// 双向链表的节点所对应的数据结构。
// 包含3部分：上一节点，下一节点，当前节点值。
private static class Node<E> {
    E item;
    LinkedList.Node<E> next;
    LinkedList.Node<E> prev;

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

LinkedList 的一些基本操作都分为两组：removeFirst/removeLast、 getFirst/getLast、addFirst/addLast，它们分别对应为在链表头尾处的操作。 对于输入参数是元素对象的方法，LinkedList 的处理逻辑与 ArrayList 一致：add(E e) 添加到 链表的最后（等同于 addLast），remove(Object o) 从前面开始查找（等同于 removeFirst）。 而对于输入参数是元素索引的方法，都用到了下面的方法来寻找指定元素，时间复杂度是 O(n/2)。

// 获取指定下标的结点，index从0开始
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;
    }
}

clear 方法并不是只删除了头尾结点了事，而是遍历了整个链表，置空了所有结点， 与 ArrayList 一样是 O(n) 时间复杂度。

// 清空双向链表
public void clear() {
    //遍历链表，删除所有结点,方便gc回收垃圾
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    // 首尾结点置空
    first = last = null;
    // 元素数量置0
    size = 0;
    modCount++;
}

LinkedList 实现了 Deque（读作 deck），而 Deque 接口定义了在双端队列两端访问元素的方法。 提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常， 另一种形式返回一个特殊值（null 或 false，具体取决于操作）。同时， LinkedList 既可以作为 FIFO(先进先出) 的队列，又可以作为 LIFO(后进先出) 的栈，有着 对应数据结构的特殊名称方法。感觉给简单的几个功能起了好多名字……

Linked List

LinkedList 的 iterator 也支持 fail-fast 机制，这里就不再重提了。

最后提一下，我一开始参考的源码笔记 中给出的代码好像是 JDK 1.6 的源码，写法也很有趣。它是这样设计字段的：不保存头尾结点的引用， 转而保存了一个不包含实际数据的哨兵节点。

    // 链表的表头，表头不包含任何数据。
    private transient Entry<E> header = new Node<E>(null, null, null);

    // LinkedList中元素个数
    private transient int size = 0;

在默认的构造函数中，初始化哨兵结点 header 的指针都指向自己。

// 默认构造函数：创建一个空的链表
public LinkedList() {
    header.next = header.prev = header;
}

addFirst 把元素添加在哨兵结点 header 之后（让 header.next 指 向它），addLast 则把元素添加在哨兵结点 header 之前（让 header.prev 指向它）。 那么，有元素的 LinkedList 的内部模型如下图所示，header 连接双向链表的头和尾形成环形， 这样只需要一个哨兵结点就可以控制两个端点。

   last          first
    6 -- header -- 0
    |              |
    5              1
    |              |
    4 --    3   -- 2

size = 7
header.next = 0
header.prev = 6

Vector 与 Stack

Vector 与 ArrayList 一样是使用动态数组实现的，但是 Vector 中的操作是线程安全的。 Stack 是 Vector 的子类，表现为一个堆栈。这两个类都已经过时了，不推荐使用。

Vector 保证线程安全的措施是在每一个方法上加上 synchronized 修饰，而对集合的 操作经常是几个方法的组合使用，这种情况下依然需要自己采取措施保证组合操作的并发安全。 如果需要线程安全 ArrayList，可以用 Collections 的 synchronizedList 方法装饰。 而 Stack 类违反了面向对象设计原则，Stack 应当只允许 push/pop/peek 操作，但是它的 父类 Vector 却提供了更多的方法，允许修改任意索引处的元素。一般推荐用 Deque 代替它， 即把双端队列当成堆栈用。

HashMap

HashMap 是常用的 Java 集合之一，是基于哈希表的 Map 接口的实现。 与 HashTable 主要区别为不支持同步和允许 null 作为 key 和 value。 HashMap 非线程安全，如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法 使 HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap。 在 JDK1.6 中，HashMap 采用数组+链表实现，即使用链表处理冲突，同一 hash 值的元素都存储在一个链表里。 但是当位于一个链表中的元素较多，即 hash 值相等的元素较多时，通过 key 值依次查找的效率较低。 而 JDK1.8 中，HashMap 采用数组+链表+红黑树实现，当链表长度超过阈值 8 时，将链表转换为红黑树， 这样大大减少了查找时间。 原本 Map.Entry 接口的实现类 Entry 改名为了 Node。转化为红黑树时改用另一种实现 TreeNode。

构造函数

// 默认构造函数。
HashMap()

// 指定“容量大小”的构造函数
HashMap(int capacity)

// 指定“容量大小”和“负载因子”的构造函数
HashMap(int capacity, float loadFactor)

// 包含“子Map”的构造函数
HashMap(Map<? extends K, ? extends V> map)

继承关系与类声明

java.lang.Object
   ↳     java.util.AbstractMap<K, V>
         ↳     java.util.HashMap<K, V>

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable { }

类字段与方法

    // 默认的初始容量（容量为HashMap中槽的数目）是16，且实际容量必须是2的整数次幂。
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    // 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
    static final int MAXIMUM_CAPACITY = 1 << 30;

    // 默认负载因子0.75，如果当前键值对个数 >= HashMap最大容量*负载因子，进行rehash操作
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // JDK1.8 新加，Entry链表最大长度，当桶中节点数目大于该长度时，将链表转成红黑树存储；
    static final int TREEIFY_THRESHOLD = 8;

    // JDK1.8 新加，当桶中节点数小于该长度，将红黑树转为链表存储；
    static final int UNTREEIFY_THRESHOLD = 6;

    // 桶可能被转化为树形结构时对应的最小容量。当哈希表的大小超过这个阈值，才会把链式结构转化成树型结构，
    // 否则仅采取扩容来尝试减少冲突。
    // 应该至少4*TREEIFY_THRESHOLD来避免扩容和树形结构化之间的冲突。
    static final int MIN_TREEIFY_CAPACITY = 64;


    // 哈希桶数组，分配的时候，table的长度总是2的幂
    transient Node<K, V>[] table;

    // HashMap将数据转换成set的另一种存储形式，这个变量主要用于迭代功能
    transient Set<Map.Entry<K, V>> entrySet;

    // 实际存储的数量，HashMap的size()方法，实际返回的就是这个值，isEmpty()也是判断该值是否为0
    transient int size;

    // hashmap结构被改变的次数，用于支持fail-fast机制
    transient int modCount;

    // HashMap的负载因子
    final float loadFactor;

    // HashMap的扩容阈值，在HashMap中存储的Node键值对超过这个数量时，自动扩容容量为原来的二倍
    // threshold = loadFactor * table.length
    int threshold;

注意，HashMap 实际容量必须是 2 的整数次幂(power of 2)，主要是为了方便通过位运算确定 hash 值对应的桶索引， 否则，对于负数的 hash 值用传统的取模运算要稍微麻烦一点。为了保证“2 的整数次幂”这一要求，初始容量与 最大容量都满足要求，并且扩容倍数也是 2。因为扩容倍数是 2，所以扩容后大约会有一半的 hash 值对应的桶索引不变。

// example
static int indexFor(int h, int length) {
    return h & (length-1);
}

HashMap 的 clone 是浅拷贝。 clone 方法虽然生成了新的 HashMap 对象，其中的 table 数组虽然也是新生成的， 但是数组中的元素还是引用以前的 HashMap 中的元素。这就导致在对 HashMap 中的 mutable 元素进行修改的时候， 原对象也受到影响。但进行元素的新增、删除或更新则不会互相影响，毕竟这是对数组本身做出的改变。

HashMap 提供了 entrySet 用于迭代，因为其并不像其他集合类一样实现了 Iterable 接口，不可以用 增强型 for 循环直接迭代。另外，在 JDK 1.8 后，HashMap 还支持 forEach 方法，但是不同于其他 集合类（它们的 forEach 是 Iterable 接口支持的），HashMap 的 forEach 方法是自己实现的，只是 方法签名故意设计成相同的以假装保证统一。

// 返回hashMap中所有键值对的set视图。
// 改变hashMap会影响到set，反之亦然。
// 如果当迭代器迭代set时，hashMap被修改(除非是迭代器自己的remove()方法)，迭代器的结果是不确定的。
// set支持元素的删除，通过Iterator.remove、Set.remove、removeAll、retainAll、clear操作删除hashMap中对应的键值对。
// 不支持add和addAll方法。
public Set<Map.Entry<K, V>> entrySet() {
    Set<Map.Entry<K, V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

// 利用 entrySet() 迭代
long i = 0;
for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
    i += pair.getKey() + pair.getValue();
}

// 更棒的迭代方法
final long[] i = {0};
map.forEach((k, v) -> i[0] += k + v);

Hashtable

Hashtable 的处境与 Vector 类似，已不再建议使用，如果需要同步的 HashMap，左转 找 java.util.concurrent.ConcurrentHashMap。

HashSet

HashSet 是一个没有重复元素,不保证元素的顺序,允许使用 null 元素的非同步集合。

构造函数

// 默认构造函数
public HashSet() 

// 带集合的构造函数
public HashSet(Collection<? extends E> c) 

// 指定HashSet初始容量和负载因子的构造函数
public HashSet(int initialCapacity, float loadFactor) 

// 指定HashSet初始容量的构造函数
public HashSet(int initialCapacity)

继承关系与类声明

java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractSet<E>
               ↳     java.util.HashSet<E>

public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable { }

类字段与方法

    private transient HashMap<E,Object> map;

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

可以看到 HashSet 主要是在内部维护了一个 HashMap，把 Value 都设定为指向一个（比 你自己写 map.put(K,new Object()) 节约空间）没有实际意义 Object 的引用，而把 Key 暴露出来。

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

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

Enumeration 与 Iterator

从 JDK 1.0 引入了 Enumeration 接口，而从 JDK 1.2 引入了 Iterator 接口。 它们都可以进行枚举，功能基本上是重复的。主要区别有：

  1. Enumeration 接口不支持 remove 方法
  2. 使用 Enumeration 接口的都是 Vector,HashTable 和 Stack 这些过时的类
  3. Enumeration 接口不支持 fail-fast 机制
  4. Enumeration 接口的名字和方法名更长（这对于常用 API 来说真的是不容忽视的缺点）

方法对比如下：

Iterator Enumeration
hasNext() hasMoreElements()
next() nextElement()
remove() (Not Available)

所以，官方也建议使用 Iterator 代替 Enumeration。

Comparable 与 Comparator

Comparable 是排序接口(interface)，用于内部排序。 若一个类实现了 Comparable 接口，就意味着“该类支持排序”。 实现 Comparable 接口的类的对象可以用作 TreeMap 中的键或 TreeSet 中的元素，而不需要指定比较器。

// x.compareTo(y):
//      negative-> x<y
//      zero->     x==y
//      positive-> x>y
// 记忆方法：x.compareTo(y) 记作 x-y
public interface Comparable<T> {
    public int compareTo(T o);
}

Comparator 是比较器接口(谁让 Java 不支持高阶函数呢)，用于外部排序。 我们若需要控制某个类的次序，而该类本身不支持排序(即没有实现 Comparable 接口)； 那么，我们可以建立一个“该类的比较器”来进行排序，这个“比较器”只需要实现 Comparator 接口即可。

public interface Comparator<T> {
    int compare(T o1, T o2);
    // equals 不是必需的
    boolean equals(Object obj);
}

// with Java 8 Lambda
Collections.sort(list, (o1, o2) -> o1.getTime() - o2.getTime());

那么什么时候用 Comparable 什么时候用 Comparator 呢？显然，为自己的类实现 Comparable 可以 方便比较时使用，Comparator 则用于扩展别人的未实现 Comparable 的类（对修改封闭，对扩展开放）； 或者，Comparator 用于临时性的比较（特定情形下的一次性比较）。

推荐阅读 Java 文档中的集合的设计 FAQ

它为诸如此类的问题提供了答案：

Why don’t you provide an Iterator.add method?

Why don’t you support immutability directly in the core collection interfaces so that you can do away with optional operations (and UnsupportedOperationException)?

Why doesn’t Map extend Collection?

最后附上 GitHub：https://github.com/gonearewe

CATALOG
    FEATURED TAGS
    SSH Windows Subsystem Linux (wsl) IPv6 校园网 树莓派 VS Code Go 匿名函数 转载 golang gradle CSS Java git beego jQuery 算法 数据结构 设计模式 并发 随感 Programming Language 常用算法与数据结构模板系列 二叉树 马克思 论文 读书笔记 软件设计 Scala Redis Java 并发原理系列 分布式 JavaFX Spring Boot 一个视频播放器的设计与实现系列 缓存系统学习系列 性能测试
    FRIENDS