HashMap源码分析(一)

如果要选择一个在 java 开发者心目中使用最多的工具,我想 HashMap 必定榜上有名. 我们在日常开发、面试中，hashMap 已经成为一个常客。同时作为 Doug Lea 的神作，我想我们很有必要仔仔细细钻研它的具体实现，因为 hashMap 的具体实现有很多值得我们学习的东西。在面试中真正能看出一个候选人的功底深厚的往往是细节，本文我们会立足 hashMap 源码，和读者朋友们一起欣赏这一神作。使读者在感叹作者强悍的编程功底之外，能学习到一些大神的设计思路。

本文是 HashMap 系列的第一篇文章，我们先从宏观上了解 HashMap 的数据结构定义以及内部的属性定义、同时介绍了几种比较重要的内部类。

因为 HashMap 本质上是一种散列表数据结构，所以我们在脑海中一定要 HashMap 的数据结构图，站在宏观的角度去感受 HashMap。

图①

数据结构说明

由图可知 hashMap 是由 "数组 + 链表 + 红黑树" 组成的。当我们使用 HashMap 的 put(key,value) 方法将一个映射存入 hashMap 的时候，首先根据 key 计算出它的 hash 值，然后对数组 table 长度取模得到应该插入的位置(HashMap 在实际获取插入位置不是采用取模的方式，而是采用更加高效的位运算，我们后面会说到)。因为 table 的长度是有限的，但是插入数据是无限的，在有限的数组长度中保存无限的数据，必然会存在 hash 冲突，也就是多个 key 计算出来的数组位置是相同的。如果发生 hash 冲突，就会将映射存储在数组后面的链表中，当链表的长度超过一定的阈值就会转化成红黑树来存储。

类定义

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

HashMap 实现了 Map 接口，由此可知 HashMap 是一个映射表，同时也实现了 Cloneable、和 Serializable 标识接口、证明其可以克隆和序列化。关于克隆和序列化我们后面会说到。

类属性定义

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  static final float DEFAULT_LOAD_FACTOR = 0.75f;

DEFAULT_LOAD_FACTOR 是默认的加载因子，当哈希表中映射个数大于等于 > 加载因子*容量时候，就会发生扩容，减少 hash 冲突的概率。这个值是一个 tradeOff 值，在内存占用和查找效率做了均衡。

DEFAULT_INITIAL_CAPACITY 是哈希表数组的默认初始化容量。 这里使用 1 << 4 也就是 2^4 = 16，注意哈希表的数组的长度必须是 2 的幂次方，我们后文会说为什么这么规定。

这里可能有一些面试官会问 hashMap 的默认初始化容量为啥是 16 呢？为什么负载因子要设置为 0.75？我们都知道 HashMap 数组长度被设计成 2 的幂次方(下面会讲)，那为什么初始容量不设计成 4、8 或者 32....其实这是 JDK 设计者经过权衡之后得出的一个比较合理的数字，如果默认容量是 8 的话，当添加到第 6 个元素的时候就会触发扩容操作，扩容操作是非常消耗 CPU 的，32 的话如果只添加少量元素则会浪费内存，因此设计成 16 是比较合适的，负载因子也是同理。

这里需要说明一下，对于 2 的幂，在计算机的世界里是一群特殊的存在，它们的二进制中只有一个 1，其余位全为 0 。这个特性会影响与它进行位运算后的结果具有一些特殊效果。

 static final int MAXIMUM_CAPACITY = 1 << 30;

因为哈希表的容量最大值是整数，而且必须是 2 的幂次方。int 的最高位固定是 0，所以 int 最大值只能是所以最大值只能 0100 0000 0000 0000 0000 0000 0000 0000 也就是 1<<30

 0000 0000 0000 0000 0000 0000 0000 0001  1 0100 0000 0000 0000 0000 0000 0000 0000  1 << 30

 static final int TREEIFY_THRESHOLD = 8;

随着插入元素越来越多, 当发生 hash 冲突的时候，hashMap 会采用拉链法解决冲突，但是随着链表越来越长，查询性能会变差，故链表长度达到一定的条件会转化为红黑树，以此来保证稳定的查询性能。 其中一个条件就是链表长度达到一定阈值，这个阈值就是 TREEIFY_THRESHOLD，默认为 8,另一个条件就是 MIN_TREEIFY_CAPACITY 属性定义的。

 static final int MIN_TREEIFY_CAPACITY = 64;

在进行链表转红黑树的时候，第一步是检查链表的长度是否大于等于 8，第二步会检查 table 数组的容量是否小于此数值，若小于，则取消转为红黑树，只对 table 数组进行扩容。

 static final int UNTREEIFY_THRESHOLD = 6;

当键值对数量过多时需要对 table 数组进行扩容，并且将每个键值对放到新的数组中（或者不变）。原来的数组的内部结构有可能是链表，也有可能是红黑树，经过一番洗牌之后，如果数组结构为红黑树的键值对数量过低，就会重新转变为链表。低到哪个程度呢？就是这个字段对应的大小。

成员属性定义

 transient Node<K,V>[] table;

此属性是 hashMap 内部存储映射的地方。是一个 Node 类型的数组，在第一次使用的进行初始化，必要时候进行扩容操作，也称为哈希表。

 transient Set<Map.Entry<K,V>> entrySet;

HashMap 内部有一个内部类叫做 EntrySet、他其实是对 HashMap 的一种扩展，使得其可以被当做 Set 去使用、相当于提供了 HashMap 的一种集合视图，而 Set 的每一个元素是 Map.Entry 这个内部接口类型，具体实现是 Node 类型。而 entrySet 就是保存了已经实例化好的 EntrySet 对象，相当于缓存了这个一份 HashMap 的集合视图，使其可以很方便的直接当做 Set 去使用。

 transient int size;

size 是 HashMap 中映射的个数，注意这里是所有的映射个数，包括数组部分以及数组后面的链表和红黑树的总和。

 transient int modCount;

modCount 用于记录 HashMap 的修改次数, 在 HashMap 的 put(),get(),remove(),Interator()等方法中,都使用了该属性,由于 HashMap 不是线程安全的,所以在迭代的时候,会将 modCount 赋值到迭代器的 expectedModCount 属性中,然后进行迭代, 如果在迭代的过程中 HashMap 被其他线程修改了,modCount 的数值就会发生变化, 这个时候 expectedModCount 和 ModCount 不相等, 迭代器就会抛出 ConcurrentModificationException()异常

 final float loadFactor;

final 类型的 loadFactor，证明在实例化时候就一定会被赋值，存储 hashMap 的加载因子。一般从构造函数中指定，如果不指定默认为 DEFAULT_LOAD_FACTOR

 int threshold;

次属性代表了 hashMap 进行扩容的阈值，当 hashMap 中的映射大于此值得时候，就会启动 resize 过程。次属性是通过 capacity * load factor 计算出来的。

hashMap 的构造器

 //构造器1
 public HashMap() {
     this.loadFactor = DEFAULT_LOAD_FACTOR; //① 这里只是设置了加载因子，由此可见默认的构造器没有对Node数组进行初始化。
 }
 //构造器2
 public HashMap(int initialCapacity) {
     this(initialCapacity, DEFAULT_LOAD_FACTOR);//② 调用重载的构造器 
 }
 //构造器3
 public HashMap(int initialCapacity, float loadFactor) {
     if (initialCapacity < 0)
       throw new IllegalArgumentException("Illegal initial capacity: " +
                                          initialCapacity);
     if (initialCapacity > MAXIMUM_CAPACITY)
       initialCapacity = MAXIMUM_CAPACITY;
     if (loadFactor <= 0 || Float.isNaN(loadFactor))
       throw new IllegalArgumentException("Illegal load factor: loadFactor");
     this.loadFactor = loadFactor;
     this.threshold = tableSizeFor(initialCapacity);
 }

带参构造方法 3 主要做的就是对 initialCapacity 和 loadFactor 的校验工作，并且会通过 tableSizeFor 方法计算其合理的初始容量，通过将指定的 initialCapacity 进行规格化，使其变成大于等于 initialCapacity 的最小的 2 的幂次方,由于此时 table 数组尚未实例化，所以该合理的初始容量被暂存在 threshold 属性中，tableSizeFor 方法的源码如下。

 static final int tableSizeFor(int cap) {
     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;
 }

tableSizeFor (int cap) 静态方法 的作用是计算 大于等于手动指定的数值 cap 且最接近的 2 的整数次幂的数。

参数 cap 的值肯定大于 0，故 n 大于等于 0 ，假设 n = 0，经过右移之后，依旧为 0 ，0 与 0 异或依旧为 0 ，通过 return 语句的 n+ 1 计算得 1，即 2 的 0 次幂。

当 n 大于 0 时，n 的二进制位肯定会有位的值为 1，即 001xx..xx 的形式，接着，对 n 右移 1 位得 0001xx..xx，再进行位或，由于 1 与 0 或 1 异或结果都为 1，所以结果必为 0011xx..xx 的形式。以此类推，位移 2 位、4 位、8 位、 16 位，最终该算法能让最高位的 1 后面的所有位全变为 1

下面用一个例子距离说明：

让cap-1再赋值给 n 的目的是另找到的目标值大于或等于原值。例如二进制 1000，十进制数值为 8。如果不对它减 1 而直接操作，将得到答案 10000，即 16。显然不是结果。减 1 后二进制为 111，再进行操作则会得到原来的数值 1000，即 8。通过一系列位运算大大提高效率。

hashMap 的重要的内部类

由 HashMap 的数据结构图可知 hashMap 内部是一个 Node 类型的数组。从代码①处可知数组的每一项都有一个 Next 指针指向下一个 Node 节点，据此可以看出 HashMap 内部默认采用拉链法解决 hash 冲突。

 static class Node<K,V> implements Map.Entry<K,V> {
     final int hash;
     final K key;
     V value;
     Node<K,V> next;//① 
 ​
     Node(int hash, K key, V value, Node<K,V> next) {
         this.hash = hash;
         this.key = key;
         this.value = value;
         this.next = next;
     }
 ​
     //其他代码。。。
 }

上文说过 HashMap 内部是一个 Node 类型的数组，当发生 hash 冲突时候，采用拉链法解决冲突，但是当链表长度大于一定阈值导致查找性能降低，所以在 jdk1.8 中为了优化查找性能，会将链表转化成一颗红黑树，红黑树的定义就是这里的 TreeNode，实际上他也是一个 Node 类型，他继承了 LinkedHashMap.Entry<K,V>，而 LinkedHashMap.Entry<K,V>又继承了 HashMap.Node<K,V>。

 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
     TreeNode<K,V> parent;  
     TreeNode<K,V> left;
     TreeNode<K,V> right;
     TreeNode<K,V> prev;    
     boolean red;
     //其他代码。。。
 }

由于红黑树相比于链表占用了两倍的存储空间，所以我们仅仅在链表容量足够大的时候才会将链表在转化为红黑树，同样的当链表在 resize 之后又变得足够的小，我们又会将红黑树重新转回链表. 通常来说在一个设计良好的 hash 函数，红黑树是很少用到的。理想情况下，在随机 hashCodes 下，容器中节点的频率遵循泊松分布(http://en.wikipedia.org/wiki/Poisson_distribution)，在默认的加载因子是 0.75 情况下，泊松分布的平均参数约为 0.5。忽略方差，列表大小 k 的期望出现次数是 exp(-0.5) * pow(0.5, k) / factorial(k)

在上文我们说到 entrySet 变量的时候，我们提到过有一个内部类提供了 HashMap 的功能扩展，提供了一个集合视图方便使用者进行迭代等操作，这个内部类定义如下。

  final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
     public final int size()                 { return size; }
     public final void clear()               { HashMap.this.clear(); }
     public final Iterator<Map.Entry<K,V>> iterator() {
         return new EntryIterator();
     }
     //其他代码。。。
 }

限于篇幅的关系，我们第一篇就先到这里，下一篇我们会挑选 HashMap 内部几个核心的方法，在细节中细细琢磨 HashMap 的设计之美。