深入理解HashMap

电玩女神 2021-09-24 02:20 483阅读 0赞

# 哈希表 #

核心是基于哈希值的桶和链表

O(1)的平均查找、插入、删除时间

致命的缺陷是哈希值的碰撞(collision)

**图表理解**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]

# Java7中的HashMap(数组+链表) #

## 一、put操作理解。 ##

1、首先对于HashMap，我们存的是什么呢？就是key和value，表面上上我们看到的key和value是分开的，但是真正在实现的时候，HashMap会把这个key和value生成一个Entry对象，也就是说这个生成的Entry对象有两个属性，一个是key，另一个是value。所以我们在进行put操作的时候，其实就是生成一个Entry对象，然后将这个对象（对象引用地址）放在数组中。这样的话就把这个key和value放在这个容器中来了。

2、**hashCode不相等，那么两个对象不相等。hashCode相等，那么两个对象也不一定相等。**  
在进行put操作的时候，会进行链表的遍历，首先会判断hash值是不是相等，以及key值是不是相等。如果相等的话就会覆盖掉原来的值。然后会返回原来的key对应的value。

## 二、数组下标计算 ##

我们要想在数组当中存放一个元素，首先要得到下标index。例如：\*\*`arr[1]=e;`\*\*我们要把元素e放在数组的1号索引。但是在进行put操作时并没有指定一个下标，那想要在数组中存放这个Entry对象，这个下标是怎么来的呢？通过源码解读，这个下标是通过key来的。具体可以这样理解 ：一个Entry中包含了一个key属性，这个key可以属于任何数据类型（int、String…），但都属于Object。这里引入一下源码中的hash函数。(源码如下）可以看到hash函数根据 key 的不同类型进行 hashcode 的计算。

static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    key 在数组中的位置公式：tab[(n - 1) & hash]

这个时候只是算出了这个hashcode，但是不可能用这个hashcode作为这个数组的下标。一般来说，hashcode算出来之后，要计算当前 key 在数组中的索引下标位置时，可以采用取模的方式，就是索引下标位置 = hashcode % 数组大小，这样做的好处，就是可以保证计算出来的索引下标值可以均匀的分布在数组的各个索引位置上，但取模操作对于处理器的计算是比较慢的，数学上有个公式，当 b 是 2 的幂次方时，a % b = a &（b-1），所以此处索引位置的计算公式我们可以更换为： (n-1)&hashcode。

## **此问题可以延伸出四个小问题：** ##

**1：为什么不用 key % 数组大小，而是需要用 key 的 hash 值 % 数组大小。**

答：如果 key 是数字，直接用 key % 数组大小是完全没有问题的，但我们的 key 还有可能是字符串，是复杂对象，这时候用 字符串或复杂对象 % 数组大小是不行的，所以需要先计算出 key 的 hash 值。  
对于任何一个key 的 hash 值，用它来%数组大小都会得到一个\[0，数组大小-1\]这样范围的值，也就是说不会得到一个大于数组长度的下标，从而也就保证了不会发生数组越界异常。

**2：计算 hash 值时，为什么需要右移 16 位？**

答：hash 算法是 h ^ (h >>> 16)，为了使计算出的 hash 值更分散，所以选择先将 h 无符号右移 16 位，然后再于 h 异或时，就能达到 h 的高 16 位和低 16 位都能参与计算，减少了碰撞的可能性。

**3：为什么把取模操作换成了 & 操作？**

答：key.hashCode() 算出来的 hash 值还不是数组的索引下标，为了随机的计算出索引的下表位置，我们还会用 hash 值和数组大小进行取模，这样子计算出来的索引下标比较均匀分布。

取模操作处理器计算比较慢，处理器对 & 操作就比较擅长，换成了 & 操作，是有数学上证明的支撑，为了提高了处理器处理的速度。

**4：为什么提倡数组大小是 2 的幂次方？**

答：因为只有大小是 2 的幂次方时，才能使 hash 值 % n(数组大小) == (n-1) & hash 公式成立。

## 三、哈希冲突 ##

通过以上数组下标的计算从而我们可以经过hash函数得到了数组的下标。但是这是又出现了一个新的问题，假如在进行put操作时，通过同样的算法，很有可能得到一个和之前相同的下标值。这就产生了冲突。相同数组下标只能存放一个元素，那么怎么办呢？也就是常说的哈希碰撞。在Java1.7中采用了链表法：也就是在原来的Entry对象中添加next属性，指向发了冲突的下一个Entry对象。基于插入的效率，这里采用的是头插法。在新的Entry插入链表中后，并将其作为链表的头结点。

## 四、扩容 ##

首先判断一下当前HashMap的元素的个数是否大于等于预期的个数\*负载因子，如果满足就要进行扩容操作。那么是怎么扩容的呢 ？首先扩容是针对数组的，因为在初始化数组之后就已经初始化好了数组的大小。做法就是再生成一个新的数组，新数组空间为原来空间的2倍，然后将原来数组中的元素拷贝到新的数组中来。

# Java8中的HashMap(数组+链表+红黑树) #

## 新增操作示意图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]

## 1、 链表的新增 ##

链表的新增比较简单，就是把当前节点追加到链表的尾部，和 LinkedList 的追加实现一样的。

当链表长度大于等于 8 时，此时的链表就会转化成红黑树，转化的方法是：treeifyBin，此方法有一个判断，当链表长度大于等于 8，并且整个数组大小大于 64 时，才会转成红黑树，当数组大小小于 64 时，只会触发扩容，不会转化成红黑树，转化成红黑树的过程也比较简单，

## 2、红黑树新增节点过程 ##

首先判断新增的节点在红黑树上是不是已经存在，判断手段有如下两种：

1.1. 如果节点没有实现 Comparable 接口，使用 equals 进行判断；

1.2. 如果节点自己实现了 Comparable 接口，使用 compareTo 进行判断。

新增的节点如果已经在红黑树上，直接返回；不在的话，判断新增节点是在当前节点的左边还是右边，左边值小，右边值大；

自旋递归 1 和 2 步，直到当前节点的左边或者右边的节点为空时，停止自旋，当前节点即为我们新增节点的父节点；

把新增节点放到当前节点的左边或右边为空的地方，并于当前节点建立父子节点关系；

进行着色和旋转，结束。着色指的是给红黑树的节点着上红色或黑色，旋转是为了让红黑树更加平衡，提高查询的效率，总的来说都是为了满足红黑树的 5 个原则：

1、节点是红色或黑色  
2、根是黑色  
3、所有叶子都是黑色  
4、从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点  
5、从每个叶子到根的所有路径上不能有两个连续的红色节点

**为什么加入了红黑树，而不是其他的数据结构？**

答：这是基于综合的角度来考虑的、，因为对于HashMap不仅仅是put操作的效率要保证，get操作的效率也要保证。而红黑树对于这两个都是均衡的，是一个折中的办法。

**转化过程**

答：当链表的元素大于等于8时就会转换为红黑树。当链表的元素大于等于8时，查询效率降低了，这个时候就要变成红黑树了（但也不一定就要转化成红黑树，在源码中其实是可以看到的，还有一个判断的条件就是数组的容量小于默认值64，这时就会扩容）。当红黑树只有六个节点了，查询的效率还算可以，但是插入效率提高了，这时就要变成链表了。

**为什么临界值分别是8和6而不都是一样的呢？**

答：为了防止频繁的进行插入和删除，降低转化的效率。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]: /images/20210923/a789ca10c7524eee852b1510431dfc1c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]: /images/20210923/8f45dbc50e2e4f62a0ef6c4d1dc1b501.png