HashMap源码探究之底“库”看穿

本是古典何须时尚 2024-03-23 21:55 47阅读 0赞

## 前言： ##

本次的源码探究会以jdk1.7和jdk1.8对比进行探究二者在HashMap实现上有的差异性，除此之外，还会简单介绍HashMap的hash算法的设计细节、jdk1.8中HashMap添加功能的整个流程、什么情况下会树化等源码设计知识。

## 一、HashMap介绍 ##

> HashMap是Java集合框架中的一种数据结构，它实现了Map接口，并基于哈希表（Hash Table）来存储键值对。下面这张是HashMap的继承关系图：![在这里插入图片描述][900009f79fcb42f09f776e5bf2b589b5.png_pic_center]

在HashMap中，每个键值对由一个键（key）和一个值（value）组成。键是唯一的，而值可以重复。

HashMap使用哈希函数将键映射到存储桶（bucket）中，每个存储桶存储着一个链表或红黑树的数据结构(jdk1.8)，用于解决哈希冲突。（`*哈希冲突是指不同的键经过哈希函数映射到相同的存储桶*`）

> 举个例子： 假如**x.hashCode().equals(y.hashCode()) == true**，那么HashMap中会将x与y放在同一个桶的链表（红黑树）上  
> ![在这里插入图片描述][77ccdd6d0d654c7ba1538e52dd8e45d0.png_pic_center]

## 二、HashMap与Hashtable ##

这是一个老生常谈的话题，HashMap和Hashtable都是hash表，二者又有什么区别？什么时候使用哪个更合适？

Map<Integer,Integer> hashMap = new HashMap<>(); // HashMap
    Map<Integer,Integer> hashTable = new Hashtable<>(); // Hashtable

### 1.使用场景 ###

> 结论：HashMap适合于单线程，Hashtable适合于多线程。

如果你要问为什么，那么我会告诉你在底层源码中Hashtable使用了大量的synchronized锁对方法进行修饰，而HashMap中就没有任何加锁的痕迹，所以我们可以得出一个结论，**`Hashtable是线程安全的，而HashMap是线程不安全的`**

### 2.差异 ###

*  散列码的计算方式不同

来看底层实现：

//Hashtable
    hash = key.hashCode();
    index = (hash & 0x7FFFFFFF) % tab.length;

// HashMap
    static final int hash(Object key) {
        
    	int h;
    	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    ......
    i = (n - 1) & hash // i就是index

一个很明显的差异就是Hashtable使用的是简单的算数+位运算，而我们的HashMap使用纯位运算！！！

这个是一个效率的提升，但是为什么这个位运算可以做到算数+位运算的效果，我文章后面会详细介绍到，一定要耐心看完。

*  HashMap与Hashtable前者可以存储null值作为key和value，后者则不能

直接上源码(以put()方法为例)：

//Hashtable
    public synchronized V put(K key, V value) {
        
       // Make sure the value is not null
       if (value == null) {
        
       throw new NullPointerException();
       }
       int hash = key.hashCode();
           ........
    }

对于，Hashtable他会在put之前判断key和value是否为空，为空就报异常（null.hashCode()也是空指针异常）。

然而你在HashMap中是找不到类似语句的，因为它来者不拒，实操代码：

public static void main(String[] args) {
        
            Map<Integer,Integer> hashMap = new HashMap<>(); // HashMap
            Map<Integer,Integer> hashTable = new Hashtable<>(); // Hashtable
    
            hashMap.put(null,null);
            System.out.println(hashMap.containsKey(null));
    
            hashTable.put(null,null);
        }

结果：  
![在这里插入图片描述][793ecbcfae834994bee56cb2a23f3486.png_pic_center]  
你会发现Hashtable直接空指针异常了，而我们的HashMap是返回的true。

那么问题来了，Hashtable为什么不可以存储null，而HashMap可以呢？？？

这就是一个经典的`二义性造成的歧义问题`。首先，我们需要明确一个问题，如果一个值为null可以拥有什么意义所在或者说null可以代表什么？？？答案很明显，`null == 未赋值(不存在) || null值，要么不存在要么就是本身的null意义`（有点类似于薛定谔的猫？！@.@）

而这个二义性问题主要是因为get()方法造成的，在单线程环境下，其实我们的HashMap本身是存在二义性问题的，但是可以忽略不看，为什么？？

首先，我们在HashMap中的get()方法如下：

public V get(Object key) {
        
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }

在其源码中，我们不难发现，这个返回的就是一个封装的Node<K,V> e要么为null，要么为不为null。

*  假如返回的Node对象是<K,V>=><null,null>，返回null，与预期结果一样，都为null
 *  假如返回的Node对象是<K,V>=><null，value>，返回value

但问题是<K,V>=><null,null>存在到底是存在还是不存在，我们也不得而知，虽然可以containsKey(key)获取，但是因为它的存在不影响单线程的执行，注意我说的**单线程环境**

那么问题来了，多线程环境下呢？ 同样的的，我们还是以<K,V>=><null,null>和<K,V>=><null，value>为例：多线程环境下，我们确实可以拿到null或者value，也可以通过containsKey()或者containsValue()来判断是否存在key== null 或者 value == null，但是我们需要注意到是**containsKey()/containsValue()与get()方法是无法做到** **`原子性的`**！！！这才是为什么Hashtable乃至现在常用的CurrentHashMap把null归为黑名单的真正理由！！！在多线程下，如果一个操作不是原子性的，那么就会引来线程安全问题，线程安全问题是我们多线程环境下最不想看到的，所以在这些线程安全的集合下，null就被放到黑名单了

*  最后我个人感觉很笨的是Hashtable不是大驼峰命名，大家编程不要学它（娱乐向）

## 三、HashMap的1.7版本和1.8版本比较 ##

### 1. 结构不同 ###

必须明确一点，jdk1.7中使用的是数组+链表，而jdk1.8中使用数组+链表/红黑树，前者使用的是头插法，后者使用的是尾插法，  
![96b3e483e63a4decaa3b22e59243c878.png_pic_center][]  
如果你去翻源码你会发现1.7中，put()方法的实现远没有1.8中的复杂。（不过1.8的也还好，认真看还是很简单的，和spring源码相比真的的不是一个量级）

> Hashtable  
> ![在这里插入图片描述][3260c68e32444b579de616a020a5ac3b.png]

> HashMap  
> ![在这里插入图片描述][59045b622be94ba68efc033a9ed5b2cd.png]

### 2. jdk1.7头插法的死链循环问题 ###

首先，用图来简单说1.7中的头插法过程  
![在这里插入图片描述][426c5b3eeef644439eed52799209b7a9.png]  
发生死链循环的3个必要条件：

*  多线程
 *  resize()扩容
 *  头插法

举个简单的图例：  
![在这里插入图片描述][5fa7591440bd424ebcdcc0a6e3b3caa1.png_pic_center]  
这个问题在1.8改成尾插法后就得到了解决，是如何解决的可以自己画一下。

## 四、HashMap中的散列码函数 ##

我个人觉得散列码函数是整个HashMap中中设计非常厉害的一个地方，完美运用上了位运算来实现了散列和效率的二者兼得！！！

### 1.HashMap中的hash算法 ###

hash算法源码：

static final int hash(Object key) {
        
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

我们需要带着下面这几个问题来进行学习：

### 2 HashMap为什么异或原数右移16位计算哈希值？ ###

在介绍为什么之前，可以先看一下这个值的计算结果示例：

0100 1110 1100 1001 0101 1111 1101 0000  原数
    
    0000 0000 0000 0000 0100 1110 1100 1001  原数>>>16
    
    0100 1110 1100 1001 0001 0001 0001 1001  异或

看到这里应该还不能凸显处右移和异或的精妙之处

我们在来看看，HashMap中的tab是如何进行插值的

if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    }else{
        
        //.....
    }

tab对这个hash值使用n-1【n:当前tab表容量】与hash进行了&运算

我们再来看看计算实例：

0100 1110 1100 1001 0001 0001 0001 1001 hash
    
      0000 0000 0000 0000 0000 0000 0000 1111 n-1
    
    & 0000 0000 0000 0000 0000 0000 0000 1001 index

通过这个实例，我们可以知道一切原由了，hash值的计算(hash^hash>>>16)，`这是因为右移16位是为了保护其高位特性`,在&运算中高位是会被0抹除掉的，所以就存在低位差距小但是高位差距大的hash值，导致桶碰撞的概率大，从而使数据没有分散存储起来,在后续取的时候.效率比较低。所我们保护高位数据,是为了降低桶的碰撞

举个例子，假如高位差距很大,低位差距很小,高位却被抹除了,就会导致桶的碰撞增加了，将高位和低位进行异或可以保留高位和低位的特性(异或的特点),从而使桶的碰撞发生减小！！！

使用hash值的目的是为了足够散从而导致每个位置都能存到数据，而不是一支独大！！！所以使用异或和右移是一项非常不错的选择，不仅保存了低位高位的特点，又能使hash值分布均匀，足够散列。

### 3 HashMap的hash算法为什么使用异或？ ###

使用异或也是为了保证数据不偏不倚，假如使用的是&，会往0上靠拢，假如使用的是|，那么会往1上靠拢，使用异或是两种情况都能走55开的概率

### 4 可以用%取余运算吗？ ###

理论上，可以使用hash值对tab的长度取余的，但是既然&操作能处理得到同样的效果，当然是&运算更好啦，位运算比直接除法效率快太多了。

> 可以简单说明一下，因为n一定是一个2的幂，所以n-1的二进制数一定是全1，对于&运算来说，全1就代表谁来了就是谁，&出来的结果是谁就是谁，也肯定在n的范围内，是公平的，并且由于hash值可以是这个范围内的任意随机值，所以刚刚好能做到每一个桶都有机会放上数据

## 五、 HashMap的加载因子 ##

### 1 什么是负载因子 ###

负载因子是HashMap中的元素存储数量与容量大小的比例。通常用公式：`负载因子 = 元素数量 / 容量 来表示`。负载因子的大小可以是一个小于等于1的正数

当hash表中的元素数量 / 容量 >负载因子这个阈值的时候，则会发生扩容，调整桶数量减少hash冲突。

### 2加载因子为什么是0.75？ ###

/**
    *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:
    *
    * 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
    *
    *
    * The load factor used when none specified in constructor.
    */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

java官方是这么说的。  
其实说中国话就是：

> 0.75是基于一个空间和时间上的一个权衡，
> 
> > 如果说这个因子过大，则会导致扩容时机后移，hash冲突的概率提升，节点插入的时间也随之过大
> 
> > 如果说这个因子过小，则回导致扩容时机前移，hash冲突概率减少。节点插入时间变快，但是随之而来的问题是大部分空间会被浪费掉。

### 3 加载因子可以调整吗？ ###

HashMap提供了一个构造器来方便调整，第一个参数为容量大小，第二个参数为负载因子

public HashMap(int initialCapacity, float loadFactor)

## 六、HashMap的容量 ##

### 1 初始容量 ###

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

### 2.初始容量如果不是2的次方呢？ ###

假设初始容量是n==15

0100 1110 1100 1001 0001 0001 0001 1001 hash
    
      0000 0000 0000 0000 0000 0000 0000 1110 n-1（15-1）
    
    & 0000 0000 0000 0000 0000 0000 0000 1000 index
    
    //无论如果计算0,2,4,6,8,10,12,14都没办法用上

再假设初始容量是n==17

0100 1110 1100 1001 0001 0001 0001 1001 hash
    
      0000 0000 0000 0000 0000 0000 0001 0000 n-1（17-1）
    
    & 0000 0000 0000 0000 0000 0000 0001 0000 index
    
    //无论如何计算只能放0001 0000号桶上

结论：  
由于初始容量不是二的次方，那么就会造成，在计算桶位置的时候，n-1的二进制数的某一位或者几位只能是0，而又因为与运算中，0&0== 0，0&1== 0，所以就会导致某几个桶将永远都不可能使用到，这样也增大了hash碰撞的概率。，hash碰撞的概率加大又会导致桶内所装的链表越来越长，自然也增加了遍历时间。（虽然有红黑树转化，但不过是减缓的作用，该吃效率还是得吃效率）

### 3.HashMap对于你输入非2的次方的数，会怎么样？ ###

public HashMap(int initialCapacity, float loadFactor) {
        
     ...
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
    
    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;
    }

假如你调用的构造器传的容量不是2的次方，内部会把这个数转化为大于这个数的最小2的次方的数来作为初始化容量大小，这个位运算过程也挺有意思的，建议去理解它并烂熟于心，指不定那条面试官要你写哈哈哈。

## 七、HashMaps树化 ##

### 1. 为什么链表长度为8的概率如此之低，还要去树化？ ###

还是那句话，在计算机中，概率在低，数据达到一定数量，也会发生不少，全球70亿人的0.0001%这个数量都不可忽视了，更何况在计算机的世界里面。

所以当存在许多条a.hash()==b.hash() , a.equals(b)==false这种性质的数据时，不树化来提升查找速度，纯遍历，那效率可想而知

### 2. 为什么不选择6进行树化? ###

我们看一下TreeNode的源码

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        
            TreeNode<K,V> parent;  // red-black tree links
            TreeNode<K,V> left;
            TreeNode<K,V> right;
            TreeNode<K,V> prev;    // needed to unlink next upon deletion
            boolean red;
           ........
    }

这是node节点，继承了Map.Entry

static class Node<K,V> implements Map.Entry<K,V> {
        
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }

对比发现：TreeNode每一个数都是一个TreeNode，正如官方所说的，TreeNode大概是普通节点的2倍，所以我们转换成树结构时会加大内存开销的。

我们会发现在加载因子没有修改的前提下，单一条链表的长度大于等于8的概率是非常的低的，所以我们选择8才树化，树化的频率还是很低的，HashMap整体性能受到影响还是比较小的。

如果选择6进行树化，虽然概率也很低，但是也比8大了一千倍，遇到组合Hash攻击时（让你每个链表都进行树化），也会遇到性能下降的问题。

> 我的个人猜想是：当极端概率的事件都发生了，就说明被攻击了，所以需要采用必要措施来进行防御

### 3. 为什么树化之后，当长度减至6的时候，还要进行反树化？ ###

长度为6时我们查询次数是6，而红黑树是3次，但是消耗了一倍的内存空间，所以我们认为，转换回链表是有必要的。

维护一颗红黑树比维护一个链表要复杂，红黑树有一些左旋右旋等操作来维护顺序，而链表只有一个插入操作，不考虑顺序，所以链表的内存开销和耗时在数据少的情况下是更优的选择

### 4. 为什么在JDK1.8中进行对HashMap优化的时候，把链表转化为红黑树的阈值是8,而不是7或者不是20呢？ ###

如果选择6和8（如果链表小于等于6树还原转为链表，大于等于8转为树），中间有个差值7可以有效防止链表和树频繁转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

还有一点重要的就是由于treenodes的大小大约是常规节点的两倍，因此我们仅在容器包含足够的节点以保证使用时才使用它们，当它们变得太小（由于移除或调整大小）时，它们会被转换回普通的node节点，容器中节点分布在hash桶中的频率遵循泊松分布，桶的长度超过8的概率非常非常小。所以作者应该是根据概率统计而选择了8作为阀值

## 后续 ##

JDK1.8的put()方法流程，有时间再补上

END 感谢阅读，本文章为个人学习笔记

[900009f79fcb42f09f776e5bf2b589b5.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/680a9ad0b0564929889f3c52e32443d6.png
[77ccdd6d0d654c7ba1538e52dd8e45d0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/dd2511d7aaca4d25a5ee377f2fdf0268.png
[793ecbcfae834994bee56cb2a23f3486.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/611cbc0cabc74c29a2336336ebcc8199.png
[96b3e483e63a4decaa3b22e59243c878.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/b845dad9419a467fa200fc173011d88a.png
[3260c68e32444b579de616a020a5ac3b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/f320558a59054aa3a7c1520876da87f3.png
[59045b622be94ba68efc033a9ed5b2cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/c761154efa664b2e83b9519611378dc1.png
[426c5b3eeef644439eed52799209b7a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/6f52a6d2ea7a4f7894785dc03e9ac63c.png
[5fa7591440bd424ebcdcc0a6e3b3caa1.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/e83bb8b63d2f4df89e78b012beb6e1f3.png