面试题之HashMap

Jdk1.7到Jdk1.8 HashMap 发⽣了什么变化(底层)?

HashMap的Put⽅法

HashMap的扩容机制原理

1.7版本

1.8版本

HashMap扩容为什么是扩为两倍?

1. 1.7中底层是数组+链表，1.8中底层是数组+链表+红⿊树，加红⿊树的⽬的是提⾼HashMap插⼊和查询整体效率

2. 1.7中链表插⼊使⽤的是头插法，1.8中链表插⼊使⽤的是尾插法，因为1.8中插⼊key和value时需要判断链表元素个数，所以需要遍历链表统计链表元素个数，所以正好就直接使⽤尾插法

3. 1.7中哈希算法⽐较复杂，存在各种右移与异或运算，1.8中进⾏了简化，因为复杂的哈希算法的⽬的就是提⾼散列性，来提供HashMap的整体效率，⽽1.8中新增了红⿊树，所以可以适当的简化哈希算法，节省CPU资源

1. 根据Key通过哈希算法与与运算得出数组下标

2. 如果数组下标位置元素为空，则将key和value封装为Entry对象（JDK1.7中是Entry对象，JDK1.8中是Node对象）并放⼊该位置

3. 如果数组下标位置元素不为空，则要分情况讨论：

a.如果是JDK1.7，则先判断是否需要扩容，如果要扩容就进⾏扩容，如果不⽤扩容就⽣成Entry对象，并使⽤头插法添加到当前位置的链表中

b.如果是JDK1.8，则会先判断当前位置上的Node的类型，看是红⿊树Node，还是链表Node

如果是红⿊树Node，则将key和value封装为⼀个红⿊树节点并添加到红⿊树中去，在这个

过程中会判断红⿊树中是否存在当前key，如果存在则更新value

c,如果此位置上的Node对象是链表节点，则将key和value封装为⼀个链表Node并通过尾插

法插⼊到链表的最后位置去，因为是尾插法，所以需要遍历链表，在遍历链表的过程中会

判断是否存在当前key，如果存在则更新value，当遍历完链表后，将新链表Node插⼊到链

表中，插⼊到链表后，会看当前链表的节点个数，如果⼤于等于8，那么则会将该链表转成

红⿊树

d.将key和value封装为Node插⼊到链表或红⿊树中后，再判断是否需要进⾏扩容，如果需要

就扩容，如果不需要就结束PUT⽅法

1. 先⽣成新数组

2. 遍历⽼数组中的每个位置上的链表上的每个元素

3. 取每个元素的key，并基于新数组⻓度，计算出每个元素在新数组中的下标

4. 将元素添加到新数组中去

5. 所有元素转移完了之后，将新数组赋值给HashMap对象的table属性

1. 先⽣成新数组

2. 遍历⽼数组中的每个位置上的链表或红⿊树

3. 如果是链表，则直接将链表中的每个元素重新计算下标，并添加到新数组中去

4. 如果是红⿊树，则先遍历红⿊树，先计算出红⿊树中每个元素对应在新数组中的下标位置

a. 统计每个下标位置的元素个数

b. 如果该位置下的元素个数超过了8，则⽣成⼀个新的红⿊树，并将根节点的添加到新数组的对应位置

c. 如果该位置下的元素个数没有超过8，那么则⽣成⼀个链表，并将链表的头节点添加到新数组的对应位置

5. 所有元素转移完了之后，将新数组赋值给HashMap对象的table属性

HashMap扩容通常选择为原来的两倍，这一策略主要是为了在性能和内存占用之间寻找一个平衡点。这种策略基于以下几个原因：1

性能优化：扩容时，将容量扩大2倍可以更均匀地重新分布已有的元素，从而减少哈希冲突的概率。这意味着在新的容量下，每个桶中的元素数量更少，查找时间更短，提高了HashMap的性能。
空间利用率：虽然扩容会占用额外的内存，但2倍的扩容策略相对来说是一个合理的权衡。它不仅避免了频繁的扩容操作，还可以保持较高的空间利用率。如果扩容因子过小，可能会导致频繁的扩容操作，浪费内存；如果扩容因子过大，可能导致桶中的元素数量过多，增加了查找时间。
位运算优化：当扩容因子为2的幂次方时，可以使用位运算来计算哈希值的桶位置，而不需要进行昂贵的模运算，从而提高了计算的效率。
历史原因：在HashMap的早期版本中，选择2倍扩容因子是因为计算机中的整数乘法和除法操作通常要比其他因子（如3、5等）更快和更高效。

综上所述，2倍扩容因子是一种在性能和空间利用之间取得平衡的策略，它在实际应用中表现良好，使得HashMap在大多数情况下都能够提供高效的性能和相对高的空间利用率。但值得注意的是，如果特定应用场景需要不同的权衡，可以通过自定义HashMap来选择不同的扩容因子。