哈希表笔记（三）Java Hashmap

一、基本介绍

HashMap 是 Java 集合框架中的核心类之一，基于哈希表实现，提供了 Map 接口的主要实现。

1.1 主要特点

• 实现了 Map<K,V> 接口
• 允许 null 键和 null 值（不同于 Hashtable）
• 非同步实现（非线程安全）
• 不保证元素顺序的一致性和稳定性
• 基本操作（get 和 put）提供常数级时间性能（O(1)）
• 迭代性能与"容量"和"大小"成正比

1.2 继承关系

java.lang.Object└── java.util.AbstractMap<K,V>└── java.util.HashMap<K,V>

1.3 常见应用场景

• 快速查找数据：当需要通过键快速查找数据时
• 缓存实现：保存数据以便快速访问
• 数据统计：统计元素出现次数
• 关联映射：需要建立对象与对象之间关系时

二、核心参数

2.1 基本参数

// 默认初始容量 - 必须是 2 的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 即 16// 最大容量（必须是 2 的幂且小于等于 1<<30）
static final int MAXIMUM_CAPACITY = 1 << 30;// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 链表转红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;// 红黑树转链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;// 可以树化的最小表容量
static final int MIN_TREEIFY_CAPACITY = 64;

2.2 关键字段

// 存储元素的数组，长度总是 2 的幂
transient Node<K,V>[] table;// 保存 entrySet() 的缓存
transient Set<Map.Entry<K,V>> entrySet;// 键值对数量
transient int size;// 结构修改次数（用于快速失败机制）
transient int modCount;// 扩容阈值 = 容量 * 负载因子
int threshold;// 哈希表的负载因子
final float loadFactor;

三、数据结构详解

3.1 Node 节点（基本节点）

static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;// 构造器和各种方法实现...
}

• hash: 键的哈希值
• key: 键
• value: 值
• next: 指向下一个节点的引用，形成链表结构

3.2 TreeNode 节点（树形节点）

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent;TreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev;boolean red;// 各种红黑树操作方法...
}

• parent: 父节点
• left: 左子节点
• right: 右子节点
• prev: 双向链表中的前驱节点
• red: 红黑树中节点的颜色标记

四、关键方法实现

4.1 哈希计算方法

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 核心思想：将 hashCode 的高 16 位和低 16 位进行异或，增加低位的随机性
• 目的：减少哈希冲突，提高 HashMap 的性能
• 特殊处理：null 键的哈希值为 0

4.2 确定桶索引

索引计算：(n - 1) & hash，其中 n 是 table 的长度。

• 由于 n 总是 2 的幂，所以 (n - 1) 是一个全 1 的位掩码
• (n - 1) & hash 等价于 hash % n，但位运算更高效
• 巧妙利用了位运算提高性能

4.3 tableSizeFor 方法

static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

• 作用：找到大于等于给定数值的最小的 2 的幂
• 实现原理：通过一系列位操作，将最高位的 1 扩展到右侧所有位，然后加 1
• 场景：设置初始容量时使用

4.4 put 方法实现

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 1. 如果表为空则创建if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 2. 计算索引位置，如果为空则直接插入新节点if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;// 3. 如果首节点就是要找的键，准备更新值if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))e = p;// 4. 如果是红黑树节点，使用树的方式插入else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 5. 遍历链表else {for (int binCount = 0; ; ++binCount) {// 到达链表尾部，插入新节点if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 检查是否需要树化if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);break;}// 找到键相等的节点if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 6. 如果找到匹配的键，更新值并返回旧值if (e != null) {V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}// 7. 结构修改计数加1++modCount;// 8. 判断是否需要扩容if (++size > threshold)resize();// 9. 插入后回调afterNodeInsertion(evict);return null;
}

4.5 get 方法实现

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 1. 表不为空，长度大于0，且对应桶不为空if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 2. 检查第一个节点if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))return first;// 3. 检查剩余节点if ((e = first.next) != null) {// 如果是树节点，使用树的查找方法if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 遍历链表do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}

4.6 resize 方法实现

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;// 1. 计算新容量和新阈值if (oldCap > 0) {// 如果旧容量已达到最大值，不再扩容if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 容量翻倍，阈值也翻倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1;}else if (oldThr > 0) // 使用初始阈值作为初始容量newCap = oldThr;else {               // 使用默认值newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 2. 如果新阈值为0，计算新阈值if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;// 3. 创建新表@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;// 4. 将旧表数据迁移到新表if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null; // 帮助GC// 如果桶中只有一个节点，直接放到新位置if (e.next == null)newTab[e.hash & (newCap - 1)] = e;// 如果是树节点，需要特殊处理else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 如果是链表，需要拆分为高低两个链表else {Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;// 根据 (e.hash & oldCap) 决定节点去向if ((e.hash & oldCap) == 0) {// 放到低位链表（原索引）if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {// 放到高位链表（原索引+oldCap）if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 将两个链表放入新表对应位置if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

4.7 树化操作

final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// 如果表太小，优先扩容而不是树化if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {// 将链表转换为红黑树TreeNode<K,V> hd = null, tl = null;// 1. 将普通节点链表转为双向链表形式的TreeNode链表do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);// 2. 如果转换成功，执行树化操作if ((tab[index] = hd) != null)hd.treeify(tab);}
}

4.8 红黑树分裂

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {TreeNode<K,V> b = this;// 将树节点分为低位和高位两部分TreeNode<K,V> loHead = null, loTail = null;TreeNode<K,V> hiHead = null, hiTail = null;int lc = 0, hc = 0;// 1. 遍历树节点，根据 (hash & bit) 分组for (TreeNode<K,V> e = b, next; e != null; e = next) {next = (TreeNode<K,V>)e.next;e.next = null;if ((e.hash & bit) == 0) {// 低位组if ((e.prev = loTail) == null)loHead = e;elseloTail.next = e;loTail = e;++lc;}else {// 高位组if ((e.prev = hiTail) == null)hiHead = e;elsehiTail.next = e;hiTail = e;++hc;}}// 2. 根据节点数量决定是保持树形结构还是转回链表if (loHead != null) {if (lc <= UNTREEIFY_THRESHOLD)tab[index] = loHead.untreeify(map);else {tab[index] = loHead;if (hiHead != null)loHead.treeify(tab);}}if (hiHead != null) {if (hc <= UNTREEIFY_THRESHOLD)tab[index + bit] = hiHead.untreeify(map);else {tab[index + bit] = hiHead;if (loHead != null)hiHead.treeify(tab);}}
}

4.9 红黑树转链表

final Node<K,V> untreeify(HashMap<K,V> map) {Node<K,V> hd = null, tl = null;// 将 TreeNode 转回普通 Nodefor (Node<K,V> q = this; q != null; q = q.next) {Node<K,V> p = map.replacementNode(q, null);if (tl == null)hd = p;elsetl.next = p;tl = p;}return hd;
}

五、关键机制解析

5.1 哈希冲突解决方案

1. 链地址法：

   • 使用链表存储哈希冲突的元素
   • 当链表长度超过阈值时，转为红黑树提高效率

2. 容量始终为 2 的幂的好处：

   • 使用 (n - 1) & hash 代替 hash % n 计算索引，提高性能
   • 元素在扩容时分布更均匀（利用 hash 的高位信息）

5.2 扩容机制详解

1. 触发条件：

   • size > threshold（元素数量超过阈值）
   • 初始化时（table 为 null）
   • 树化时表太小（treeifyBin 方法中）

2. 扩容过程：

   • 容量翻倍（<<1）
   • 阈值翻倍
   • 重新哈希所有元素

3. 元素再散列优化：

   • 利用 hash & oldCap 将元素分为两组
   • 一组留在原位置（j）
   • 另一组放在新位置（j + oldCap）
   • 避免了全部重新计算索引的开销

5.3 树化与反树化机制

1. 树化条件：

   • 链表长度 >= TREEIFY_THRESHOLD（8）
   • 桶数组容量 >= MIN_TREEIFY_CAPACITY（64）

2. 反树化（树转链表）条件：

   • 树节点数量 <= UNTREEIFY_THRESHOLD（6）
   • 扩容时会触发检查

3. 树化过程：

   • 先转为双向链表形式的 TreeNode
   • 然后应用红黑树算法建树

4. 为什么需要树化：

   • 链表查找时间复杂度为 O(n)
   • 红黑树查找时间复杂度为 O(log n)
   • 当链表过长时，树结构能显著提高性能

5.4 负载因子的作用

1. 定义：

   • 负载因子 = 元素数量 / 容量
   • 默认值为 0.75

2. 影响：

   • 较小的负载因子：空间利用率低，但冲突少，查询性能好
   • 较大的负载因子：空间利用率高，但冲突多，查询性能差
   • 0.75 是时间和空间成本的折中

3. 阈值计算：

   • threshold = capacity * loadFactor
   • 当元素数量超过阈值时触发扩容

六、使用注意事项

6.1 线程安全问题

• HashMap 非线程安全，并发环境下可能导致死循环、数据丢失等问题
• 多线程环境应使用 ConcurrentHashMap 或 Collections.synchronizedMap()

6.2 性能优化建议

1. 初始容量设置：

   • 如果预知数据量，合理设置初始容量可减少扩容次数
   • 初始容量 = 预期元素数量 / 负载因子

2. 哈希码质量：

   • 自定义键类型应正确实现 hashCode() 和 equals() 方法
   • 尽量使哈希分布均匀，减少冲突

3. 避免频繁扩容：

   • 合理估计数据规模，一次性分配足够空间
   • 批量添加数据时，使用带初始容量的构造器

6.3 常见错误

1. 可变对象做键：

   • 键对象的哈希码变化会导致无法找到已存储的值
   • 键应为不可变对象，或确保哈希码不变

2. 未正确实现 equals 和 hashCode：

   • 必须同时重写这两个方法
   • 相等的对象必须有相同的哈希码

3. 迭代时修改：

   • 迭代过程中修改结构（增删元素）会触发 ConcurrentModificationException
   • 应使用迭代器的 remove 方法进行安全删除

七、JDK 8 相比 JDK 7 的改进

1. 红黑树优化：

   • JDK 7 中只使用链表解决冲突
   • JDK 8 引入红黑树结构，提高大量冲突时的性能

2. 链表插入方式：

   • JDK 7 采用头插法，扩容时可能导致循环链表
   • JDK 8 采用尾插法，避免了这个问题

3. 哈希计算优化：

   • JDK 8 的哈希算法更简单高效
   • 使用 h ^ (h >>> 16) 增加低位随机性

4. 新增 API：

   • 引入函数式接口支持：compute、merge、forEach 等
   • 提供更灵活的操作方式

八、常见面试题解析

8.1 为什么 HashMap 的容量总是 2 的幂？

• 使用位运算 (n-1) & hash 代替取模运算 hash % n，提高效率
• 确保元素分布更均匀，特别是在扩容时
• tableSizeFor 方法确保容量总是 2 的幂

8.2 HashMap 和 Hashtable 的区别？

• HashMap 允许 null 键和值，Hashtable 不允许
• HashMap 非同步（非线程安全），Hashtable 同步（线程安全）
• HashMap 性能更好，Hashtable 操作有同步开销
• HashMap 继承自 AbstractMap，Hashtable 继承自 Dictionary
• HashMap 的迭代器是 fail-fast 的

8.3 HashMap 的 put 过程？

1. 计算键的哈希值
2. 确定桶索引位置
3. 遍历该桶，查找是否已存在该键
   • 如果桶为空，直接插入
   • 如果找到相同键，更新值
   • 如果是链表，遍历查找；达到树化阈值则树化
   • 如果是红黑树，按树的方式操作
4. 检查是否需要扩容

8.4 HashMap 的扩容过程？

1. 容量翻倍（新容量 = 旧容量 * 2）
2. 计算新的阈值（新阈值 = 新容量 * 负载因子）
3. 创建新的哈希表
4. 将原哈希表中的所有元素重新哈希到新表
   • 巧妙利用 hash & oldCap == 0 判断元素新位置
   • 元素要么在原位置，要么在原位置 + oldCap 的位置

8.5 HashMap 如何解决哈希冲突？

1. 链地址法：同一个桶存放链表
2. 当链表过长时（>= 8），转换为红黑树
3. 桶容量小于 64 时优先扩容而非树化
4. 当树节点较少时（<= 6），退化为链表
5. 使用高质量的哈希函数减少冲突可能性

九、源码学习收获与思考

9.1 数据结构的选择权衡

HashMap 结合使用了数组、链表和红黑树三种数据结构，根据实际情况动态调整：

• 数组提供 O(1) 的访问性能
• 链表适合少量元素的冲突解决
• 红黑树处理大量冲突时保证 O(log n) 的性能

这种灵活组合的思想值得借鉴，根据实际场景选择最合适的数据结构。

9.2 扩容策略的优化思路

HashMap 的扩容过程中，元素再散列的优化非常巧妙：

• 利用哈希值与旧容量的位运算，快速确定元素新位置
• 只需比较一位即可决定元素去向，避免重新计算全部哈希索引
• 这种技巧在需要频繁迁移数据的场景中非常有价值

9.3 参数选择的启示

阈值的选择（如 8 和 6）经过了精心考量：

• TREEIFY_THRESHOLD = 8：根据泊松分布，链表长度达到 8 的概率已经非常小
• UNTREEIFY_THRESHOLD = 6：小于树化阈值，形成迟滞效应，避免频繁树化/反树化
• 这提醒我们在设计系统时，参数选择应基于数学模型和实际测试

9.4 面向接口设计

HashMap 通过一系列钩子方法（如 afterNodeInsertion）支持子类扩展：

• 这些方法在基类中是空实现
• 子类如 LinkedHashMap 可以重写这些方法实现特定功能
• 很好地体现了开闭原则和模板方法设计模式

十、总结

关键要点：

1. 基于数组 + 链表 + 红黑树的复合结构
2. 容量总是 2 的幂，便于哈希计算
3. 负载因子影响空间利用率与性能
4. 树化/反树化机制动态优化性能
5. 巧妙的扩容算法降低重哈希成本
6. 非线程安全，并发使用需注意

HashMap 桶数据结构与扩容机制的代码详解

桶的数据结构定义

HashMap 的桶结构是通过 Node 类和 TreeNode 类实现的：

基本节点 - Node 类

// 基本的哈希桶节点，用于大多数条目
static class Node<K,V> implements Map.Entry<K,V> {final int hash;     // 哈希值final K key;        // 键V value;            // 值Node<K,V> next;     // 指向下一个节点Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}// 实现 Map.Entry 接口的方法...
}

树节点 - TreeNode 类

// 树形节点，当桶中元素过多时使用
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent;  // 父节点TreeNode<K,V> left;    // 左子节点TreeNode<K,V> right;   // 右子节点TreeNode<K,V> prev;    // 用于删除时解链boolean red;           // 红黑树颜色标记TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}// 红黑树相关操作方法...
}

桶数组定义

// 桶数组，首次使用时初始化，必要时调整大小
transient Node<K,V>[] table;

扩容机制的具体实现

扩容通过 resize() 方法实现：

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;// 计算新容量和新阈值if (oldCap > 0) {// 原容量已达到最大值，不再扩容if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 否则容量翻倍（左移1位），阈值也翻倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; }else if (oldThr > 0) // 使用初始阈值作为初始容量newCap = oldThr;else {               // 使用默认值newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 计算新阈值if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;// 创建新数组@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;// 将旧数组中的元素转移到新数组if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null; // 帮助GCif (e.next == null) // 单个节点直接放入新位置newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode) // 树节点需要特殊处理((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // 链表节点，根据 (e.hash & oldCap) 拆分为两部分Node<K,V> loHead = null, loTail = null;  // 原索引Node<K,V> hiHead = null, hiTail = null;  // 原索引+oldCapNode<K,V> next;do {next = e.next;// 根据新增的位判断节点去向if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 将拆分的两个链表放入新数组if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

链表转树和树转链表（缩容相关）

链表转树通过 treeifyBin() 方法：

final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// 如果桶数组太小，优先扩容而不是树化if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;// 将链表转换为双向链表形式的TreeNodedo {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);// 对双向链表进行树化操作if ((tab[index] = hd) != null)hd.treeify(tab);}
}

树转链表在 split() 方法中实现：

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {TreeNode<K,V> b = this;// 将树拆分为两部分TreeNode<K,V> loHead = null, loTail = null;TreeNode<K,V> hiHead = null, hiTail = null;int lc = 0, hc = 0;// 遍历树节点，根据 hash & bit 分为两组for (TreeNode<K,V> e = b, next; e != null; e = next) {next = (TreeNode<K,V>)e.next;e.next = null;if ((e.hash & bit) == 0) {// 放入 lo 组if ((e.prev = loTail) == null)loHead = e;elseloTail.next = e;loTail = e;++lc;}else {// 放入 hi 组if ((e.prev = hiTail) == null)hiHead = e;elsehiTail.next = e;hiTail = e;++hc;}}// 如果节点数量少于阈值，则转回链表if (loHead != null) {if (lc <= UNTREEIFY_THRESHOLD)tab[index] = loHead.untreeify(map);else {tab[index] = loHead;if (hiHead != null)loHead.treeify(tab);}}if (hiHead != null) {if (hc <= UNTREEIFY_THRESHOLD)tab[index + bit] = hiHead.untreeify(map);else {tab[index + bit] = hiHead;if (loHead != null)hiHead.treeify(tab);}}
}

树转链表的 untreeify() 方法：

final Node<K,V> untreeify(HashMap<K,V> map) {Node<K,V> hd = null, tl = null;// 将 TreeNode 转为普通 Nodefor (Node<K,V> q = this; q != null; q = q.next) {Node<K,V> p = map.replacementNode(q, null);if (tl == null)hd = p;elsetl.next = p;tl = p;}return hd;
}