HashMap源码分析 (基于JDK1.8)

HashMap

本文讲解的HashMap以及源代码都是基于JDK1.8

背景引入

数组

优：读取修改快                        劣：增加删除慢
原因：数组可以根据下标直接定位到指定位置的数据进行读取和修改，但增加和删除需要开辟一个新数组并移动增加和删除后的数据到新数组并返回。

链表

优：增加删除快                        劣：读取修改慢
原因：链表增加和删除只需断开指定位置的两端节点，但读取的时候只能从头/尾开始往另一方向读取。
拓展知识点：
数组和链表迭代的方式不同 ArrayList实现了RandomAccess接口 这是一个标记接口，标注是否可以随机访问 ArrayList使用数组实现，可以随机访问 经过测试 使用for循环遍历ArrayList更快 而LinkedList没有实现这个RandomAccess接口 不支持随机访问，使用迭代器遍历更快 RandomAccess接口的作用。
正是数组和链表各有各的优势，所以引入了散列表，结合了两者的优势尽可能的降低劣势带来的影响。

简介

Hash

哈希：英文是Hash，也称为散列 基本原理就是把任意长度输入，转化为固定长度输出 这个映射的规则就是Hash算法，而原始数据映射的二进制串就是Hash值
Hash特点：

• 从Hash值不可以反向推导出原始数据 （因为异或的缘故无法反推）
  
• 输入数据的微小变化会得到完全不同的Hash值相同的数据一定可以得到相同的值
  
• 哈希算法的执行效率要高效，长的文本也能快速计算Hash值
  
• Hash算法的冲突概率要小
  

HashMap

HashMap ，是一种散列表，用于存储 key-value 键值对的数据结构，每一个键值对也叫做Entry，一般翻译为“哈希表”，提供平均时间复杂度为 O(1) 的、基于 key 级别的 get/put 等操作。

类图

双列集合定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap

下面针对各个实现类的特点做一些说明：
(1) HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
(2) Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。
(3) LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。
(4) TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。
对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。

存储结构

HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的

改变链表结构的默认条件：1. 单链表中的元素个数大于8时  2. 桶数组中的元素个数大于64时 【二者满足其一即可】

table数组是一个Node [] table的数组，存放node节点（Node是HashMap的一个内部类）

1. static class Node<K,V> implements Map.Entry<K,V> {
2.     final int hash;    //当前节点经过hash扰动函数和路由算法后的值（存放位置的下标）
3.     final K key;
4.     V value;
5.     Node<K,V> next;   //下一个node节点
7.     Node(int hash, K key, V value, Node<K,V> next) { ... }
8.     public final K getKey(){ ... }
9.     public final V getValue() { ... }
10.     public final String toString() { ... }
11.     public final int hashCode() { ... }
12.     public final V setValue(V newValue) { ... }
13.     public final boolean equals(Object o) { ... }
14. }

复制代码

Hash存储过程

比较简单的描述，详细的可以看put方法流程图

以存储该键值对为例

1. map.put("侦探","conan");

复制代码

① 系统将调用”侦探”这个key的hashCode()方法得到其hashCode 值（该方法适用于每个Java对象），
② 然后再通过Hash算法的后两步运算（高位运算 (扰动函数) 和取模运算 (路由算法) ）来定位该键值对的存储位置

Hash冲突

由来：不同的数据经过hash扰动函数hash( )、路由算法 ( hash(x) & (n-1) ) 后得到的值可能相同，此时就会存到同一个桶位，这就叫hash冲突。
解决hash冲突方法：

• 开放寻址法
  
• 链表法（JDK1.8使用链表+红黑树）
  当不同的数据经过hash算法后到达同一个桶位，该桶内的数据就会链化。拉链法的链子就会很长，那么就会降低查找速度。
  

此时桶数组小了容易发生hash冲突，hash算法要是区分数据不明显也会导致hash冲突，所以仅仅时靠链表法来缓解hash冲突是不够的，也需要号的hash算法以及扩容机制来预防hash冲突。

Hash算法

hash算法包括hash扰动函数以及路由算法。Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。
Hash扰动函数

作用：分散hashcode，使相似的数据有着截然不同的hash值

1. //hash扰动函数：加入了对高16位的特征，更见分散hash值
2. //(h = key.hashCode()) ^ (h >>> 16)：拿自己本身和本身右进制16位后的数组做异或运算，得到的数字就带有高16位的特征
3. //疑问：为什么不直接使用整个hash而是要得到前16位为0的数字？（整合hash就包括本身的高低16位数的特征）
4. //答案：因为hashcode的数据类型是int，有符号位所以int在正数范围内是16位。所以需要hash得到一个16的数字
5. static final int hash(Object key) {
6.     int h;        //key对于的hashcode值
7.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
8. }

复制代码

代码中的h>>>16就是jdk1.8新引入的高位运算算法，作用：使hashcode的高位数字特征也能一并体现再hashcode中，更加分散hash值。通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
n为table长度

路由算法

jdk1.8没有封装成方法，而是直接使用以下公式

1. h & (table.length-1); //h是前面hash扰动得到的值

复制代码

HashMap扩容

注意点：JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是JDK1.8不会倒置 （具体可以看下文的Resize方法讲解）

先了解几个源码变量：

1. //当前hash表中实际存在的元素个数
2. transient int size;
4. //当前hash表的结构修改次数（注意：改查不算结构修改，增删才算结构修改）
5. transient int modCount;
7. //扩容阈值：当hash表中的元素超过该值时，触发扩容【通过赋值因子计算得来：threshold=loadFactor * capacity】 capacity是桶数组长度
8. int threshold;
10. //负载因子【默认0.75】
11. final float loadFactor;

复制代码

Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。
threshold扩容阈值就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择。（一般情况不修改，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1）
在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)（如何保证为2的n次方下面构造方法有讲），这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。

必须为2的n次方的HashMap非常规设计目的：为了在取模 (路由算法) 和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了 (扰动函数) 高位参与运算的过程。
路由算法优化：因为要提升性能 &比%快，所以只有当容量n为2的n次方时，(n - 1) & hash == hash % (n - 1) 才成立！
扩容优化：扩容的时候方便数据迁移。（具体如何方便后文有讲）

Hash源码

构造函数

小结：扩容是一个特别耗性能的操作，所以在创建hashmap的时候尽量估算capacity容量

先认识以下变量（和前面扩容认识的变量一样）

1. //桶数组
2. transient Node<K,V>[] table;
4. //键值对对象
5. transient Set<Entry<K,V>> entrySet;
7. //当前hash表中实际存在的元素个数
8. transient int size;
10. //当前hash表的结构修改次数（改查不算结构修改，增删才算结构修改）
11. transient int modCount;
13. //扩容阈值：当hash表中的元素超过该值时，触发扩容【通过赋值因子计算得来：threshold=loadFactor * capacity】 capacity是桶数组长度
14. int threshold;
16. //负载因子
17. final float loadFactor;

复制代码

四种构造方法
[code]//指定容量和负载因子构造public HashMap(int initialCapacity, float loadFactor) {    //1. 做校验：    //1.1 容量合法 容量要在0~最大值内    //1.2 负载因子必须大于0    if (initialCapacity < 0)        throw new IllegalArgumentException("Illegal initial capacity: " +                                           initialCapacity);    if (initialCapacity > MAXIMUM_CAPACITY)        initialCapacity = MAXIMUM_CAPACITY;    if (loadFactor