Java基础（五）-HashMap原理分析

HashMap绝对是Java基础的集合部分最重要的知识点之一了，网上文章也一抓一大把，也就不详细分析了，这里针对一些核心点简单做个小总结，以备之后查阅。

一、 HashMap 1.7版本介绍

1.1 数据结构

数据结构采用数组+单链表，以拉链法来解决hash冲突，其中数组元素和链表节点由Entry<K,V>实现，表示键值对。

1.2 重要参数

• initialCapacity：容量 默认2^4 最大2^30
• loadFactor：加载因子 默认0.75
• threshold：扩容阀值 = 容量 * 加载因子

扩容时机：
当hashmap中的元素个数超过扩容阀值，就会进行数组扩容，即扩大一倍，然后重新计算每个元素在数组中的位置，这个过程非常消耗性能，如果能预知容量大小，尽量手动设置initialCapacity。

加载因子：
默认为0.75，如果自定义要注意：
设置太大：空间利用率高（扩容次数少些）、但冲突的机会加大、查找效率变低（因为链表变长了）
设置太小：空间利用率小（扩容次数多些）、冲突的机会减小、查找效率高（链表不长）

1.3 put流程

  /**
    * 源码分析：主要分析： HashMap的put函数
    */
   public V put(K key, V value)
//若 哈希表未初始化（即 table为空)， 则初始化 数组table 
       if (table == EMPTY_TABLE) {
       inflateTable(threshold);
   } 
       // 判断key是否为空值null， 若key == null，则将该键-值 存放到数组table 中的第1个位置，即table [0]
       //（本质：key = Null时，hash值 = 0，故存放到table[0]中）
       // 该位置永远只有1个value，新传进来的value会覆盖旧的value
       if (key == null)
           return putForNullKey(value);
       // 这里首先了解3个概念：
      //hashCode：key对象的hashCode方法的返回值（若没有重写则默认用Object类的hashCode方法的生成值）
      //hash值：是在hashCode值的基础上又进行了一步运算后的结果，这个运算过程就是hash方法。
      //数组下标：根据该hash值和数组长度计算出数组下标。
      //若 key ≠ null，则根据键值key计算hash值
       int hash = hash(key);
       //根据hash值 最终获得 key对应存放的数组Table中位置
      // indexFor的计算是：h & (length-1）  
    //原因：hashMap的初始容量和扩容都是以2的次方来进行的，那么length-1换算成二进制的话肯定所有位都为1，
    // 所以h& (length-1)运算从数值上来讲其实等价于对length取模。那为什么要是2的N次方呢？以15为例，当数组
   //长度为15的时 候，hash值会与length-1（1110）进行按位与，那么最后一位永远是0, 结果是最后一位为1的位置
   //无法存储元素，造成浪费，也造成跟多碰撞。
       int i = indexFor(hash, table.length);
       //判断该key对应的值是否已存在（通过遍历 以该数组元素为头结点的链表 逐个判断）
       for (Entry<K,V> e = table[i]; e != null; e = e.next) {
           Object k;
           // 若该key已存在（即 key-value已存在 ），则用 新value 替换 旧value
           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
               return oldValue; //并返回旧的value
           }
       }
       modCount++;
       //若该key不存在，则将“key-value”添加到table中, 这时候会进行扩容判断
       addEntry(hash, key, value, i);
       return null;

     //链表的插入方式：头插法
     //扩容方式：达到扩容阀值 = 容量 * 加载因子，则double扩容，然后把之前元素重新计算下标插入
   }

1.4 get流程

/**
  * 源码分析
  */
  public V get(Object key) { 
   // 当key == null时，则到 以哈希表数组中的第1个元素（即table[0]）为头结点的链表去寻找对应 key == null的键
   if (key == null) 
       return getForNullKey(); 
   // 当key ≠ null时，去获得对应值
   Entry<K,V> entry = getEntry(key);
   return null == entry ? null : entry.getValue(); 
}

/**
  * 作用：当key ≠ null时，去获得对应值
  */ 
final Entry<K,V> getEntry(Object key) { 
   if (size == 0) { 
       return null; 
   } 
   // 根据key值，通过hash（）计算出对应的hash值
   int hash = (key == null) ? 0 : hash(key); 
   // 根据hash值计算出对应的数组下标
   // 遍历 以该数组下标的数组元素为头结点的链表所有节点，寻找该key对应的值
   for (Entry<K,V> e = table[indexFor(hash, table.length)];  e != null;  e = e.next) { 
       Object k; 
       // 若 hash值 & key 相等，则证明该Entry是我们要的键值对
       // 通过equals（）判断key是否相等
       if (e.hash == hash && 
           ((k = e.key) == key || (key != null && key.equals(k)))) 
           return e; 
   } 
   return null; 
}

二、HashMap 1.8新特性

这里简单列下几个核心改动：

数据结构死亡4连问：

1 为什么引入红黑树？

红黑树是一种自平衡二叉查找树，红黑树最坏查询效率为O(log(n)),而链表是O(n)。从查询效率上看红黑树是优于链表的，而当碰撞过多导致链表过长时，链表的查询效率就会降低，这时候引入红黑树目的为了提升此时的查询效率。

2 为什么不直接用红黑树替换链表？

链表插入效率为O(1)，而红黑树是O(log(n))。从插入效率上看链表是优于红黑树的，并且在元素不多的情况下，红黑树查询效率O(log(n))比较与链表的O(n)也没有很明显的优势，因此选择混合使用，以达到最优的性能表现。

3 为什么是红黑树（BR-Tree）而不是自平衡二叉查找树（AVL-Tree）？

平衡二叉树类型	平衡度	方式	调整频率	适用场景
AVL树	高	全局平衡	高	查询 > 增/删
红黑树	低	局部平衡	低	查询 <= 增/删

由于AVL高度平衡，因此AVL的查询效率更高；但是插入和删除引起失衡，RB-Tree开销更小，复衡效率更高；现在问题是需要解决链表的查询效率问题：
查询效率：链表 < BR < AVL 这俩都能满足，但是从开销角度看：AVL的全局平衡自然要比BR的大，因此综合考虑选红黑树。

4 为什么是到8才由链表转红黑树？为什么到6又转为链表？

先说为什么是8：

官方文档中的一段描述:

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](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:

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

当hashCode离散性很好的时候，树型bin用到的概率非常小，因为数据均匀分布在每个bin中，几乎不会有bin中链表长度会达到阈值。但是在随机hashCode下，离散性可能会变差，然而JDK又不能阻止用户实现这种不好的hash算法，因此就可能导致不均匀的数据分布。不过理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布，我们可以看到，一个bin中链表长度达到8个元素的概率为0.00000006，几乎是不可能事件。所以，之所以选择8，不是拍拍屁股决定的，而是根据概率统计决定的。

至于为什么到6才转为链表：这个也没有一个明确的答案，个人感觉就是把7当做一个链表和红黑树的过渡点，一是这个点的效率变化本身也不明显，二是作为一个缓冲带减少切换吧。

最后来一张1.8的元素插入整体流程图结束

jdk1.8 hashmap 元素插入流程

参考：
https://blog.csdn.net/zyywolf/article/details/101363793
https://www.jianshu.com/p/e136ec79235c
https://www.jianshu.com/p/e5c8a814c0ca
https://www.jianshu.com/p/8324a34577a0