linkedhashmap 迭代仅依赖双向链表,从 head 出发沿 after 引用遍历,性能与元素个数成正比;插入顺序按节点追加到 tail 维护,访问顺序则通过移动节点至 tail 实现 lru;所有操作均同步更新哈希表与链表以保证一致性。

双向链表是迭代顺序的唯一依据
LinkedHashMap 迭代时不扫描哈希桶数组(table),而是从 head 节点出发,沿着每个节点的 after 引用逐个跳转,直到为 null。这意味着:
- 迭代性能只和实际元素个数有关,哪怕哈希表扩容到 65536,只要存了 3 个键值对,遍历就只走 3 步
- 顺序完全由链表结构决定,与 hash 分布、数组长度、是否发生扩容都无关
- 每个 Entry 是 HashMap.Node 的子类,额外携带 before 和 after 两个引用,构成双向连接
插入顺序:新节点永远追加到链表尾部
默认构造的 LinkedHashMap(accessOrder = false)按插入时间线组织链表:
- 首次插入:新建节点,head 和 tail 都指向它
- 后续插入:新节点的 before 指向当前 tail;原 tail.after 指向新节点;再把 tail 更新为新节点
- 重复 put 同一个 key:复用原有节点、仅更新 value,不创建新节点,因此链表位置完全不动
- putIfAbsent、computeIfAbsent 等方法也只在真正新增时才链接进链表
访问顺序(Access Order):get/put 触发节点移动到尾部
当构造时传入 true(如 new LinkedHashMap(16, 0.75f, true)),链表不再固定插入序,而变成“最近访问在尾,最久未用在头”:
- get(key) 或 put(key, value) 访问已有节点时,自动调用 afterNodeAccess()
- 该方法将目标节点从原位置摘除(前后节点互相连接),再插到 tail 之后,成为新的尾节点
- 迭代仍走 same head→after 路径,但此时路径反映的是访问时间倒序,天然支持 LRU 缓存语义
- 配合重写 removeEldestEntry(),就能在插入新元素时自动淘汰头部最老项
删除与反序列化需同步维护链表完整性
链表不是装饰性结构,而是核心数据视图,任何修改都必须双路同步:
- remove(key):既从哈希桶中移除节点,也从双向链表中断开(before.after = after,after.before = before),并更新 head/tail(若被删的是头或尾)
- 反序列化 时,head 和 tail 是 transient 字段,不会被自动恢复,所以 LinkedHashMap 自行实现了 readObject() 来重建链表顺序
- 所有操作——插入、访问、删除——都确保哈希表和双向链表状态严格一致,否则迭代结果会错乱或出现空指针











