[数据结构与算法]干趴HashMap

HashMap

HashMap是怎么实现的？

• jdk1.8 之前 HashMap 由 数组 + 链表 组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突
• jdk1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（转为红黑树的边界值，默认为 8 ）并且当前数组的长度大于64时（必须同时满足两个条件），此时此索引位置上的所有数据改为使用红黑树存储。
• 补充：将链表转换成红黑树前会判断，即便阈值大于8，但是数组长度小于64，此时并不会将链表变为红黑树，而是选择逬行数组扩容。

说说红黑树特点？为什么不用二叉树/平衡树呢？

红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：

• 每个节点要么是红色，要么是黑色；
• 根节点永远是黑色的；
• 所有的叶子节点都是是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；
• 每个红色节点的两个子节点一定都是黑色；
• 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

之所以不用二叉树：

红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的O(n)时间复杂度。

之所以不用平衡二叉树：

平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。

红黑树怎么保持平衡的知道吗？TODO

红黑树有两种方式保持平衡：旋转和染色。

• 旋转：旋转分为两种，左旋和右旋

HashMap的put流程知道吗？

1. 首先进行哈希值的扰动，获取一个新的哈希值。

   (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   

2. 如果table没有初始化就先进行初始化过程；
3. 根据哈希值计算数组下标，如果对应小标正好没有存放数据，则直接插入即可，否则需要覆盖。

   tab[i = (n - 1) & hash])
   

4. 判断tab[i]是否为树节点，否则向链表中插入数据，是则向树中插入节点。
5. 如果链表中插入节点的时候，链表长度大于等于8，则需要把链表转换为红黑树。在该方法中会判断数组长度是否小于64，如果大于64才转换为红黑树，否则依旧进行扩容 。

   treeifyBin(tab, hash);
   

6. 最后所有元素处理完成后，判断是否超过阈值；threshold ，超过则扩容。

HashMap的扩容，详细讲一下？

以JDK1.8为例，当往HashMap放入元素时，如果元素个数大于threshold时，会进行扩容，使用2倍容量的数组代替原有数组。

原因是数组长度变为原来的2倍，表现在二进制上就是多了一个高位参与数组下标计算。

也就是说，在元素拷贝过程不需要重新计算元素在数组中的位置，只需要看看原来的hash值新增的那个bit是1还是0，是0的话索引没变，是1的话索引变成“原索引+oldCap”（根据e.hash & (oldCap - 1) == 0判断） 。

这样可以省去重新计算hash值的时间，而且由于新增的1bit是0还是1可以认为是随机的，因此resize的过程会均匀的把之前的冲突的节点分散到新的bucket。

HashMap的 哈希/扰动 函数是怎么设计的?如何计算数组（索引）下标？为什么这样设计？

• hash()函数 是先拿到 key 的hashcode，是一个32位的int类型的数值，然后让hashcode的高16位和低16位进行异或操作。

  static final int hash(Object key) {
      int h;
      // key的hashCode和key的hashCode右移16位做异或运算
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
  

• (n - 1) & hash：根据hash值计算索引值，在n为2的整次幂的时候相当于取模。

为什么这样设计？

如果当 n 即数组长度很小，假设是 16 的话，那么 n - 1 即为 1111 ，这样的值和 hashCode 直接做按位与操作，实际上只使用了哈希值的后 4 位。 如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题。

为什么HashMap链表转红黑树的阈值为8呢？

红黑树节点的大小大概是普通节点大小的两倍，所以转红黑树，牺牲了空间换时间，更多的是一种兜底的策略，保证极端情况下的查找效率。

阈值为什么要选8呢？和统计学有关。理想情况下，使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为8的情况，发生概率仅为0.00000006。

至于红黑树转回链表的阈值为什么是6，而不是8？是因为如果这个阈值也设置成8，假如发生碰撞，节点增减刚好在8附近，会发生链表和红黑树的不断转换，导致资源浪费。

HashMap怎么查找元素的呢？

1. 使用 hash() 函数，获取新的哈希值
2. 计算数组下标，获取节点
3. 当前节点和key匹配，直接返回
4. 否则，当前节点是否为树节点，查找红黑树
5. 否则，遍历链表查找

HashMap在什么时候需要会扩容？为什么扩容因子是0.75？

1. 当 HashMap 中的元素个数超过 临界值（threshold ）= 数组大小(数组长度) * loadFactor(负载因子) 时，就会进行数组扩容，loadFactor 的默认值是 0.75。默认为 16 * 0.75 = 12。
2. 当链表长度大于8，且数组长度小于64时会进行扩容。

为什么是 0.75？

假如设的比较大，元素比较多，空位比较少的时候才扩容，那么发生哈希冲突的概率就增加了，查找的 时间成本就增加了 。

设的比较小的话，元素比较少，空位比较多的时候就扩容了，发生哈希碰撞的概率就降低了，查找时间成本降低，但是就需要更多的空间去存储元素，空间成本就增加了 。

HashMap扩容流程了解吗？它是如何计算新下标的？

HashMap 在进行扩容时，使用的 rehash 方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n - 1) & hash 的结果相比，只是多了一个 bit 位，所以结点要么就在 原来的位置 ，要么就被分配到 原位置 + 旧容量 这个位置。

因此，我们在扩充 HashMap 的时候，不需要重新计算 hash 值 ，只需要用 原来的 hash 值 和 原数组扩容前长度进行 与操作（&），然后 看高位的那个 bit 是 1 还是 0 就可以了 ，是 0 的话索引没变，是 1 的话索引变成 “原位置 + 旧容量” 。

if ((e.hash & oldCap) == 0) {
	// 在 原位置
} else {
	// 在 原位置 + oldCap 的位置
}

优点：

• 省去了重新计算 hash 值的时间。
• 由于新增的 1bit 是 0 还是 1 可以认为 是随机的 ，在 resize 的过程中保证了 rehash 之后每个桶上的结点数一定小于等于原来桶上的结点数，保证了 rehash 之后不会出现更严重的 hash 冲突，均匀的把之前的冲突的结点分散到新的桶中了。

如果初始化HashMap，传一个14的值（不是2的整次幂）new HashMap<>，它会怎么处理？

传的不是2的倍数时，HashMap会向上寻找离得最近的2的倍数，所以传入14，但HashMap的实际容量是16。

源码中是通过一系列 右移 + 按位或 实现的。

为什么HashMap的容量是2的幂次方呢？

Hash 值的范围值比较大，使用之前需要先对数组的长度取模运算，得到的余数才是元素存放的位置也就是对应的数组下标。这个数组下标的计算方法是(n - 1) & hash。

将HashMap的长度定为2 的幂次方，这样就可以使用(n - 1)&hash位运算代替%取余的操作，提高性能。

在解决 hash 冲突的时候，为什么选择先用链表，再转红黑树?

• 因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。
• 当元素小于 8 个的时候，链表结构可以保证查询性能。
• 当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n) ，此时需要红黑树来 加快查询速度 ，但是插入和删除节点的效率变慢了 。

HashMap 是线程安全的吗？多线程下会有什么问题？

HashMap不是线程安全的，可能会发生这些问题：

• 多线程下扩容死循环 。JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。JDK1.8 使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
• 多线程的 put 可能导致元素的丢失 。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK 1.7 和 JDK 1.8 中都存在。
• put 和 get 并发时，可能导致 get 为 null 。线程 1 执行 put 时，因为元素个数超出 threshold 而导致 rehash，线程 2 此时执行 get，有可能导致这个问题。这个问题在 JDK 1.7 和 JDK 1.8 中都存在。

有什么办法能解决HashMap线程不安全的问题呢？

Java 中有 HashTable、Collections.synchronizedMap、以及 ConcurrentHashMap 可以实现线程安全的 Map。

• HashTable 是 直接在操作方法上加 synchronized 关键字，锁住整个table数组 ，粒度比较大；
• Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入 Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；
• ConcurrentHashMap 在jdk1.7中使用 分段锁 ，在jdk1.8中使用 CAS+synchronized 。

jdk1.8对HashMap主要做了哪些优化呢？为什么？（总结，不仅仅局限于数据结构）

• 数据结构 ：数组 + 链表改成了数组 + 链表或红黑树
  • 原因：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由O(n)降为O(logn)
• 链表插入方式 ：链表的插入方式从头插法改成了尾插法
  • 原因：因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环。
• 扩容rehash
  • 扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。
  • 原因：提高扩容的效率，更快地扩容。
• 扩容时机：在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；