【学习OR面试】HashMap

1.HashMap的布局特点

• 布局：桶数组 + 链表 / 红黑树
  
• 转换机遇：（3点）
  
  
  
  • 当链表的长度超过8 时且桶数组的长度大于等于 64，链表就会转换为红黑树。
    
  • 当链表长度超过8，但是桶数组长度没有到达64，优先扩容，提升桶数组长度。
    
  • 当红黑树节点 ≤ 6 时，红黑树退化为链表。
    
  
  
• 链表的查找时间复杂度是 O(n)，当链表长度较长时，查找性能会降落。红黑树是一种折中的方案，查找、插入、删除的时间复杂度都是 O(log n)。
  

2.红黑树的简单先容

一种自平衡二叉查找树，但是条件没平衡二叉树那么严格。
5点

• 每个节点要么是赤色，要么是黑色；
  
• 根节点永远是黑色；全部的叶子节点都是是黑色的（NULL 节点）；
  
• 赤色节点的子节点肯定是黑色的；
  
• 从任一节点到其每个叶子的全部简单路径都包罗雷同数目标黑色节点。（ 不走回头路）
  
• 任意一条路径不会超过另一条路径的两倍长度。
  

对比平衡二叉树：

• AVL树查，插，删也是O(log n)。但是查找更快，树高度更矮；插入删除更慢，必要处理更多的旋转（红黑树必要的做法是旋转与染色）。
  

3.HashMap的扩容【重点】

• 首先， HashMap 的容量是 2 的幂次方，目标：将取模运算 hash % table.length 优化为位运算 hash & (length - 1)。
  
• 扩容是看总表的全部节点数，不是单看链表或者桶数组；时间复杂度为 O(n)。
  
• 扩容一样平常是扩容为原来的2倍，不必要重新 hash ，只必要判断 hash & oldCap == 0 就可以知道键在新数组中的位置。这里的Cap是桶数组巨细。
  

扩容的三种环境：

• 单个节点：indexNew = hash & (newCap - 1)，相当于取模运算。
  
• 链表：遍历链表，将链表拆分为两个链表
  
  
  
  • 低位链表（Lo） ：hash & oldCap == 0 → 保存在原位置。
    
  • 高位链表（Hi） ：hash & oldCap != 0 → 移动到 原位置 + oldCap 的位置。
    
  
  
• 红黑树布局
  
  
  
  • 如果当前桶是一个红黑树（TreeNode），HashMap 会调用 split() 方法举行分裂。
    
  • 分裂后的红黑树如果节点数 ≤ UNTREEIFY_THRESHOLD（默认 6），会退化为链表。
    
  
  
• 举例：
  8的二进制为1000，扩容后16的二进制为10000，那么newCap-1的二进制为1111。
  indexNew = hash & (newCap - 1)：相当于保存二进制的低四位，也就是0-15，相当于取模。
  hash & oldCap  ：hash&1000，相当于把桶数组分为了两半，0-7旧的部分 | 8-15 新的部分。
  当低四位中的第四位不是1，那么就在旧的部分也就不必要迁移，必要迁移的环境就是 原位置 + oldCap 。
  

扩容后顺序是否变化？比如链表a->b->c拆分为（ac|b）后出现c->a

• JDK 7 在扩容的时间使用头插法来重新插入链表节点，这样会导致链表无法保持原有的顺序。(头插法性能高，不消遍历)
  
• JDK 8 改用了尾插法，并且当 (e.hash & oldCap) == 0 时，元素保存在原索引的位置；否则元素移动到原索引 + 旧数组巨细的位置。
  

4.HashMap的put流程【重点】

哈希寻址（123） → 处理哈希冲突（链表照旧红黑树）插入/覆盖节点（45）→ 判断是否必要扩容（67）

• 扰动哈希：先拿到 key 的哈希值，是一个 32 位的 int 类型数值，然后再让哈希值的高 16 位和低 16 位举行异或操作，这样能保证哈希分布均匀。
  
  
  
  • （补充：哈希表的索引是通过 h & (n-1) 盘算的，相当于截取了最低的四位。只取 h 的低位很容易导致哈希冲突。通过异或操作将 h 的高位引入低位，可以增长哈希值的随机性，从而减少哈希冲突。）
    
  
  
• 判断table是否为null或空，是的话举行初次分配；并使用哈希值和数组长度举行取模运算，确定索引位置。
  
  
  
  • 这里有一个懒加载，HashMap 在初始化时，并不会立即创建存储键值对的数组。
    
  • 只有当第一次调用 put()、get() 等方法时，才会触发数组的初始化。
    
  
  
• value雷同则覆盖，不同则代表哈希冲突插入链表尾部，当条件达到后，链表转换为红黑树。
  
• 判断是否必要扩容：大于``capacity * loadFactor`，总容量*负载因子（默认为0.75）。
  
• 新建桶数组容量为原来的2倍，举行扩容。
  

1. HashMap.put(k, v)
3. 1. 计算扰动 hash 值（h = hash(k) ^ (h >>> 16)）
4. 2. 判断 table 是否为空，若为空则初始化
5. 3. 计算桶索引 index = (n - 1) & hash
6. 4. 若无冲突：直接插入
7. 5. 若冲突：
8.    - 若 key 已存在：替换
9.    - 否则插入链尾
10.    - 若链表 > 8 且 table ≥ 64：转红黑树(插入链表后再转换为红黑树)
11. 6. 插入完成后：size++
12. 7. 判断是否 > threshold？若是：resize（扩容）

复制代码

5.JDK 8 对 HashMap 做了哪些优化呢？

• 布局：由数组 + 链表改成了数组 + 链表或红黑树
  
• 插入方式：由头插法改为了尾插法。头插法在扩容后会改变原来链表的顺序。
  
• 扩容机遇：扩容的机遇由插入时判断改为插入后判断。
  
• 哈希扰动算法优化：JDK 7 是通过多次移位和异或运算来实现的。JDK 8 让 hash 值的高 16 位和低 16 位举行了异或运算。
  

4点
6.对比一下 LinkedHashMap、TreeMap

• LinkedHashMap 在 HashMap 的基础上维护了一个双向链表，通过 before 和 after 标识前置节点和后置节点。
  保持插入顺序。
  
• TreeMap 通过 key 的比力器来决定元素的顺序，如果没有指定比力器，那么 key 必须实现 [Comparable 接口]。底层是红黑树，类比二叉排序树实现顺序访问。
  
• TreeMap的key不允许出现NULL，因为NULL无法比力，其它两个可以。