【JavaSE】深入HashMap

ゝ一纸荒年。 2024-03-27 15:33 70阅读 0赞

#### 文章目录 ####

*  1. HashMap概述
 *  2. 哈希冲突
 *  3. 树化与退化
 *   *  3.1 树化的意义
     *  3.2 树的退化
 *  4. 二次哈希
 *  5. put方法源码分析
 *  6. key的设计
 *  7. 并发问题

> 参考
> 
>  *  [如何防止因哈希碰撞引起的DoS攻击\_hashmap dos攻击\_双子孤狼的博客-CSDN博客][DoS_hashmap dos_-CSDN]
>  *  [ 为什么 HashMap 要用 h^(h ＞＞＞16) 计算hash值？槽位数必须是 2^n?\_一行Java的博客-CSDN博客][_ HashMap _ h_h _16_ _hash_ 2_n_Java_-CSDN]
>  *  [HashMap面试，看这一篇就够了\_苦味代码的博客-CSDN博客][HashMap_-CSDN]

## 1. HashMap概述 ##

`HashMap`是Java中最常用的集合框架。

在JDK1.7的时候，`HashMap`的底层**由数组和链表组成**。数组是`HashMap`的主体，而链表是为了解决哈希冲突而存在的。

![image-20230203164757901][]

在JDK1.8的时候，`HashMap`的底层**由数组、链表和红黑树组成**。红黑树的出现是为了解决因哈希冲突导致的链表长度过长影响`HashMap`性能的问题。红黑树搜索的空间复杂度为`O(logn)`，而链表却是`O(n)`。

也就是当链表的长度达到一定长度后，链表就会进行树化，当然这是一种笼统说法，具体细节待会深究。

![img][]

--------------------

## 2. 哈希冲突 ##

**哈希冲突是指对不同的关键字通过一个哈希函数进行计算得出相同的哈希值**，这样使得它们存在的数组时候发生了冲突。

解决哈希冲突通常有以下四种方法。

*  **开放定址法**

开放定址法，也称为再散列地址法。基本思想就是，如果`p=H(key)`出现冲突时，则以`p`为基础，再次`hash`，`p1=H(p)`,如果`p1`再次出现冲突，则以`p1`为基础，以此类推，直到找到一个不冲突的哈希地址`pi`。

就是说当发生哈希冲突的时候，对哈希值进行求哈希值，只要哈希表足够大，那么总能找到一个这样的空地址。

**因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素。**

*  **再哈希法**

再哈希法，也称双重散列，多重散列。基本思想就是提供多个不同的哈希函数，当`R1=H1(key1)`发生冲突时，再计算`R2=H2(key1)`，直到没有冲突为止。**这样做虽然不易产生堆集，但增加了计算的时间。**

*  **链地址法**

链地址法，也称拉链法，将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。

*  **建立公共溢出区**

将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

而`HashMap`采用的就是链地址法。

并且JDK1.7和JDK1.8的链表插入节点时，采用的方式不一样

1.  JDK1.7采用的是头插法。
2.  JDK1.8采用的是尾插法。

--------------------

## 3. 树化与退化 ##

树化是指将链表转化为红黑树的过程。

在JDK1.8的`HashMap`中，树化的规则是这样的：**当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度，如果数组容量已经 >=64，才会进行树化**

所以，`HashMap`并不是一开始就进行树化的。

阈值设置为8主要是因为泊松分布，具体原因`HashMap`作者在源码中也有解释

![image-20230203172039652][]

意思就是说，**理想情况下使用随机的哈希码，容器中节点分布在 hash 桶中的频率遵循泊松分布，按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表，可以看到链表中元素个数为 8 时的概率已经非常小**，再多的就更少了，所以原作者在选择链表元素个数时选择了 8，是根据概率统计而选择的。

也就是说哈希 值如果足够随机，则在 哈希表内按泊松分布，在负载因子 0.75 的情况下，长度超过 8 的链表出现概率是 0.00000006，树化阈值选择 8 就是为了让树化几率足够小。

--------------------

### 3.1 树化的意义 ###

**首先，树化成红黑树可以避免DOS攻击，防止链表超长时性能下降，树化应当是偶然情况，是保底策略。**

> DOS攻击是指恶意的攻击者通过使用以下精心构造的数据，使得所有数据经过哈希函数之后，都映射到了一个位置，导致了大量数据出现了哈希冲突，通过`HashMap`查询的效率从`O(1)`变成了`O(n)`。这样就有可能发生因为查询操作消耗大量 `CPU` 或者线程资源，而导致系统无法响应其他请求的情况，从而达到拒绝服务攻击（`DoS`）的目的。

**其次，哈希表的查找，更新的时间复杂度是 `O(1)`，而红黑树的查找，更新的时间复杂度是 `O(log2⁡n)`。**

但是由于`TreeNode`占用空间也比普通 `Node`的大，如非必要，尽量还是使用链表。

--------------------

### 3.2 树的退化 ###

树的退化主要是发生在这两种情况下

*  `HashMap`在扩容时，如果拆分树，树元素个数小于等于6，则会退化成链表
 *  `remove`树节点时，若 `root`、`root.left`、`root.right`、`root.left.left` 有一个为 null ，也会退化为链表

--------------------

## 4. 二次哈希 ##

在JDK1.8的源码的`put`方法中，会将`key`进行二次哈希

public V put(K key, V value) {
        
        return putVal(hash(key), key, value, false, true);
    }
    
    static final int hash(Object key) {
        
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

**通过源码可以了解到，首先会调用`key`对象的`hashCode`方法进行求哈希值，然后将该哈希值的低16位与高16位进行异或运算，这样做的目的是为了综合高位数据，让哈希分布更为均匀，减少哈希碰撞。**

**并且这么做可以在数组 table 的 length 比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。**

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>值</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>hashCode()</td> 
   <td>1,794,106,052</td> 
  </tr> 
  <tr> 
   <td>二进制</td> 
   <td><strong>01101010 11101111</strong> 11100010 11000100</td> 
  </tr> 
  <tr> 
   <td>h &gt;&gt;&gt; 16</td> 
   <td>00000000 00000000 <strong>01101010 11101111</strong></td> 
  </tr> 
 </tbody> 
</table>

--------------------

## 5. put方法源码分析 ##

查看`put`方法源码

transient Node<K,V>[] table;
    
    public V put(K key, V value) {
        
        // 调用上文我们已经分析过的hash方法
        return putVal(hash(key), key, value, false, true);
    }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                    boolean evict) {
        
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            // 第一次put时，会调用resize进行桶数组初始化
            n = (tab = resize()).length;
        // 根据数组长度和哈希值相与来寻址，原理上文也分析过
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 如果没有哈希碰撞，直接放到桶中
            tab[i] = newNode(hash, key, value, null);
        else {
        
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 哈希碰撞，且节点已存在，直接替换
                e = p;
            else if (p instanceof TreeNode)
                // 哈希碰撞，树结构
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
        
                // 哈希碰撞，链表结构
                for (int binCount = 0; ; ++binCount) {
        
                    if ((e = p.next) == null) {
        
                        p.next = newNode(hash, key, value, null);
                        // 链表过长，转换为树结构
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        // 如果节点已存在，则跳出循环
                        break;
                    // 否则，指针后移，继续后循环
                    p = e;
                }
            }
            if (e != null) {
         // existing mapping for key
                // 对应着上文中节点已存在，跳出循环的分支
                // 直接替换
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            // 如果超过阈值，还需要扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

`put`方法的大体思路如下

1.  调用`key`的`hashCode`方法计算哈希值，并据此计算出数组下标index
2.  如果发现当前的桶数组为`null`，则调用`resize()`方法进行初始化
3.  如果没有发生哈希碰撞，则直接放到对应的桶中
4.  如果发生哈希碰撞，且节点已经存在，就替换掉相应的`value`
5.  如果发生哈希碰撞，且桶中存放的是树状结构，则挂载到树上
6.  如果碰撞后为链表，添加到链表尾，如果链表超度超过`TREEIFY_THRESHOLD`默认是8，则将链表转换为树结构
7.  数据put完成后，如果`HashMap`的总数超过`threshold`就要`resize`

**`put`方法中比较重要的一个知识点莫过于计算索引了。**

1.  首先，先调用`hash`方法。
    
    1.  在`hash`方法中，计算对象的`hashCode`方法
    2.  再进行调用`HashMap`的`hash()`方法进行二次哈希
2.  接着，将`hash`方法返回的二次哈希值记为`hash`，用`(n - 1)`也就是数组长度减一对`hash`进行与运算（`(n - 1) & hash`）

**这里使用`n-1`是因为以默认数组长度16为例子，那么数组下标为0-15，哈希值计算`hash%(2^4)`，其本质就是和长度取余。也就等价于 (2^4 - 1) & hash**

**在JDK1.8和JDK1.7中，它们的`put`方法实现有所不同**

1.  链表插入节点时，1.7 是头插法，1.8 是尾插法
2.  1.7 是大于等于阈值且没有空位时才扩容，而 1.8 是大于阈值就扩容
3.  1.8 在扩容计算 Node 索引时，会优化

--------------------

## 6. key的设计 ##

`HashMap`的 `key`可以为 `null`，但 `Map`的其他实现就不一定了

其`key`应当符合下面的要求

1.  作为 `key`的对象，必须实现 `hashCode`和 `equals`，并且 `key`的内容不能修改（不可变）
2.  key 的 `hashCode`应该有良好的散列性

--------------------

## 7. 并发问题 ##

*  **扩容死链（1.7 会存在）**

void transfer(Entry[] newTable, boolean rehash) {
        
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
        
            while(null != e) {
        
                Entry<K,V> next = e.next;
                if (rehash) {
        
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

*  `e` 和 `next`都是局部变量，用来指向当前节点和下一个节点
 *  线程1（绿色）的临时变量 `e` 和 `next`刚引用了这俩节点，还未来得及移动节点，发生了线程切换，由线程2（蓝色）完成扩容和迁移

![image-20210831084325075][]

*  线程2 扩容完成，由于头插法，链表顺序颠倒。但线程1 的临时变量 e 和 next 还引用了这俩节点，还要再来一遍迁移

![image-20210831084723383][]

*  第一次循环
    
     *  循环接着线程切换前运行，注意此时 e 指向的是节点 a，next 指向的是节点 b
     *  e 头插 a 节点，注意图中画了两份 a 节点，但事实上只有一个（为了不让箭头特别乱画了两份）
     *  当循环结束是 e 会指向 next 也就是 b 节点

![image-20210831084855348][]

*  第二次循环
    
     *  next 指向了节点 a
     *  e 头插节点 b
     *  当循环结束时，e 指向 next 也就是节点 a

![image-20210831085329449][]

*  第三次循环
    
     *  next 指向了 null
     *  e 头插节点 a，**a 的 next 指向了 b**（之前 a.next 一直是 null），b 的 next 指向 a，死链已成
     *  当循环结束时，e 指向 next 也就是 null，因此第四次循环时会正常退出

![image-20210831085543224][]

*  **数据错乱（1.7，1.8 都会存在）**

假设现在有两个线程A和B，这两个线程都分别将数据C和D放进`HashMap`中，并且C和D的二次哈希值都一样。

线程A和线程B同时执行到检查有无哈希冲突的那一段代码。A和B检查均无发现有哈希冲突。

假设线程A比较快，于是线程A将`tab[i]`指向数据C。

这时候线程B将`tab[i]`指向数据D。

最终`tab[i]`指向数据D，导致了数据C丢失

--------------------

[DoS_hashmap dos_-CSDN]: https://blog.csdn.net/zwx900102/article/details/122502351
[_ HashMap _ h_h _16_ _hash_ 2_n_Java_-CSDN]: https://blog.csdn.net/lupengfei1009/article/details/124397576
[HashMap_-CSDN]: https://blog.csdn.net/DD_Dddd/article/details/115427040
[image-20230203164757901]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4bf37f27a72c49cf843b327f3db0275f.png
[img]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/291c76e7a4ab4e1094d4fcc0632b23fb.png
[image-20230203172039652]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/fd2f665385a24a528007f466232b021c.png
[image-20210831084325075]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/2a13cb01529442a28f4393afd289859f.png
[image-20210831084723383]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/332dde7a27d24cfc892531f75a1a0403.png
[image-20210831084855348]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/6df6fc1477ed4113b8e4b04004ec0ab8.png
[image-20210831085329449]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/183d8ae63daf4703a1c1cc18c6e294c6.png
[image-20210831085543224]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/5638e71aec134f1492ccad248d7f537f.png