HashMap居然可以和它直接合体？？？
<blockquote><p><code>LinkedHashMap</code>集合继承于<code>HashMap</code>，学习<code>LinkedHashMap</code>重点对比 <code>LinkedHashMap</code> 与 <code>HashMap</code> 的异同</p>
<p>特别强调两者的 <code>Entry</code>（节点）数据结构、数据结构的不同带来的特性差异、<code>HashMap</code> 的后置处理机制及最少访问删除策略。</p>
</blockquote>
<p><code>LinkedHashMap</code> = <code>HashMap</code> + <code>LinkedList</code> ？</p>
<p><strong>就像这幅图一样？</strong></p>
<p><img src="https://img2024.cnblogs.com/blog/1209017/202507/1209017-20250714094307496-1318022374.jpg" alt="image" loading="lazy"></p>
<h2 id="1-entry节点数据结构">1. Entry（节点）数据结构</h2>
<h3 id="11-hashmapnode">1.1. HashMap.Node</h3>
<pre><code class="language-java">static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// … 构造、getKey/getValue/setValue、equals/hashCode 等 …
}
</code></pre>
<p><strong>字段</strong>说明：<code>hash</code>：key 的哈希值，<code>key</code>、<code>value</code>：存储的键值对，<code>next</code>：链表或树化时的链表指针。</p>
<p><img src="https://img2024.cnblogs.com/blog/1209017/202507/1209017-20250714094322299-811701120.jpg" alt="image" loading="lazy"></p>
<h3 id="12-linkedhashmapentry">1.2. LinkedHashMap.Entry</h3>
<pre><code class="language-java">// 头节点
transient LinkedHashMap.Entry<K,V> head;
// 尾节点
transient LinkedHashMap.Entry<K,V> tail;
// 节点类
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;// 双向链表指针
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
</code></pre>
<p><strong>新增字段说明</strong>：<code>before</code>、<code>after</code>：维护插入/访问顺序的双向链表；</p>
<p><strong>链表头尾</strong>：在 <code>LinkedHashMap</code> 中，维护一个 <code>head</code> 和 <code>tail</code> 指针，插入时追加到尾部。</p>
<p><img src="https://img2024.cnblogs.com/blog/1209017/202507/1209017-20250714094335975-1801010351.jpg" alt="image" loading="lazy"></p>
<p><code>LinkedHashMap</code> 数据结构就像它的名称一样<strong>Linked + HashMap</strong>，它是在<code>HashMap</code>的基础上，维护了一个双向链表。这个双向链表就像<code>LinkedList</code>一样，可以维护节点插入的顺序。</p>
<p><code>LinkedHashMap</code> 数据结构是<strong>两种形态共存</strong>的数据结构</p>
<ul>
<li>你可以忽略双向链表，把它看做普通的<code>HashMap</code>；</li>
<li>也可以忽略<code>HashMap</code>，把它看作是双向链表。</li>
</ul>
<blockquote>
<p>如果你不想使用<code>LinkedHashMap</code>，但又想要维护<code>HashMap</code>的插入顺序，那你可以在<code>HashMap.put</code>元素后，同时将该元素保存到<code>LinkedList.add</code>集合，但这样就需要你确保集合一致性，比如插入和删除。这么想想，还不如直接用<code>LinkedHashMap</code>集合较为稳妥。</p>
</blockquote>
<p>其实<code>LinkedHashMap</code> 一部分源码为的就是维护<code>HashMap</code>与双向链表的一致性，及操作过程做的一些扩展。比如：节点创建时的双向链表尾部插入和<code>HashMap</code>的后置处理。</p>
<h3 id="13-两者对比">1.3. 两者对比</h3>
<table>
<thead>
<tr>
<th>特性</th>
<th>HashMap</th>
<th>LinkedHashMap</th>
</tr>
</thead>
<tbody>
<tr>
<td>底层数据结构</td>
<td>数组 + 链表/红黑树</td>
<td>数组 + 链表/红黑树 + 双向链表</td>
</tr>
<tr>
<td>迭代顺序</td>
<td>不保证顺序</td>
<td>按插入顺序（或访问顺序，可选）</td>
</tr>
<tr>
<td>内存开销</td>
<td>较小</td>
<td>较大（每个节点额外维护链表指针）</td>
</tr>
<tr>
<td>适用场景</td>
<td>一般的键值存取</td>
<td>需要按插入或访问顺序遍历 (如 LRU 缓存)</td>
</tr>
</tbody>
</table>
<h3 id="14-详细的数据结构案例">1.4. 详细的数据结构案例</h3>
<p>通过下面的案例图，清楚地看见每个节点的指向。</p>
<p><strong>假设插入顺序为：</strong>22、23、45、89、25、38、49、28</p>
<p>插入完成后的数据结构如图，</p>
<p><strong>图中信息含义：</strong> 当前节点信息只显示<code>key</code>值，<code>next</code>为下一个映射冲突节点；<code>before</code>为双链结构的上一节点，<code>after</code>为双链结构的下一节点；<strong>绿色虚线</strong>是整个<code>LinkedHashMap</code>的双链结构的连接关系。</p>
<p><img src="https://img2024.cnblogs.com/blog/1209017/202507/1209017-20250714094351903-1059752500.jpg" alt="image" loading="lazy"></p>
<p>可以清楚地看到，相比<code>HashMap</code>每个节点都需要多维护<code>before</code>和<code>after</code>节点，<code>LinkedHashMap</code>也就需要更多的空间。</p>
<h2 id="2-节点创建和转化重写">2. 节点创建和转化重写</h2>
<h3 id="21-创建entry节点">2.1. 创建<code>Entry</code>节点</h3>
<p>链表节点创建的同时，通过<code>linkNodeLast(p)</code> 方法，维护双链结构的尾部插入</p>
<pre><code class="language-java">Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
</code></pre>
<h3 id="22-树节点创建">2.2. 树节点创建</h3>
<p>红黑树节点创建的同时，通过<code>linkNodeLast(p)</code>方法，维护双链结构的尾部插入</p>
<pre><code class="language-java">TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
linkNodeLast(p);
return p;
}
</code></pre>
<h3 id="23-节点转化">2.3. 节点转化</h3>
<p><strong>树节点转化为Entry节点</strong>和<strong>Entry节点转化树节点</strong>都做了重写，通过<code>transferLinks(q, t);</code>方法完成节点转化</p>
<pre><code class="language-java">Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
LinkedHashMap.Entry<K,V> t =
new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
transferLinks(q, t);
return t;
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
transferLinks(q, t);
return t;
}
</code></pre>
<p>这些都是<strong>多态</strong>的简单应用，<code>HashMap</code> 引用指向不同的实例化子类，实现不同的功能。</p>
<h2 id="3-hashmap-的后置处理post-processing">3. HashMap 的后置处理（post-processing）</h2>
<p><code>HashMap</code> 本身在节点插入、访问、删除后并不做额外操作。<code>LinkedHashMap</code> 则通过重写以下钩子方法，在插入、访问或删除时维护自己的双链表结构。</p>
<h3 id="31-插入后">3.1. 插入后</h3>
<p>仅在<code>evict=true</code> 并且<code>removeEldestEntry(first)==true</code>时，插入后才需要移除头部节点</p>
<pre><code class="language-java">void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
</code></pre>
<h3 id="32-访问后">3.2. 访问后</h3>
<p>仅在 <code>accessOrder = true</code> 时，访问后需调整顺序；需要在<code>LinkedHashMap</code> 的构造方法中设定<code>accessOrder</code>的值。</p>
<pre><code class="language-java">void afterNodeAccess(Node<K,V> e) {
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e;
// 将 p 移到双向链表尾部
moveNodeToLast(p);
}
</code></pre>
<h3 id="33-删除后">3.3. 删除后</h3>
<p>只要节点作删除，<code>LinkedHashMap</code>集合就必须删除双链表上的<code>Entry</code> 节点</p>
<pre><code class="language-java">void afterNodeRemoval(Node<K,V> e) {
// 将 e 从双向链表中摘除
unlinkNode((LinkedHashMap.Entry<K,V>)e);
}
</code></pre>
<p>这三步合称为 <strong>后置处理</strong>，保证在 <code>put</code>、<code>get</code>、<code>remove</code> 等操作时，链表结构的正确维护。</p>
<p>但是、</p>
<p>为什么<code>LinkedHashMap</code>集合在<strong>插入完成后</strong>，需要多做一步删除头节点的操作呢？</p>
<p>为什么<strong>访问完成后</strong>需要将访问节点移动到双链表的尾部呢？</p>
<h2 id="4-最少访问删除策略">4. 最少访问删除策略</h2>
<p>👉 <strong>为什么是 <code>LinkedHashMap</code> 而不是 <code>HashMap</code>：</strong></p>
<p><code>LinkedHashMap</code> 在 <code>HashMap</code> 基础上，增加了 <strong>双向链表</strong>，用来记录：插入顺序（默认）或访问顺序（<code>accessOrder = true</code> 时）</p>
<p>这就可以实现：记录最近访问的节点（最近访问的放到链表尾部）；删除最久未访问的节点（链表头）</p>
<h3 id="41-核心方法">4.1. 核心方法</h3>
<pre><code class="language-java">protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false; // 默认不删除
}
</code></pre>
<p>这是一个 <strong>钩子</strong>，这个钩子<code>removeEldestEntry(first)</code> 在插入后缀处理中调用，<code>LinkedHashMap</code> 的源码如下：</p>
<pre><code class="language-java">void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
</code></pre>
<p>你可以自己重写，<strong>制定属于自己的处理策略</strong>：</p>
<pre><code class="language-java">LinkedHashMap<K,V> lru = new LinkedHashMap<K,V>(16, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > 100; // 超过 100 个就删除最老的
}
};
</code></pre>
<p>当每次 <code>put</code> 后：<code>afterNodeInsertion</code> 调用 <code>removeEldestEntry</code>，如果返回 <code>true</code>，就从链表头删除最老节点</p>
<p><strong>总结：</strong></p>
<blockquote>
<p><code>LinkedHashMap</code> 用 <code>removeEldestEntry</code> + <code>accessOrder=true</code> 可实现简单 LRU 缓存。</p>
<p><code>HashMap</code> 不自带任何访问追踪或自动删除机制，必须由使用者自己实现。</p>
</blockquote>
<h3 id="42-lru缓存例子">4.2. LRU缓存例子</h3>
<p>LRU 缓存（<strong>Least Recently Used Cache</strong>，最近最少使用缓存）是一种常用的 <strong>缓存淘汰策略</strong>，它的核心思想是：</p>
<blockquote>
<p>如果数据最近被访问过，那么将来被访问的可能性也更高；反之则淘汰。</p>
</blockquote>
<p>规定固定大小为4的缓存容器，源码如下</p>
<pre><code class="language-java">public class LRUDemo {
public static void main(String[] args) {
// 指定只能缓存四个数据
LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
return size() > 4;
}
};
linkedHashMap.put("A","1");
linkedHashMap.put("B","2");
linkedHashMap.put("C","3");
linkedHashMap.put("D","4");
printOrder(linkedHashMap);
linkedHashMap.get("B"); // B 被访问，移到末尾
printOrder(linkedHashMap);
linkedHashMap.put("E","5"); // 淘汰最老的 A
printOrder(linkedHashMap);
}
public static void printOrder(LinkedHashMap<String, String> linkedHashMap ) {
System.out.print("数据结构：" + "\n");
for (Map.Entry<String, String> entry : linkedHashMap.entrySet()) {
System.out.print(" ⇄ " + entry.getKey());
}
System.out.println(" ⇄ \n");
}
}
</code></pre>
<p>执行输出结果如下：</p>
<blockquote>
<p>数据结构：</p>
<p> ⇄ A ⇄ B ⇄ C ⇄ D ⇄ </p>
<p>数据结构：</p>
<p> ⇄ A ⇄ C ⇄ D ⇄ B ⇄ </p>
<p>数据结构：</p>
<p> ⇄ C ⇄ D ⇄ B ⇄ E ⇄ </p>
</blockquote>
<h2 id="5-hashmap与linkedhashmap区别汇总">5. HashMap与LinkedHashMap区别汇总</h2>
<table>
<thead>
<tr>
<th>对比维度</th>
<th>HashMap</th>
<th>LinkedHashMap</th>
</tr>
</thead>
<tbody>
<tr>
<td>节点类型</td>
<td><code>HashMap.Node</code></td>
<td><code>LinkedHashMap.Entry</code>（继承自 <code>HashMap.Node</code>）</td>
</tr>
<tr>
<td>顺序保证</td>
<td>无</td>
<td>按插入顺序或访问顺序</td>
</tr>
<tr>
<td>额外字段</td>
<td><code>next</code></td>
<td><code>next</code> + <code>before</code> + <code>after</code></td>
</tr>
<tr>
<td>内存消耗</td>
<td>较低</td>
<td>较高（每个节点多两个引用）</td>
</tr>
<tr>
<td><code>put</code> 后置处理</td>
<td>无</td>
<td><code>afterNodeInsertion</code>（链表尾部插入 + 可选淘汰）</td>
</tr>
<tr>
<td><code>get</code> 后置处理</td>
<td>无</td>
<td><code>afterNodeAccess</code>（访问时链表重排序，仅 accessOrder = true）</td>
</tr>
<tr>
<td><code>remove</code> 后置处理</td>
<td>无</td>
<td><code>afterNodeRemoval</code>（从链表中摘除）</td>
</tr>
<tr>
<td>用途</td>
<td>高效快速随机存取</td>
<td>需要遍历顺序、实现 LRU 缓存、保持可预测迭代顺序</td>
</tr>
</tbody>
</table>
<p>通过上述对比，可以看出 <code>LinkedHashMap</code> 只是对 <code>HashMap</code> 的轻量增强：</p>
<ol>
<li><strong>核心额外逻辑</strong>：在每次增删改查操作后，钩入双向链表维护；</li>
<li><strong>额外空间开销</strong>：每个节点多俩指针；</li>
<li><strong>功能收益</strong>：可提供插入顺序或访问顺序的迭代、可实现基于访问顺序的缓存淘汰（如 LRU）。</li>
</ol>
<h2 id="6-总结">6. 总结</h2>
<p><code>LinkedHashMap</code>集合继承于<code>HashMap</code>，重点对比 <code>LinkedHashMap</code> 与 <code>HashMap</code> 不同的数据结构的带来的特性差异；为什么需要<code>LinkedHashMap</code>这种<strong>两种形态共存</strong>的数据结构；以及通过<code>HashMap</code> 的后置处理机制轻松实现数据结构的功能扩展；并且对<code>LinkedHashMap</code>最少访问删除策略<code>LRU</code>做了简单案例演示。</p>
<h2 id="往期推荐"><strong>往期推荐</strong></h2>
<table>
<thead>
<tr>
<th>分类</th>
<th>往期文章</th>
</tr>
</thead>
<tbody>
<tr>
<td>Java集合原理</td>
<td>HashMap集合--基本操作流程的源码可视化<br>Java集合--HashMap底层原理可视化，秒懂扩容、链化、树化<br>Java集合--从本质出发理解HashMap<br>Java集合--LinkedList源码可视化<br>Java集合源码--ArrayList的可视化操作过程</td>
</tr>
<tr>
<td>设计模式秘籍<br>（已全部开源）</td>
<td>掌握设计模式的两个秘籍<br>往期设计模式文章的：设计模式</td>
</tr>
<tr>
<td>软件设计师</td>
<td>软考中级--软件设计师毫无保留的备考分享通过软考后却领取不到实体证书？<br>2023年下半年软考考试重磅消息</td>
</tr>
<tr>
<td>Java学习路线<br>和相应资源</td>
<td>Java全栈学习路线、学习资源和面试题一条龙</td>
</tr>
</tbody>
</table>
<p>原创不易，觉得还不错的，三连支持：点赞、分享、推荐↓</p><br><br>
来源：https://www.cnblogs.com/dennyLee2025/p/18983432
頁:
[1]