关于java:Java-HashMap源码解析

注：此文针对 jdk1.8 下的源码进行剖析，不同 jdk 版本下的 HashMap 会略有不同

背景介绍

哈希表的实现次要分为两大类：凋谢寻址法和拉链法。
而在 Java 源码中，HashMap 的实现可归为拉链法这一大类中。
本文将按照 Java 源码，将 jdk1.8 实现的 HashMap 的种种细节进行剖析。

源码剖析

     /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */

在这段源码中波及到了 6 个变量

DEFAULT_INITIAL_CAPACITY

• 变量含意：默认初始化容量
• 变量值：16

如果 HashMap 初始时未指定容量

HashMap<Integer, Integer> map = new HashMap<>();

那么该 map 的容量会被初始化为 16

须要留神的是，倡议在结构 HashMap 时对其指定大小，尽量一次开够，且容量通常为 2 的整数次幂，这样能力使 HashMap 体现得更高效。

MAXIMUM_CAPACITY

• 变量含意：最大容量
• 变量值：1 << 30

HashMap 的最大容量不能超过 1 << 30

DEFAULT_LOAD_FACTOR

• 变量含意：扩容加载因子
• 变量值：0.75f

当 HashMap 结构时并没有指定容量并且此时的元素个数已达到容量的 0.75 倍时，HashMap 会进行扩容

TREEIFY_THRESHOLD、UNTREEIFY_THRESHOLD、MIN_TREEIFY_CAPACITY

这三个变量须要一起介绍，因为他们都牵扯到 Java HashMap 的底层实现。
正如上文所说，Java 的 HashMap 可归为拉链法这一大类，但它的设计远不止一般的拉链法那么简略，而是非常精妙。
最奢侈的拉链法是指在哈希表产生哈希抵触的时候，将 Node[]数组中抵触的 Node 后连贯一个链表，使其形如
图中展现的为 Node[1]在遭逢哈希抵触时的解决，它会向 Node[1]节点下延长出一条链表

可能聪慧的读者看到这里会有疑难了，如果产生大量的哈希抵触，是不是所有节点都会变成一条很长的链表，那如此一来，查问效率岂不是会大大降低？

正是思考到了这个起因，Java 在设计 HashMap 时对这种奢侈的拉链法做了改良，当这条链表变得很长时，它会进化为红黑树，而 TREEIFY_THRESHOLD、UNTREEIFY_THRESHOLD、MIN_TREEIFY_CAPACITY 这三个变量正是管制红黑树和链表之间的转换。

TREEIFY_THRESHOLD 的值为 8，代表当链表长度大于 8 时，这条链表将会变为红黑树
UNTREEIFY_THRESHOLD 的值为 6，代表红黑树中的节点小于等于 6 时，它会从新变回链表
MIN_TREEIFY_CAPACITY 的值为 64，代表当产生哈希抵触且哈希表的容量小于 64 时，它首先会抉择扩容，而不是间接采取拉链法。

总结

HashMap 中的实现决定了它的取与寸的效率都极高，其工夫复杂度可被认为是 O(1)，当须要 Key-Value 模式的存储且 key 惟一时，采纳 HashMap 无疑是极佳的抉择。