HashMap 源码分析

一、类图

       

二、源码分析

       a.  允许 null Key 或 Value

       b.  和 Hashtable 相比，不同点主要是 允许 null key value 和 非同步的

       c.   不保证顺序

       d.  capacity 不宜设置过大（load factor 不宜过小），会影响迭代时间复杂度

       e.  load factor 0.75 在时间和空间上做出了良好的折衷，

            更高的值能降低空间开销，但是增加查找成本

            提前预设合适的 capacity（load factor 一般不修改），能减少 rehash 的次数

       f.  iterator 是 fail-fast 的，迭代中被修改会抛出 ConcurrentModificationException

      g.  实现了序列化和克隆接口

      h.  桶里成员少的时候就拉链，成员太多，就改用 TreeNode 构造树结构，类似 TreeMap

           这种 Tree 默认采用 Hashcode 排序，但是如果被比较对象实现了 Comparable 接口，会使用该接口比较排序

           防止很多 Key 的 hashcode 相同时，造成查找 tree 构造出较差的结构

           TreeNode 会占用更多的存储空间，不是数据很多的情况不会启用， TREEIFY_THRESHOLD 设定阈值

           HashMap 会自动在 Plain bins 和 Tree bins 间切换，

When bin lists are treeified, split, or untreeified, we keep them in the same

relative access/traversal order to better preserve locality

      i.   初始大小 16，最大 2^30， tree mode 的阈值参数如下：

    /**
     * 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; // 树化，table 容量至少达到这个数，否则直接扩展 table

     j.  定义了 hash 函数，对 Key 的 hashcode 进一步处理，使分布更合理，高位 Bit 的影响附加到低位上

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

// 由此可见，null key 还是放在 tab[0] 位置

   k.   链模式 、树模式 图解

       

 l.  大于阈值时，table 数组扩为原来的 2 倍 

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { // pre-size
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)  // 是 大于 
                resize();
            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);
            }
        }
    }

m.  最快情况下的查找时间复杂度，从 O(n) 降低到了 O(log n)，（红黑树 vs 链表）