04_Hashmap

• 一. hashmap的基本原理
• 二. 红黑树
• • 2.1不使用红黑树，存在什么问题？
  • 2.2 如何解决链表过长，导致查询时间复杂度上升的问题？
  • 2.3 什么是二叉搜索树？为什么这种数据结构能够加快查询速度？
  • 2.4 我用普通的二叉搜索树不香吗？为什么要用红黑树呢
  • 2.5 想要实现红黑树，需要满足哪些规则
  • 2.6 红黑树到底长什么样子
  • 2.7 规则六为什么成立？为什么新加入到红黑树的节点必须是红色的？
  • 2.8 如果新加入节点后，出现了两个红色节点相邻的后果，红黑树会如何处理？
  • 2.9 什么是红黑树的左旋？
  • 2.10 什么是红黑树的右旋？
  • 2.11 如果删除节点后，出现了两个红色节点相邻的后果，红黑树会如何处理？
• 三. hashmap源码
• • 3.1 put(key, value)
  • 3.2 总结hashmap插入元素的过程
  • 3.3 通过红黑树来解决hash冲突
  • 3.4 基于数组的扩容原理
  • 3.5 get与remove操作的原理分析
• 三. 疑问
• • 3.1 既然红黑树的查询性能比链表高得多，为什么不直接使用红黑树来代替链表呢？

一. hashmap的基本原理

二. 红黑树

2.1不使用红黑树，存在什么问题？

答: 在JDK1.8之前，向hashmap新增数据时，只要hash冲突，就会在冲突的下标位置，形成链表。但是当hash冲突严重时，链表的长度过长，会导致查询元素的时间复杂度由O(1)上升到了O(n)。

2.2 如何解决链表过长，导致查询时间复杂度上升的问题？

答: 当我们向hashmap大量插入数据时，hash冲突难以避免，为了不让链表过长，JDK1.8以后规定，当链表的长度达到8之后，再出现这个下标的hash冲突时，就会把链表转换成红黑树。利用红黑树是二叉搜索树的特点，加快查询的速度。

2.3 什么是二叉搜索树？为什么这种数据结构能够加快查询速度？

答: 二叉搜索树又叫二叉查找树，或者二叉排序树。这种数据结构有三个明显的特点: 左子树小于节点本身，右子树大于节点本身，左右子树仍然是二叉搜索树。其实完全可以用一个词来概括: 左小右大。在对二叉搜索树查找数据时，能通过层层判断，过滤大部分的分支，快速的找到目标数据。

比如下方的二叉搜索树包含了从52到67数字。假设现在想寻找61，如果使用链表，无外乎就是从头节点出发，不断的找它的next节点，直到找到61为止，这显然性能极低。

如果我们使用二叉搜索树呢？首先发现61比60大，那么61肯定在60的右侧。接着发现61比64小，那么61肯定在64的左侧。然后发现62比61大，那么61肯定在62的左侧。最后找到61。只需要寻找4次，就能找到目标节点。

2.4 我用普通的二叉搜索树不香吗？为什么要用红黑树呢

答: 有些时候，人倒霉了就连喝水都呛着，向hashmap插入数据也是同样的道理。谁能保证插入的数据总是能像上图这么均衡呢？比如二叉搜索树长成了下图这种瘸腿样子。假设现在想查询50，那么是不是要从56向左子节点，一点一点的查询？这不就又变成链表了？

红黑树解决了这个问题，它有一个自动平衡的机制，在加入节点后，它能自动调整节点，最终使树达到接近平衡的状态。

2.5 想要实现红黑树，需要满足哪些规则

• 规则一: 节点分为红色和黑色。
• 规则二: 根节点必为黑色。
• 规则三: 叶子节点都是黑色的，且值为null。
• 规则四: 红色节点的子节点都是黑色的。红色节点与红色节点之间不能连在一起！
• 规则五: 任意节点出发，到它自己的每个叶子节点的路径中，都包含相同个数的黑色节点。
• 规则六: 新加入到红黑树的节点必须是红色的。

2.6 红黑树到底长什么样子

2.7 规则六为什么成立？为什么新加入到红黑树的节点必须是红色的？

答: 因为红黑树必须满足规则五，也就是任意一个节点，到它自己的叶子结点的路径中，都得包含相同黑色节点。如果你新加的节点颜色是黑色的，就会破坏这条规则。而加入红色节点时，除非待加入节点的父节点是红色节点，否则不可能出现两个红色节点相邻的情况，破坏规则的可能性更小一些。

2.8 如果新加入节点后，出现了两个红色节点相邻的后果，红黑树会如何处理？

答: 变色+旋转。

首先引入第一个例子，通过变色就能满足红黑树所有的需求。

假设最开始，红黑树长这个样子。

接着，我们插入51，按照二叉搜索树的规则，插入后，红黑树如下:

此时可以看到，49和51连到一起，违反了规则4，因为红色节点不能与红色节点相邻。

那么怎么办呢？

这个时候我们想到可以把49染成黑色，但染完之后，会导致56-45-49-51这条线路比别的线路中包含的黑色节点都要多，违背了规则5。

所以我们又想到把45也给染成红色，这样一来，56-45-49-51这条路径包含的黑色就是3个了。

但是这样一来就违背了规则4，因为56-45-43，这三个节点居然都是红色的，肯定不能忍啊，所以我们把43和56染成红色。这样一来，根节点(60)的左子节点就是一颗红黑树了。

还没有结束呢，通过上述的变换，现在违反了规则5，所以我们想到了把根节点右侧的包含黑色节点的个数提高1个，具体的做法就是把68变成黑色。

最终调整完整棵树，形成了一颗红黑树。

但是仅通过变色就能实现红黑树的调整工作，毕竟是少数情况，更多时候，需要使用旋转。下面是案例2，在下述的红黑树中添加65。

插入节点65之后，进行以下步骤:

这个时候会发现，无论我们把64染成什么颜色，都不能满足规则5，路径中的黑色节点的个数始终无法达成一致。

所以这个时候就必须使用旋转了，旋转的时候还要搭配变色。旋转包括左旋和右旋。

2.9 什么是红黑树的左旋？

逆时针旋转两个节点，具体看图。

为什么要断开G与C2的关系？

因为如果不断开，G就要同时直接挂载PL和C2这两个左子节点了。根据搜索二叉树的原理，C2一定比PL大，于是我们索性就把C2挂到PL的右子节点了。

2.10 什么是红黑树的右旋？

顺指针旋转一个节点，具体看图。

为什么要断开PL与C2的关系？

因为如果不断开，PL就要同时直接挂载G和C2这两个右子节点了。根据搜索二叉树的原理，C2一定比G小，反正G的左子树已经没有挂载任何节点了，索性就把C2挂载到G的左子树上。

https://www.sohu.com/a/335449747_463994 尚未写完

2.11 如果删除节点后，出现了两个红色节点相邻的后果，红黑树会如何处理？

三. hashmap源码

1.size到底是hashmap中目前存放的元素个数，还是在table上存放的node的个数，不包括链表上挂载的？

2.如果hash值相同，那么不同的Node都能放到table中吗？hash冲突时，冲突的Node到底会被放到哪里？

3.1 put(key, value)

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

看看hash()的实现代码

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

假设，我们的key对应的hash值是一串32位的二进制数字，如下:

1111 1111 1111 1111 1111 1010 0111 1100

现在执行h >>> 16，也就是把h无符号右移16位，说人话，就是把上述这串二进制数中的每一位(每一个bit)向右移动16个位置。

我们知道，最多也只能有32位，移动后，肯定会有位置空缺，这个时候补0即可。

所以，移动后的32位数字为:

0000 0000 0000 0000 1111 1111 1111 1111

接着，进行异或操作。所谓的异或，就是相同为0，不同为1。

左侧操作数: 1111 1111 1111 1111 1111 1010 0111 1100
右侧操作数: 0000 0000 0000 0000 1111 1111 1111 1111

执行结果

1111 1111 1111 1111 0000 0101 1000 0011

为什么要把hash值与右移后的hash值进行异或运算，求出一个新的hash值呢？

答: 原始的hash值与右移了16位之后的hash值进行异或运算，是为了让原始hash值的高16位和低16位进行异或运算，这样计算出来的最终的hash值的低16位，就既包含了原始hash值的高16位的特征，又包含了原始hash值的低16位的特征。

为什么要搞出这样一个同时包含高低16位特征的新的hash值呢？为何要这般大费周章呢？

答: 这都是为了key存储到table时，寻找index所做的努力。当拿到最终版本的hash值后，会再一次进行位运算，计算出本次k-v到底该存放到table数组的哪个下标，而这次位运算只涉及到低16位，不涉及到高16位。如果在最开始计算hash值时，我们没有对高低16位进行异或运算，直接把初次hash的值拿来运算，这就会导致hash值的高16位自始至终不能参与运算。

为什么一定要让高低16位的特征同时参与运算呢？我就是只想让低16位参与运算，行不行？

答: 不行。之所以让高低16位的特征同时参与运算，是因为这种算法可以降低最终key存储在table内的index产生冲突的概率。我们知道，关于index重复的可能场景有以下几种:

1. key不同，但是hash值相同，导致最终计算k-v存储到HashMap内的下标相同，最终导致hash冲突。
2. key不同，hash值也不同，但是计算出的下标相同，最终导致hash冲突。

如果想避免第一种场景，需要优化key.hashCode()，但是这个不可避免的会有冲突的可能。

再看看第二种场景，当key不同，hash值不同时，如果能尽可能的保证最终存储的index不同，那不就OK了么，而这个，就是上述算法的实现目标。只有让所有的数据充分进行了运算，才能达到最好的避免hash碰撞的效果。

再来看看putVal()方法

hashmap提升寻址能力的优化点 [面试考点]
i = (n - 1) & hash，n是HashMap中节点的总数。在过去，为了找到hash值对应存放的index，使用的是取模运算。但是呢，取模运算本身的性能比较差。为了优化hash寻址算法，JDK想到了使用(n-1) & hash，位运算的性能很高，并且也能实现和取模一样的效果。

p指针: 指向寻址到的下标对应的节点。
hash：本地待插入数据的hash值

场景1: 如果待插入的位置不存在hash冲突

此时会把待插入的数据构造成一个Node，直接写入数组。

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

场景2: 如果待插入的位置已经存在节点，新数据与旧数据对应的hash值完全相同，并且，他们俩的key内存地址相同，或者内存地址虽然不同，但是值相同。

举个例子就清楚了，假设先执行map.put(1, “张三”); 再执行map.put(1, “李四”)。此时，这两条待新增数据的key，无论是内存地址，还是数值本身，是不是完全相同？

这个时候，不会创建新的节点，只会把原节点的值替换成新值。

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
	e = p;

if (e != null) { // existing mapping for key
	V oldValue = e.value;
	if (!onlyIfAbsent || oldValue == null)
		e.value = value;
	afterNodeAccess(e);
	return oldValue;
}

场景3: hash值不同，且下标冲突 (可能转换成红黑树)

首先，我们找到本次寻址的下标上，已经存在的节点。

接着，用一个指针p指向该节点。检查当前节点是否是链表的最后一个节点，具体的做法就是判断p.next是否等于null。如果是，则把待插入的数据(key，value，hash)做成一个Node节点，加入到链表的末尾。如果不是，则让p=p.next，移动p指针，指向链表中的下一个节点。继续上述的检查操作。

但是上述循环的执行次数是有限制的，如果链表中已经存在8个节点了，不巧又产生了hash冲突，那么在挂上第9个节点后，此时hashmap就会把这个链表转换成红黑树。

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;
}

这个treeifyBin()方法非常复杂，不过它的作用就是：

Step1: 遍历出现hash冲突的Node链表，把Node转换成TreeNode，也就是红黑树节点。红黑树的节点与节点之前是通过类似双向链表关联的。

Step2: 第一次循环，会生成红黑树的第一个节点，接着每次循环，都会把新的节点加入到红黑树中，通过自我调整(比如变色、旋转)，形成一颗更大的红黑树。(对应的自我调整的方法是balanceInsertion())

3.2 总结hashmap插入元素的过程

1. 向hashmap插入数据时，key不同，hashcode()的结果相同，或者key相同，hash值相同，最终hash寻址到数组的位置是相同，会导致hash碰撞。
2. JDK1.8对寻址算法进行了优化，不再使用对hash取模的方式获取数组位置，而是采用(n-1) & hash位运算的方式进行寻址，运行速度更快，并且因为充分利用了hash的高低16位数字，hash碰撞的概率更小。
3. 出现hash冲突后，如果链表上节点的个数超过8，就会把当前的链表一口气转换成一颗红黑树，红黑树为了保持平衡，会进行自动调整，比如变色、左旋、右旋。此外，红黑树是一个双向链表，前后节点会互相指向。

3.3 通过红黑树来解决hash冲突

针对同一个数组位置，根据hash冲突的节点个数，有着不同的处理逻辑。

1. hash冲突的节点个数不超过8时(包含8)，只会形成链表。
2. 加入第9个节点时，会把当前的链表(包含了9个节点)一口气转换成一颗红黑树。
3. 加入大于9个节点后，就会直接把新的普通节点转换成一个红黑树节点，直接插入到完整的红黑树中。

3.4 基于数组的扩容原理

HashMap底层是基于数组做的，既然是数组，新增数据后，需要扩容的问题。

我们都知道，想要把一串k-v加入到hashmap中，首先要获取hash值，然后根据(n-1) & hash，寻找数组的下标。想想看，现在数组扩容后，最大容量已经发生了变化，之前的k-v串如果不重新寻址，可能会造成get()等方法无法正常获取数据的bug。

所以数组扩容后，必须对所有的数据重新计算数组下标。

jdk1.8以后，扩容一定是2的倍数，比如16到32、到64、到128。这就可以保证，扩容并重新寻址后，你的每个hash值要么是停留在原来的那个index上，要么变成了原来的index + oldCap，oldCap指的是原数组的长度。

比如说，有一个hash值，它原来是在index=5上，原数组的长度是16，那么扩容后，它现在可能在index=5上，也可能在index=21上。

通过扩容+重新寻址的方法，可以把原来冲突严重、堆集在一个数组位置上的节点分散到多个不同的数组位置上。

扩容的代码如下：

if (++size > threshold)
	resize();

resize( )的过程分成两个阶段，分别是"数组扩容"和"重新寻址"。

阶段一: 数组扩容

新数组的长度 = 旧数组的长度 << 1 (乘以2倍)

新数组的阈值 = 旧数组的阈值 << 1 (乘以2倍)

接着就是使用上方准备好的参数，创建新数组。

阶段二: 重新寻址

遍历旧数组，取出每一个旧节点。

Step1: 看看这个节点的next指针是否不为null，判断是否存在链表或者红黑树。

Step2: 如果当前节点的next指针为null，则只需要重新寻址，做与运算，把这个元素放到新数组的寻址位置上就好了。

Step3: 如果当前节点的next指针不为空，且当前节点的类型是红黑树，那么就会遍历这颗红黑树，读取每个节点内的数据，重新寻址，重新创建节点并放入新数组。

Step4: 如果当前节点的next指针不为空，且是链表，那就从当前节点开始，使用next指针，依次遍历链表中的每一个节点，重新计算节点存储的位置。

3.5 get与remove操作的原理分析

get(key)操作: 首先通过寻址算法，找到待查询元素对应的数组下标，接着判断数组内存放的节点的key与目标key是否相同，如果相同，则直接返回结果，否则就看看当前节点是不是红黑树，如果是，那就通过二叉搜索来寻找元素，否则就是链表，通过不断循环next指针，遍历每一个元素，与目标key进行比对即可。

remove(key)操作：分成两个步骤：找到目标节点，删除目标节点。

首先通过寻址算法，找到目标key对应的数组下标，接着就看下标上的节点到底是一个普通节点，还是链表，或者是红黑树节点。如果是后两种，则通过遍历链表或者二叉搜索红黑树，直到找到目标节点。

接着就是删除目标节点，如果目标节点就是数组节点，那么直接把对应下标上的数据置为null就好了。如果目标节点是链表，则按照链表来删除，如果是红黑树，则按照红黑树的删除规则来删除节点。

三. 疑问

3.1 既然红黑树的查询性能比链表高得多，为什么不直接使用红黑树来代替链表呢？

答： 这是因为为了做成红黑树，需要用到调整、加颜色、自旋，这就导致新增一个元素时，为了维持整颗红黑树，要花费更多的时间。新增元素的效率较低。