Java:HashMap原理与设计缘由

╰+攻爆jí腚メ 2021-12-15 12:19 446阅读 0赞

## 前言 ##

Java中使用最多的数据结构基本就是ArrayList和HashMap，HashMap的原理也常常出现在各种面试题中，本文就HashMap的设计与设计缘由作出一一讲解，并解答面试常见的一些问题。

## 一 HashMap数据结构 ##

HashMap是一张哈希表（即数组），表中的每个元素都是键值对（Map.Entry类）。并且每个元素都是一个链表（红黑树）的节点。并且HashMap的数组长度一定是**2的次幂**。

### 1.1 为何数组长度一定是2的次幂 ###

正常情况下，新增节点时，会对节点进行取模运算，确定节点在哈希表中的位置。但是当哈希表（数组）长度为2的次幂时，取模运算可以修改为**位与运算**。  
源码如下：

static final int hash(Object key) {
        if (key == null){
            return 0;
        }
        int h;
        h = key.hashCode()；返回散列值也就是hashcode
        // ^ ：按位异或
        // >>>:无符号右移，忽略符号位，空位都以0补齐
        //其中n是数组的长度，即Map的数组部分初始化长度
        return (n-1)&(h ^ (h >>> 16));
    }

具体原理可以参考专门讲解该算法的文章：  
[由HashMap哈希算法引出的求余%和与运算&转换问题][HashMap]

## 二 HashMap的键值存储 ##

我们给 put() 方法传递键和值时，我们先对键调用 hashCode() 方法，计算并返回 hashCode，然后使用HashMap内部的hash算法，将hashCode计算为表中的具体位置，找到 Map 数组的 bucket 位置来储存 Node 对象。

## 三 解决Hash碰撞 ##

> 使用拉链法

如果hash到的数组位置已存在对象，即为Hash碰撞。JDK使用拉链法解决Hash碰撞问题。  
即以原有的Node节点为基础，构造链表。将新的Node节点设为链表表头。

### 3.1 为何新节点为表头 ###

如果已原有节点为表头，则需要**遍历链表**，徒增不必要的性能消耗

### 3.2 链表过长导致的复杂度问题 ###

HashMap的查询操作最佳时间复杂度是`O(1)`，但是当表中的某个链表过长时，查询该链表上的元素时间复杂度为`O(n)`。`JDK1.8`中解决了该问题，当HashMap中某链表长度大于8时，链表会重构为红黑树，这样，HashMap的最坏时间复杂度为`O(n)`。同理，为了不必要的消耗，当链表长度小于6时，红黑树会重新变回链表

### 3.3 还有什么方法解决Hash碰撞 ###

开放寻址法，再哈希法  
感兴趣可以参看此文：  
[Hash碰撞和解决策略][Hash]

## 四 HashMap的扩容 ##

### 4.1 扩容时机 ###

当size超过阈值（*数组长度负载因子*\*）时，即开始扩容，HashMap的负载因子为0.75。

### 4.1.1 为何要数组未满就扩容 ###

避免频繁出现Hash碰撞，造成拉链过长（红黑树过长）。这样会导致查询复杂度频繁出现最坏情况

### 4.2 扩容过程 ###

创建原本数组容量\*2的新数组，将节点从原本的数组中迁移过去。

### 4.2.1 为何扩容的倍数是2倍 ###

原因一上文已说明，方便进行哈希运算。  
原因二是不需要重新计算Hash值（`JDK1.8`优化）。经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，经过rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。对应的就是下方的resize的注释。

/** 
     * Initializes or doubles table size.  If null, allocates in 
     * accord with initial capacity target held in field threshold. 
     * Otherwise, because we are using power-of-two expansion, the 
     * elements from each bin must either stay at same index, or move 
     * with a power of two offset in the new table. 
     * 
     * @return the table 
     */  
    final Node<K,V>[] resize() {  }

看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希值(也就是根据key1算出来的hashcode值)与高位与运算的结果。

![4624570-d09aaaebeb27eecd.png][]

image

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

![4624570-bf240f798a169eac.png][]

image

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。

## 五 重写equals方法需同时重写hashCode方法 ##

这个是老生常谈的问题了，如果顺利理解了HashMap的底层结构那么这个问题就很好理解了。equals相同的key理论上必定有相同hashCode，所以必须也重写hashCode方法。可以思考下如果没重写，在put,get过程中会导致什么问题。

[HashMap]: https://links.jianshu.com/go?to=https%3A%2F%2Fwww.cnblogs.com%2Fysocean%2Fp%2F9054804.html
[Hash]: https://links.jianshu.com/go?to=https%3A%2F%2Fwww.kawabangga.com%2Fposts%2F2493
[4624570-d09aaaebeb27eecd.png]: /images/20211214/c330e9793b244a199a7ed705b4ae4b2f.png
[4624570-bf240f798a169eac.png]: /images/20211214/ea21f805429e46dd9a0a74260d07b094.png