JDK1.8源码(七)——java.util.HashMap 类

　　本篇博客我们来介绍在 JDK1.8 中 HashMap 的源码实现，这也是最常用的一个集合。但是在介绍 HashMap 之前，我们先介绍什么是 Hash表。

1、哈希表

　　Hash表也称为散列表，也有直接译作哈希表，Hash表是一种根据关键字值（key - value）而直接进行访问的数据结构。也就是说它通过把关键码值映射到表中的一个位置来访问记录，以此来加快查找的速度。在链表、数组等数据结构中，查找某个关键字，通常要遍历整个数据结构，也就是O(N)的时间级，但是对于哈希表来说，只是O(1)的时间级。

　　比如对于前面我们讲解的 ArrayList 集合和 LinkedList ，如果我们要查找这两个集合中的某个元素，通常是通过遍历整个集合，需要O(N)的时间级。

　　如果是哈希表，它是通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表，只需要O(1)的时间级。

　　①、存放在哈希表中的数据是key-value 键值对，比如存放哈希表的数据为:

　　{Key1-Value1,Key2-Value2,Key3-Value3,Key4-Value4,Key5-Value5,Key6-Value6}

　　如果我们想查找是否存在键值对 Key3-Value3，首先通过 Key3 经过散列函数，得到值 k3，然后通过 k3 和散列表对应的值找到是 Value3。

　　②、当然也有可能存放哈希表的值只是 Value1,Value2,Value3这种类型：

　　{Value1,Value2,Value3,Value4,Value5,Value6}

　　这时候我们可以假设 Value1 是等于 Key1的，也就是{Value1-Value1,Value2-Value2,Value3-Value3,Value4-Value4,Value5-Value5,Value6-Value6}可以将 Value1经过散列函数转换成与散列表对应的值。

大家都用过汉语字典吧，汉语字典的优点是我们可以通过前面的拼音目录快速定位到所要查找的汉字。当给定我们某个汉字时，大脑会自动将汉字转换成拼音（如果我们认识，不认识可以通过偏旁部首），这个转换的过程我们可以看成是一个散列函数，之后在根据转换得到的拼音找到该字所在的页码，从而找到该汉字。

 　　汉语字典是哈希表的典型实现，但是我们仔细思考，会发现这样几个问题？

　　①、为什么要有散列函数？

　　②、多个 key 通过散列函数会得到相同的值，这时候怎么办？

　　对于第一个问题，散列函数的存在能够帮助我们更快的确定key和value的映射关系，试想一下，如果没有汉字和拼音的转换规则（或者汉字和偏旁部首的），给你一个汉字，你该如何从字典中找到该汉字？我想除了遍历整部字典，你没有什么更好的办法。

　　对于第二个问题，多个 key 通过散列函数得到相同的值，这其实也是哈希表最大的问题——冲突。比如同音字汉字，我们得到的拼音就会是相同的，那么我们该如何在字典中存放同音字汉字呢？有两种做法：

　　第一种是开放地址法，当我们遇到冲突了，这时候通过另一种函数再计算一遍，得到相应的映射关系。比如对于汉语字典，一个字 “余”，拼音是“yu”，我们将其放在页码为567(假设在该位置)，这时候又来了一个汉字“于”，拼音也是“yu”，那么这时候我们要是按照转换规则，也得将其放在页码为567的位置，但是我们发现这个页码已经被占用了，这时候怎么办？我们可以在通过另一种函数，得到的值加1。那么汉字"于"就会被放在576+1=577的位置。

　　第二种是链地址法，我们可以将字典的每一页都看成是一个子数组或者子链表，当遇到冲突了，直接往当前页码的子数组或者子链表里面填充即可。那么我们进行同音字查找的时候，可能需要遍历其子数组或者子链表。如下图所示：

　　对于开放地址法，可能会遇到二次冲突，三次冲突，所以需要良好的散列函数，分布的越均匀越好。对于链地址法，虽然不会造成二次冲突，但是如果一次冲突很多，那么会造成子数组或者子链表很长，那么我们查找所需遍历的时间也会很长。

　　关于哈希表的详细介绍，请点击这里。

2、什么是 HashMap？

　　听名字就知道，HashMap 是一个利用哈希表原理来存储元素的集合。遇到冲突时，HashMap 是采用的链地址法来解决，在 JDK1.7 中，HashMap 是由 数组+链表构成的。但是在 JDK1.8 中，HashMap 是由 数组+链表+红黑树构成，新增了红黑树作为底层数据结构，结构变得复杂了，但是效率也变的更高效。下面我们来具体介绍在 JDK1.8 中 HashMap 是如何实现的。

3、HashMap定义

　　HashMap 是一个散列表，它存储的内容是键值对(key-value)映射，而且 key 和 value 都可以为 null。

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

　　首先该类实现了一个 Map 接口，该接口定义了一组键值对映射通用的操作。储存一组成对的键-值对象，提供key（键）到value（值）的映射，Map中的key不要求有序，不允许重复。value同样不要求有序，但可以重复。但是我们发现该接口方法有很多，我们设计某个键值对的集合有时候并不像实现那么多方法，那该怎么办？

　　JDK 还为我们提供了一个抽象类 AbstractMap ，该抽象类继承 Map 接口，所以如果我们不想实现所有的 Map 接口方法，就可以选择继承抽象类 AbstractMap 。

　　但是我们发现 HashMap 类即继承了 AbstractMap 接口，也实现了 Map 接口，这样做难道不是多此一举？后面我们会讲的 LinkedHashSet 集合也有这样的写法。

　　毕竟 JDK 经过这么多年的发展维护，博主起初也是认为这样是有具体的作用的，后来找了很多资料，发现这其实完全没有任何作用，具体出处。

据 java 集合框架的创始人Josh Bloch描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。

　　HashMap 集合还实现了 Cloneable 接口以及 Serializable 接口，分别用来进行对象克隆以及将对象进行序列化。

4、字段属性

 1     //序列化和反序列化时，通过该字段进行版本一致性验证
 2     private static final long serialVersionUID = 362498820763181265L;
 3     //默认 HashMap 集合初始容量为16（必须是 2 的倍数）
 4     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 5     //集合的最大容量，如果通过带参构造指定的最大容量超过此数，默认还是使用此数
 6     static final int MAXIMUM_CAPACITY = 1 << 30;
 7     //默认的填充因子
 8     static final float DEFAULT_LOAD_FACTOR = 0.75f;
 9     //当桶(bucket)上的结点数大于这个值时会转成红黑树(JDK1.8新增)
10     static final int TREEIFY_THRESHOLD = 8;
11     //当桶(bucket)上的节点数小于这个值时会转成链表(JDK1.8新增)
12     static final int UNTREEIFY_THRESHOLD = 6;
13     /**(JDK1.8新增)
14      * 当集合中的容量大于这个值时，表中的桶才能进行树形化 ，否则桶内元素太多时会扩容，
15      * 而不是树形化 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
16      */
17     static final int MIN_TREEIFY_CAPACITY = 64;

　　注意：后面三个字段是 JDK1.8 新增的，主要是用来进行红黑树和链表的互相转换。

 1     /**
 2      * 初始化使用，长度总是 2的幂
 3      */
 4     transient Node<K,V>[] table;
 5 
 6     /**
 7      * 保存缓存的entrySet（）
 8      */
 9     transient Set<Map.Entry<K,V>> entrySet;
10 
11     /**
12      * 此映射中包含的键值映射的数量。（集合存储键值对的数量）
13      */
14     transient int size;
15 
16     /**
17      * 跟前面ArrayList和LinkedList集合中的字段modCount一样，记录集合被修改的次数
18      * 主要用于迭代器中的快速失败
19      */
20     transient int modCount;
21 
22     /**
23      * 调整大小的下一个大小值（容量*加载因子）。capacity * load factor
24      */
25     int threshold;
26 
27     /**
28      * 散列表的加载因子。
29      */
30     final float loadFactor;

　　下面我们重点介绍上面几个字段：

　　①、Node<K,V>[] table

　　我们说 HashMap 是由数组+链表+红黑树组成，这里的数组就是 table 字段。后面对其进行初始化长度默认是 DEFAULT_INITIAL_CAPACITY= 16。而且 JDK 声明数组的长度总是 2的n次方(一定是合数)，为什么这里要求是合数，一般我们知道哈希算法为了避免冲突都要求长度是质数，这里要求是合数，下面在介绍 HashMap 的hashCode() 方法(散列函数)，我们再进行讲解。

　　②、size

　　集合中存放key-value 的实时对数。

　　③、loadFactor

　　装载因子，是用来衡量 HashMap 满的程度，计算HashMap的实时装载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity。capacity 是桶的数量，也就是 table 的长度length。

　　默认的负载因子0.75 是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子loadFactor 的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子 loadFactor 的值，这个值可以大于1。

　　④、threshold

　　计算公式：capacity * loadFactor。这个值是当前已占用数组长度的最大值。过这个数目就重新resize(扩容)，扩容后的 HashMap 容量是之前容量的两倍

5、构造函数

　　①、默认无参构造函数

    /**
     * 默认构造函数，初始化加载因子loadFactor = 0.75
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }

View Code

　　无参构造器，初始化散列表的加载因子为0.75

　　②、指定初始容量的构造函数

 1     /**
 2      * 
 3      * @param initialCapacity 指定初始化容量
 4      * @param loadFactor 加载因子 0.75
 5      */
 6     public HashMap(int initialCapacity, float loadFactor) {
 7         //初始化容量不能小于 0 ，否则抛出异常
 8         if (initialCapacity < 0)
 9             throw new IllegalArgumentException("Illegal initial capacity: " +
10                                                initialCapacity);
11         //如果初始化容量大于2的30次方，则初始化容量都为2的30次方
12         if (initialCapacity > MAXIMUM_CAPACITY)
13             initialCapacity = MAXIMUM_CAPACITY;
14         //如果加载因子小于0，或者加载因子是一个非数值，抛出异常
15         if (loadFactor <= 0 || Float.isNaN(loadFactor))
16             throw new IllegalArgumentException("Illegal load factor: " +
17                                                loadFactor);
18         this.loadFactor = loadFactor;
19         this.threshold = tableSizeFor(initialCapacity);
20     }
21     // 返回大于等于initialCapacity的最小的二次幂数值。
22     // >>> 操作符表示无符号右移，高位取0。
23     // | 按位或运算
24     static final int tableSizeFor(int cap) {
25         int n = cap - 1;
26         n |= n >>> 1;
27         n |= n >>> 2;
28         n |= n >>> 4;
29         n |= n >>> 8;
30         n |= n >>> 16;
31         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
32     }

View Code

6、确定哈希桶数组索引位置

　　前面我们讲解哈希表的时候，我们知道是用散列函数来确定索引的位置。散列函数设计的越好，使得元素分布的越均匀。HashMap 是数组+链表+红黑树的组合，我们希望在有限个数组位置时，尽量每个位置的元素只有一个，那么当我们用散列函数求得索引位置的时候，我们能马上知道对应位置的元素是不是我们想要的，而不是要进行链表的遍历或者红黑树的遍历，这会大大优化我们的查询效率。我们看 HashMap 中的哈希算法：

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    i = (table.length - 1) & hash;//这一步是在后面添加元素putVal()方法中进行位置的确定

　　主要分为三步：

　　①、取 hashCode 值： key.hashCode()

　　②、高位参与运算：h>>>16

　　③、取模运算：(n-1) & hash

　　这里获取 hashCode() 方法的值是变量，但是我们知道，对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(Object key) 所计算得到的 hash码 值总是相同的。

　　为了让数组元素分布均匀，我们首先想到的是把获得的 hash码对数组长度取模运算( hash%length)，但是计算机都是二进制进行操作，取模运算相对开销还是很大的，那该如何优化呢？

　　HashMap 使用的方法很巧妙，它通过 hash & (table.length -1)来得到该对象的保存位，前面说过 HashMap 底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当 length 总是2的n次方时，hash & (length-1)运算等价于对 length 取模，也就是 hash%length，但是&比%具有更高的效率。比如 n % 32 = n & (32 -1)

　　这也解释了为什么要保证数组的长度总是2的n次方。

　　再就是在 JDK1.8 中还有个高位参与运算，hashCode() 得到的是一个32位 int 类型的值，通过hashCode()的高16位 异或 低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

　　下面举例说明下，n为table的长度：

7、添加元素

 1     //hash(key)就是上面讲的hash方法，对其进行了第一步和第二步处理
 2     public V put(K key, V value) {
 3         return putVal(hash(key), key, value, false, true);
 4     }
 5     /**
 6      * 
 7      * @param hash 索引的位置
 8      * @param key  键
 9      * @param value  值
10      * @param onlyIfAbsent true 表示不要更改现有值
11      * @param evict false表示table处于创建模式
12      * @return
13      */
14     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
15             boolean evict) {
16          Node<K,V>[] tab; Node<K,V> p; int n, i;
17          //如果table为null或者长度为0，则进行初始化
18          //resize()方法本来是用于扩容，由于初始化没有实际分配空间，这里用该方法进行空间分配，后面会详细讲解该方法
19          if ((tab = table) == null || (n = tab.length) == 0)
20              n = (tab = resize()).length;
21          //注意：这里用到了前面讲解获得key的hash码的第三步，取模运算，下面的if-else分别是 tab[i] 为null和不为null
22          if ((p = tab[i = (n - 1) & hash]) == null)
23              tab[i] = newNode(hash, key, value, null);//tab[i] 为null，直接将新的key-value插入到计算的索引i位置
24          else {//tab[i] 不为null，表示该位置已经有值了
25              Node<K,V> e; K k;
26              if (p.hash == hash &&
27                  ((k = p.key) == key || (key != null && key.equals(k))))
28                  e = p;//节点key已经有值了，直接用新值覆盖
29              //该链是红黑树
30              else if (p instanceof TreeNode)
31                  e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
32              //该链是链表
33              else {
34                  for (int binCount = 0; ; ++binCount) {
35                      if ((e = p.next) == null) {
36                          p.next = newNode(hash, key, value, null);
37                          //链表长度大于8，转换成红黑树
38                          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
39                              treeifyBin(tab, hash);
40                          break;
41                      }
42                      //key已经存在直接覆盖value
43                      if (e.hash == hash &&
44                          ((k = e.key) == key || (key != null && key.equals(k))))
45                          break;
46                      p = e;
47                  }
48              }
49              if (e != null) { // existing mapping for key
50                  V oldValue = e.value;
51                  if (!onlyIfAbsent || oldValue == null)
52                      e.value = value;
53                  afterNodeAccess(e);
54                  return oldValue;
55              }
56          }
57          ++modCount;//用作修改和新增快速失败
58          if (++size > threshold)//超过最大容量，进行扩容
59              resize();
60          afterNodeInsertion(evict);
61          return null;
62     }

View Code

　　①、判断键值对数组 table 是否为空或为null，否则执行resize()进行扩容；

　　②、根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，