拿下HashMap

绝地灬酷狼 2024-03-16 20:48 40阅读 0赞

从各方收集到的HashMap八股文，按照自己的考究、理解和侧重点做了整合。

## 1. 数据结构： ##

● 数组+链表，jdk1.8后引入红黑树。  
● 数组上面存多个entry键值对。链表时存的是node，node是entry的一个实现类。红黑树时在节点上放一个红黑树。  
○ node类里面的属性有：hash（hash值）、key、value、Node<K,V> next（存放下一个节点）  
● jdk1.7是头插法，1.8改为尾插法。  
○ 因为作者认为新插入的元素可能经常被使用，所以放在头部，便于查找。  
■ 高并发下扩容容易形成环形链表，当在链表搜索一个（用put或get操作）不存在的key时就会存在死循环。  
○ 尾插法：在未转化红黑树之前，新元素是追加在链表的尾部，最后一个元素的next指向是null  
■ 不会形成环形链表

##    2. 六大常量解释： ##

1. static final int DEFAULT\_INITIAL\_CAPACITY = 1 << 4; // aka 16  
默认初始化的数组大小 (默认的哈希桶数量) ： 16  
注：哈希桶就是哈希表中一个个的数组元素，不包括链表元素  
2.static final int MAXIMUM\_CAPACITY = 1 << 30;  
最大的数组容量： 2^30  
3.static final float DEFAULT\_LOAD\_FACTOR = 0.75f;  
默认负载因子，默认时开始保存的元素个数最多为 16 \* loadFactor = 12 个  
4.static final int TREEIFY\_THRESHOLD = 8;  
树化阈值。某个哈希桶中的链表长度超过8才会触发“树化”操作  
5.static final int UNTREEIFY\_THRESHOLD = 6;  
“解树化” 当某个哈希桶中的红黑树结点个数过小，< 6时，就会将红黑树还原为链表。  
6.static final int MIN\_TREEIFY\_CAPACITY = 64;

**树化有两个条件：**  
1. 此时哈希表的哈希桶个数 > =64  
2. 单个链表的结点个数 > 8  
若某个链表长度 > 8 ,但此时哈希桶的数量不足64，则只是简单的哈希表扩容而已。

**链表转为红黑树的条件：**  
1. 链表长度大于8  
a. 为什么是8？ —— 泊松分布。在空间和时间开销的取舍。  
2. 数组长度大于等于64  
a. 为什么是64？ —— 因为数组的长度较小，应该尽量避开红黑树，红黑树需要进行左旋，右旋，变色操作来保持平衡，维护成本较高。  
两个条件都满足才会转化，否则只是扩容数组。先判断链表长度再判断数组长度。  
  
**红黑树退化为链表条件：**  
1. resize的时候，对红黑树进行了拆分。链表长度小于6  
a. 为什么是6？ —— 需要有缓冲，不然会频繁切换数据结构。  
b. 不是立即转化，而是调用resize方法时，判断链表长度小于UNTREEIFY\_THRESHOLD（默认6）  
2. 调用map的remove方法删除元素，如果是红黑树则执行 removeTreeNode( ) 方法 。  
a. 如果红黑树根 root 为空，或者 root 的左子树/右子树为空，root.left.left 根的左子树的左子树为空，都会发生红黑树退化成链表。

b.所以说最大情况当有10个节点时也可能退化成链表 —— 根的左子树的左子树为空，其他地方都不为空，且遵循红黑树的规则。（再加叶子结点的话就违背了“从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。”）

##    3. 扩容相关 ##

扩容机制：  
根据数组长度\*扩容因子，到达这个数值时会进行扩容。

为什么扩容到2倍？  
1. 计算下标时会对key的hash值进行取模，当长度总是2^n时，用hash值和长度减一这个值进行位与运算时，结果等于对length长度直接取模。位与操作是二进制运算，性能比取模更好  
2. 只有在数组长度为 2 的指数次幂时，（hash & 数组长度）才会只有 0 和 数组长度 两种可能，数组转移时高低位指针才有效。这个在扩容后计算元素新的位置时需要用到。

对key计算hash值的时候，会先进行右移16位，再异或计算操作。  
保留高位和地位的信息，这样能使结果更离散，减少hash碰撞。

hashmap是一开始就16长度吗？  
不是，是第一次put值的时候，如果判断为null或长度为0，就进行第一次扩容并初始化数组。  
此外每次扩容都是在put元素插入值之后进行判断是否需要扩容，扩容前值已经放好了。  
另外，容量不一定输入多少就是多少，hashmap会改成不小于指定值的2的n次幂。

扩容阈值是大于还是大于等于？  
扩容是大于12（默认）；链表转红黑树是大于8且数组长度大于等于64（源码的判断是当数组是null或数组长度小于64，不进行树化）；退化为链表是小于6。  
  
  
调用扩容方法 resize() 条件：  
1. 数组初始化时会调用。  
2. 集合元素个数（size）> 数组阈值（threshold=数组长度×加载因子）时会调用。  
3. 调用了树化方法，但数组长度小于64，就会调用扩容方法。  
  
  
**HashMap 扩容后原有元素怎么存放？或：HashMap扩容后会重新计算Hash值吗？**  
1. JDK1.7  
a. JDK1.7中，HashMap扩容后，所有的key需要重新计算hash值，然后再放入到新数组中相应的位置。  
2. JDK1.8  
a. 在JDK1.8中，HashMap在扩容时，需要先创建一个新数组，然后再将旧数组中的数据转移到新数组上来。  
b. 分两种情况判断，当孤家寡人next=null时，新位置为（e.hash & newCap -1 ）—— hash值与新数组长度减一的与运算。  
c. 当next != null时 （对应上面为什么容量需要是2^n）  
ⅰ. e.hash & oldCap = 0的，在新表中与旧表中的位置一样  
ⅱ. e.hash & oldCap != 0的，位置为旧表位置+旧表长度

## 4. 横向对比 ##

HashMap为什么使用红黑树而不是B树或平衡二叉树AVL或二叉查找树？  
1.不使用二叉查找树  
  
二叉排序树在极端情况下会出现线性结构。例如：二叉排序树左子树所有节点的值均小于根节点，如果我们添加的元素都比根节点小，会导致左子树线性增长，这样就失去了用树型结构替换链表的初衷，导致查询时间增长。所以这是不用二叉查找树的原因。  
  
2.不使用平衡二叉树  
  
平衡二叉树是严格的平衡树，红黑树是不严格平衡的树，平衡二叉树在插入或删除后维持平衡的开销要大于红黑树。  
红黑树的虽然查询性能略低于平衡二叉树，但在插入和删除上性能要优于平衡二叉树。  
选择红黑树是从功能、性能和开销上综合选择的结果。  
  
3.不使用B树/B+树  
  
HashMap本来是数组+链表的形式，链表由于其查找慢的特点，所以需要被查找效率更高的树结构来替换。  
如果用B/B+树的话，在数据量不是很多的情况下，数据都会“挤在”一个结点里面，这个时候遍历效率就退化成了链表。  
  
  
HashMap和HashSet的区别？  
HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码⾮常⾮常少，因为除了 clone() 、 writeObject() 、 readObject() 是 HashSet ⾃⼰不得不实现之外，其他⽅法都是直接调⽤ HashMap 中的⽅法）  
1.HashMap实现了Map接口，HashSet实现了Set接口  
2.HashMap存储键值对，HashSet存储对象  
3.HashMap调用put()向map中添加元素，HashSet调用add()方法向Set中添加元素。  
4.HashMap使用键key计算hashCode的值，HashSet使用对象来计算hashCode的值，在hashCode相等的情况下，使用equals()方法来判断对象的相等性。  
5.HashSet中的元素由HashMap的key来保存，而HashMap的value则保存了一个静态的Object对象。

HashSet和TreeSet的区别？  
相同点：HashSet和TreeSet的元素都是不能重复的，并且它们都是线程不安全的。  
不同点：  
①HashSet中的元素可以为null，但TreeSet中的元素不能为null  
②HashSet不能保证元素的排列顺序，TreeSet支持自然排序、定制排序两种排序方式  
③HashSet底层是采用哈希表实现的，TreeSet底层是采用红黑树实现的。  
④HashSet的add，remove，contains方法的时间复杂度是 O(1)，TreeSet的add，remove，contains方法的时间复杂度是 O(logn）  
HashSet底层是基于HashMap实现的，存入HashSet中的元素实际上由HashMap的key来保存，而HashMap的value则存储了一个静态的Object对象。  
value中的值都是统一的一个private static final Object PRESENT = new Object();

## 5. 暂不归类 ##

ConcurrentHashMap是怎么保证线程安全的？  
在JDK1.7之前，ConcurrentHashMap是通过分段锁机制来实现的，所以其最大并发度受Segment的个数限制。因此，在JDK1.8中，ConcurrentHashMap的实现原理摒弃了这种设计，而是选择了与HashMap类似的数组+链表+红黑树的方式实现，而加锁则采用CAS和synchronized实现。  
  
JDK1.7及以前：  
  
ConcurrentHashMap使用分段式锁来保证线程安全，可以理解为把一个Map容器拆成n个Segment容器，每个Segment容器分配一把锁，同一时间只允许一个线程持有这把锁。但是宏观上，多个线程可以同时访问这个Map容器。  
  
ConcurrentHashMap是由一个Segment数组和多个HashEntry数组+链表组成的，Segment数组中的每一个元素都是Segment容器，存储一个HashEntry数组+链表。当线程执行添加或删除时，只锁住对应的Segment容器，不影响对其它Segment容器的操作。  
  
JDK1.8及以后：  
  
不再使用Segment+HashEntry+链表的结构了，改为像HashMap一样的数组+链表/红黑树的结构。对链表/红黑树的头/根结点加synchronized锁，在同一时间，只能有一个线程对该链表/红黑树进行操作。

put操作流程：

[更详细流程参考][Link 1]

比较关键的是第4步，当时没看懂，看了详解和源码后才看懂。重点是它比较的是下表位置的首个元素，因为红黑树和链表都是继承Node的，源码直接用Node而没有Node.next，代表是首个元素或根节点。在遍历红黑树和链表之前加这个判断的原因应该是为了效率，优化没有哈希碰撞的场景。

![6c54933fcc62447dafb71b71f01f3d3a.png][]  
①首先判断数组是否为空，如果数组为空则进行第一次扩容（resize）  
②根据key计算hash值并与上数组的长度-1（int index = key.hashCode()&(length-1)）得到键值对在数组中的索引。  
③如果该位置为null，则直接插入  
④如果该位置不为null,则判断key是否一样(hashCode和equals)，如果一样则直接覆盖value  
⑤如果key不一样，则判断该元素是否为红黑树的节点，如果是，则直接在红黑树中插入键值对  
⑥如果不是红黑树的节点，则就是链表，遍历这个链表执行插入操作，如果遍历过程中若发现key已存在，直接覆盖value即可。  
如果链表的长度大于等于8且数组中元素数量大于等于阈值64，则将链表转化为红黑树，（先在链表中插入再进行判断）  
如果链表的长度大于等于8且数组中元素数量小于阈值64，则先对数组进行扩容，不转化为红黑树。  
⑦插入成功后，判断数组中元素的个数是否大于阈值64（threshold），超过了就对数组进行扩容操作。

get操作流程：  
①计算key的hashCode的值，找到key在数组中的位置  
②如果该位置为null，就直接返回null  
③否则，根据equals()判断key与当前位置的值是否相等，如果相等就直接返回。  
④如果不等，再判断当前元素是否为树节点，如果是树节点就按红黑树进行查找。  
⑤否则，按照链表的方式进行查找。

[Link 1]: https://www.cnblogs.com/csnjava/p/16489607.html
[6c54933fcc62447dafb71b71f01f3d3a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/a94b609833854757ae5d3a7faff6709e.png