【学习OR面试】HashMap
<p><img src="https://cdn.tobebetterjavaer.com/tobebetterjavaer/images/sidebar/sanfene/collection-8.png" alt="img" loading="lazy"></p><h3 id="1hashmap的结构特点">1.HashMap的结构特点</h3>
<ul>
<li>结构：桶数组 + 链表 / 红黑树</li>
<li>转换时机：（3点）
<ul>
<li>当链表的长度<strong>超过</strong>8 时<strong>且</strong>桶数组的长度<strong>大于等于</strong> 64，链表就会转换为红黑树。</li>
<li>当链表长度超过8，但是桶数组长度没有到达64，优先<strong>扩容</strong>，提升桶数组长度。</li>
<li>当红黑树节点 ≤ 6 时，红黑树退化为链表。</li>
</ul>
</li>
<li>链表的查找时间复杂度是 <code>O(n)</code>，当链表长度较长时，查找性能会下降。红黑树是一种折中的方案，查找、插入、删除的时间复杂度都是 <code>O(log n)</code>。</li>
</ul>
<h3 id="2红黑树的简单介绍">2.红黑树的简单介绍</h3>
<p>一种自平衡二叉查找树，但是条件没平衡二叉树那么严格。</p>
<p><strong>5点</strong></p>
<ul>
<li>
<p>每个节点要么是红色，要么是黑色；</p>
</li>
<li>
<p>根节点永远是黑色；所有的叶子节点都是是黑色的（NULL 节点）；</p>
</li>
<li>
<p>红色节点的子节点一定是黑色的；</p>
</li>
<li>
<p>从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。（ 不走回头路）</p>
</li>
<li>
<p>任意一条路径不会超过另一条路径的两倍长度。</p>
</li>
</ul>
<p>对比平衡二叉树：</p>
<ul>
<li>AVL树<strong>查，插，删</strong>也是<code>O(log n)</code>。但是查找更快，树高度更矮；插入删除更慢，需要处理更多的旋转（红黑树需要的做法是旋转与染色）。</li>
</ul>
<h3 id="3hashmap的扩容重点">3.HashMap的扩容【重点】</h3>
<ul>
<li>首先， HashMap 的容量是 2 的幂次方，目的：将取模运算 <code>hash % table.length</code> 优化为位运算 <code>hash & (length - 1)</code>。</li>
<li>扩容是看<strong>总表的所有节点数</strong>，不是单看链表或者桶数组；时间复杂度为 <code>O(n)</code>。</li>
<li>扩容一般是扩容为原来的2倍，不需要重新 hash ，只需要判断 <code>hash & oldCap == 0</code> 就可以知道键在新数组中的位置。这里的<code>Cap</code>是桶数组大小。</li>
</ul>
<p>扩容的三种情况：</p>
<ul>
<li>
<p>单个节点：<code>indexNew = hash & (newCap - 1)</code>，相当于取模运算。</p>
</li>
<li>
<p>链表：遍历链表，将链表拆分为两个链表</p>
<ul>
<li><strong>低位链表（Lo）</strong> ：<code>hash & oldCap == 0</code> → 保留在原位置。</li>
<li><strong>高位链表（Hi）</strong> ：<code>hash & oldCap != 0</code> → 移动到 <code>原位置 + oldCap</code> 的位置。</li>
</ul>
</li>
<li>
<p><strong>红黑树结构</strong></p>
<ul>
<li>如果当前桶是一个红黑树（TreeNode），HashMap 会调用 <code>split()</code> 方法进行分裂。</li>
<li>分裂后的红黑树如果节点数 ≤ UNTREEIFY_THRESHOLD（默认 6），会退化为链表。</li>
</ul>
</li>
<li>
<p>举例：</p>
<p>8的二进制为1000，扩容后16的二进制为10000，那么newCap-1的二进制为1111。</p>
<p><code>indexNew = hash & (newCap - 1)</code>：相当于保留二进制的低四位，也就是0-15，相当于取模。</p>
<p><code>hash & oldCap </code> ：hash&1000，相当于把桶数组分为了两半，0-7旧的部分 | 8-15 新的部分。</p>
<p>当低四位中的第四位不是1，那么就在旧的部分也就不需要迁移，需要迁移的情况就是 <code>原位置 + oldCap</code> 。</p>
</li>
</ul>
<p>扩容后顺序是否变化？比如链表a->b->c拆分为（ac|b）后出现c->a</p>
<ul>
<li>JDK 7 在扩容的时候使用头插法来重新插入链表节点，这样会导致链表无法保持原有的顺序。(头插法性能高，不用遍历)</li>
<li>JDK 8 改用了尾插法，并且当 (e.hash & oldCap) == 0 时，元素保留在原索引的位置；否则元素移动到原索引 + 旧数组大小的位置。</li>
<li>首先，元素迁移是一个一个进行的，所以扩容后用头插法会倒序，基于此得到常见的一个问题：头插法 + 多线程操作 + 扩容会导致形成环形链表。举例：
<ul>
<li>原链表：a → b → c</li>
<li>两个线程同时进行扩容（假设链表不拆分），理想情况下：c → b → a</li>
<li>线程A线头插【a】（它的current和next指针更新，指向b，c），线程A，B同时进行插入【b，c】</li>
<li>线程B抢占成功，最终得到：c → b → a</li>
<li>此时线程A恢复（它不知道线程B做了修改，此时它的current和next指针还是指向b，c），<br>
继续插入b：b → c → b 【b → a断了】 a ，形成死循环。</li>
</ul>
</li>
</ul>
<h3 id="4hashmap的put流程重点">4.HashMap的put流程【重点】</h3>
<p>哈希寻址（123） → 处理哈希冲突（链表还是红黑树）插入/覆盖节点（45）→ 判断是否需要扩容（67）</p>
<ul>
<li>
<p>扰动哈希：先拿到 key 的哈希值，是一个 32 位的 int 类型数值，然后再<strong>让哈希值的高 16 位和低 16 位进行异或操作</strong>，这样能保证哈希<strong>分布均匀</strong>。</p>
<ul>
<li>（补充：哈希表的索引是通过 <code>h & (n-1)</code> 计算的，相当于截取了最低的四位。只取 h 的低位很容易导致哈希冲突。通过异或操作将 h 的高位引入低位，可以增加哈希值的随机性，从而减少哈希冲突。）</li>
</ul>
</li>
<li>
<p>判断table是否为null或空，是的话进行首次分配；并使用哈希值和数组长度进行取模运算，<strong>确定索引位置</strong>。</p>
<ul>
<li>这里有一个懒加载，<code>HashMap</code> 在初始化时，并不会立即创建存储键值对的数组。</li>
<li>只有当第一次调用 <code>put()</code>、<code>get()</code> 等方法时，才会触发数组的初始化。</li>
</ul>
</li>
<li>
<p>key相同则覆盖，不同则代表哈希冲突插入链表<strong>尾部</strong>，当条件达到后，链表转换为红黑树。</p>
</li>
<li>
<p>判断是否需要扩容：大于``capacity * loadFactor`，总容量*负载因子（默认为0.75）。</p>
</li>
<li>
<p>新建桶数组容量为原来的2倍，进行扩容。</p>
</li>
</ul>
<pre><code class="language-xml">HashMap.put(k, v)
1. 计算扰动 hash 值（h = hash(k) ^ (h >>> 16)）
2. 判断 table 是否为空，若为空则初始化
3. 计算桶索引 index = (n - 1) & hash
4. 若无冲突：直接插入
5. 若冲突：
- 若 key 已存在：替换
- 否则插入链尾
- 若链表 > 8 且 table ≥ 64：转红黑树(插入链表后再转换为红黑树)
6. 插入完成后：size++
7. 判断是否 > threshold？若是：resize（扩容）
</code></pre>
<h3 id="5jdk-8-对-hashmap-做了哪些优化呢">5.JDK 8 对 HashMap 做了哪些优化呢？</h3>
<ul>
<li>结构：由数组 + 链表改成了数组 + 链表或红黑树</li>
<li>插入方式：由头插法改为了尾插法。头插法在扩容后会改变原来链表的顺序。</li>
<li>扩容时机：扩容的时机由插入时判断改为插入后判断。</li>
<li>哈希扰动算法优化：JDK 7 是通过多次移位和异或运算来实现的。JDK 8 让 hash 值的高 16 位和低 16 位进行了异或运算。</li>
</ul>
<p><strong>4点</strong></p>
<h3 id="6对比一下-linkedhashmaptreemap">6.对比一下 LinkedHashMap、TreeMap</h3>
<ul>
<li>
<p>LinkedHashMap 在 HashMap 的基础上维护了一个双向链表，通过 before 和 after 标识前置节点和后置节点。</p>
<p><strong>保持插入顺序</strong>。</p>
</li>
<li>
<p>TreeMap 通过 key 的比较器来决定元素的顺序，如果没有指定<strong>比较器</strong>，那么 key 必须实现 。底层是红黑树，类比二叉排序树实现顺序访问。</p>
</li>
<li>
<p>TreeMap的key不允许出现NULL，因为NULL无法比较，其它两个可以。</p>
</li>
</ul><br><br>
来源：https://www.cnblogs.com/lazyGuai/p/18949811
頁:
[1]