HashMap源码解析 （HashMap类-变量）

1. 继承关系

• 继承关系图 - Cloneable 空接口，表示可以克隆。创建并返回 HashMap 对象的一个副本
  - Serializable 序列化接口。属于标记性接口。HashMap 对象可以被序列化和反序列化
  - AbstractMap 父类提供了 Map实现接口。以最大限度地减少实现此接口所需的工作

补充

通过上述继承关系我们发现一个很奇怪的现象，就是 HashMap 已经继承了AbstractMap 而 AbstractMap 类实现了Map 接口，那为什么 HashMap 还要在实现 Map 接口呢？同样在 ArrayList 中 LinkedLis 中都是这种结构
据 Java 集合框架的创始人 Josh Bloch 描述，这样的写法是一个失误。在 Java 集合框架中，类似这样的写法很多，最幵始写 Java 集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，jdk 的维护者，后来不认为这个小小的失误值得去修改，所以就这样保留下来了

2. 类内变量

package java.util;

import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;
import sun.misc.SharedSecrets;

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    //序列化版本号
    private static final long serialVersionUID = 362498820763181265L;

    //默认初始化容量(必须是 2 的 n 次幂）
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    //数组最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30; 

     //默认加载因子（默认：0.75）
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

     //默认转换红黑树的链表阈值（默认：8）  
    static final int TREEIFY_THRESHOLD = 8;

     //当链表的值小于 6 则会从红黑树转回链表
    static final int UNTREEIFY_THRESHOLD = 6;

    /*
      Map 里面的数量超过这个值时，表中的桶才能进行树形化，否则桶内元素太
      多时会扩容，而不是树形化为了避免进行扩容、树形化选择的冲突，
      这个值不能小于4*TREEIFY_THRESHOLD(8)
    */ 
    static final int MIN_TREEIFY_CAPACITY = 64;

    /* ---------------- Fields -------------- */

    /**
     用来存储键值对数组
     */
    transient Node<K,V>[] table;

    /**
    用来存储缓存
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     HashMap 中存放元素的个数，注意这个不等于数组的长度
     size 为 HashMap 中 K-V 的实时数量，不是数组 table 的长度
     */
    transient int size;

    /**
     用来记录 HashMap 的修改次数
     */
    transient int modCount;

    /**
     临界值 当实际大小（容量*负载因子）超过临界值时，会进行扩容
     */
    int threshold;

    /**
     加载因子
     */
    final float loadFactor;
}

3. 类变量解析

3.1 DEFAULT_INITIAL_CAPACITY
问题：为什么初始化容量必须是2的n次幂？

因为当向HashMap 中添加一个元素的时候，需要根据key 的 hash值，去确定其在数组中的具体位置。HashMap 为了存取高效，减少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现的关键就在于把数据存到哪个链表中的算法

这个算法实际就是取模，hash % length，计算机中直接求余效率不如位移运算。所以源码中做了优化，使用hash & (length - 1)，而实际上 hash % length等于 hash & ( length - 1),所以前提必须是 length是 2的n次幂

问题又来了：为什么这样就能均匀分布减少碰撞呢?

说明：按位与运算规则:相同的二进制数位上,都是1的时候,结果为1.否则为0；

例如: 如果数组长度是2的次幂
hash : 3  length数组长度 : 8(是)

3 & (8-1)

00000011  3
00000111  7
------------
00000011  3  索引


hash : 2  length数组长度 : 8(是)

2 & (8-1)

00000010  2
00000111  7
------------
00000010  2  索引

===============================================================

例如: 如果数组长度不是2的次幂
hash : 3  length数组长度 : 9(不是)

3 & (9-1)

00000011  3
00001000  8
------------
00000000  0  索引


hash : 2  length数组长度 : 9(不是)

2 & (9-1)

00000010  2
00001000  8
------------
00000000  0  索引

由上述代码总结: 如果数组长度不是2的次幂,计算出的索引特别容易相同,及其容易发生hash碰撞,导致其余数组空间很大程度上并没有存储数据,链表或者红黑树过长,效率降低

那么问题又又来了：我非要初始化容量不为2的次幂（列如：10），会发生什么？

当在实例化 HashMap 实例时，如果给定了 initialCapacity，由于 HashMap 的 capacity 必须都是 2 的次幂，因此调用tableSizeFor方法用于找到大于等于 initialCapacity 的最小的 2 的幂

static final int tableSizeFor(int cap) { //10

  /*
  int n = cap - 1; 防止 cap 已经是 2 的幂。如果 cap 已经是 2 的幂，又没有这个  减 1 操作，
  则执行完后面的几条无符号操作之后，返回的 capacity 将是这个 cap 的 2 倍
  */
  int n = cap - 1;
 
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}


/*
|   按位或运算规则: 相同的二进制数位上,都是0的时候,结果为0.否则为1
>>> 无符号右移  
*/

3.2 TREEIFY_THRESHOLD
问题：为什么 Map 桶中结点个数超过 8 才转为红黑树？
我们都知道，链表的时间复杂度是O(n)，红黑树的时间复杂度O(logn)，很显然，红黑树的复杂度是优于链表的，既然这么棒，那为什么hashmap为什么不直接就用红黑树呢?请看代码

Because TreeNodes are about twice the size of regular nodes, we use them only when bins
contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too
small (due to removal or resizing) they are converted back to plain bins.  In usages with
well-distributed user hashCodes, tree bins are rarely used.  Ideally, under random hashCodes, 
the frequency of nodes in bins follows a Poisson distribution 
(http://en.wikipedia.org/wiki/Poisson_distribution) 
with a parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, 
the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:

翻译：因为树结点的大小大约是普通结点的两倍，所以我们只在箱子包含足够的结点时才使用树结点(参见TREEIFY_THRESHOLD)。
当它们变得太小（由于删除或调整大小）时，就会被转换回普通的桶。在使用分布良好的用户 hashCode 时，很少使用树箱。
理想情况下，在随机哈希码下，箱子中结点的频率服从泊松分布
(http://en.wikipedia.org/wiki/Poisson_distribution) ，默认调整阈值为0.75，平均参数约为0.5，尽管由 
于调整粒度的差异很大。忽略方差，列表大小k的预朗出现次数是(exp(-0.5) * pow(0.5, k) / factorial(k))。 
第一个值是：

0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006
more: less than 1 in ten million

源码中的注释写的很清楚，因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。也就是说，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，综合考虑，认为只能在节点太多的时候，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树

为了配合使用分布良好的hashCode，树节点很少使用。并且在理想状态下，受随机分布的hashCode影响，链表中的节点遵循泊松分布，而且根据统计，链表中节点数是8的概率已经接近千万分之一，而且此时链表的性能已经很差了。所以在这种比较罕见和极端的情况下，才会把链表转变为红黑树。因为链表转换为红黑树也是需要消耗性能的，特殊情况特殊处理，为了挽回性能，权衡之下，才使用红黑树，提高性能。也就是大部分情况下，hashmap还是使用的链表，如果是理想的均匀分布，节点数不到8，hashmap就自动扩容了

综上所述,我们可以看到，一个桶中链表长度达到 8 个元素的槪率为 0.00000006，几乎是不可能事件。所以，之所以选择 8，不是随便決定的，而是裉据概率统计决定的。甶此可见，发展将近30年的 Java 每一项改动和优化都是非常严谨和科学的

也就是说：选择 8 因为符合泊松分布，超过 8 的时候，概率已经非常小了，所以我们选择 8 这个数宇
红黑树的平均查找长度是 log(n)，如果长度为 8，平均查找长度为 log(8) = 3，链表的平均查找长度为 n/2，当长度为 8 时，平均查找长虔为 8/2 = 4，这才有转换成树的必要；链表长度如果是小于等于 6， 6/2 = 3，而 log(6) = 2.6，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短

3.3 table

// 存储元素的数组 (必须是2的n次幂)
transient Node<K,V>[] table;

在 jdk1.8 中我们了解到HashMap 是由数组加链表加红黑树来组成的结构，其中table 就是HashMap中的数组，jdk8 之前数组类型是Entry<K,V> 类型。从 jdk1.8 之后是Node<K,V> 类型。只是换了个名字，都实现了一样的接口：Map.Entry<K,V>。负责存储键值对数据的

3.4 loadFactor

// 负载因子
final float loadFactor;

• loadFactor 是用来衡量 HashMap 满的程度，表示HashMap的疏密程度，影响 hash 操作到同一个数组位置的概率
• loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f是官方给出的一个比较好的临界值。
  当HashMap 里面容纳的元素已经达到HashMap 数组长度的 75% 时，表示 HashMap 太挤了，需要扩容，而扩容这个过程涉及到 rehash、复制数据等操作，非常消耗性能。所以开发中尽量减少扩容的次数，可以通过创建HashMap集合对象时指定初始容量来尽量避免

问题来了：为什么负载因子设置为0.75，初始化临界值是12？

threshold （阈值） 计算公式：capacity(数组长度默认16) *loadFactor(负载因子默认0.75）

loadFactor 越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，
loadFactor越小，也就是趋近于0，数组中存放的数据(entry)也就越少，也就越稀疏

负载因子是0.4。 那么16*0.4--->6 如果数组中满6个空间就扩容会造成数组利用率太低了。
负载因子是0.9。 那么16*0.9--->14 那么这样就会导致链表有点多了，导致查找元素效率低。

所以既兼顾数组利用率又考虑链表不要太多，经过大量测试 0.75 是最佳方案

阈值是当前已占用数组长度的最大值。当 Size >= threshold 的时候，那么就要考虑对数组的 resize(扩容)，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。 扩容后的 HashMap 容量是之前容量的两倍