LinkedHashSet 与 LinkedHashMap 详解一、在开始之前先回顾两个前置知识要理解LinkedHashSet和LinkedHashMap我们必须先搞清楚两件事情1. HashSet 和 HashMap 的无序问题我们知道HashMap在存储键值对时是通过对 key 计算哈希值然后决定数据放到数组的哪个位置。这意味着——数据在内部的存放顺序和你插入数据的顺序没有关系。举个例子你依次往HashMap中放入三个键值对第一个放入(苹果, 5) 第二个放入(香蕉, 3) 第三个放入(橘子, 8)当你遍历这个HashMap时输出的顺序可能是(香蕉, 3) (橘子, 8) (苹果, 5)输出的顺序完全取决于哈希值的计算结果和内部数组的位置和你放入的先后顺序无关。HashSet也是一样的因为HashSet底层就是用HashMap实现的。2. 什么是链表链表是一种数据结构它的核心思想是每个节点除了存储自己的数据之外还额外记住谁是我的前一个和谁是我的后一个。如果每个节点既记录了前一个节点又记录了后一个节点就叫做双向链表。节点A —— 节点B —— 节点C节点A知道我的下一个是B节点B知道我的上一个是A我的下一个是C节点C知道我的上一个是B通过这种方式我们可以按照链表的顺序从头到尾依次访问每个节点。二、为什么需要 LinkedHashMap问题的提出在实际开发中有时候我们既想要HashMap的高效查找能力通过 key 快速找到 value时间复杂度 O(1)又想要保持数据的插入顺序遍历时先放入的先输出后放入的后输出。普通的HashMap做不到保持插入顺序而ArrayList虽然能保持插入顺序但查找效率低时间复杂度 O(n)。LinkedHashMap就是为了解决这个问题而诞生的它既有 HashMap 的查找效率又能记住插入顺序。三、LinkedHashMap 的内部原理1. 核心思路HashMap 双向链表LinkedHashMap继承自HashMap所以它拥有HashMap的全部能力数组 链表/红黑树的结构通过哈希值定位数据。但它在此基础上做了一个关键的改动每个节点除了存在于 HashMap 的哈希桶结构中还同时被一条双向链表串联起来。这条双向链表按照插入顺序或者访问顺序后面会讲将所有节点连接在一起。2. 节点的结构在普通的HashMap中每个节点Node的结构大致是这样的classNode{inthash;// 哈希值Kkey;// 键Vvalue;// 值Nodenext;// 指向同一个哈希桶中下一个节点解决哈希冲突用的}而在LinkedHashMap中节点被扩展为Entry多了两个指针classEntryextendsHashMap.Node{Entrybefore;// 双向链表中的前一个节点Entryafter;// 双向链表中的后一个节点}请注意区分next这是 HashMap 本身的结构指向同一个哈希桶中的下一个节点用于解决哈希冲突。before和after这是 LinkedHashMap 额外维护的双向链表的指针用于记录插入或访问顺序。它们是两套完全独立的链接关系互不干扰。3. 整体结构图示假设我们依次插入三个键值对(A,1)、(B,2)、(C,3)在 HashMap 的哈希桶数组中它们根据哈希值被分散存储哈希桶数组 [0] - null [1] - Entry(B,2) [2] - null [3] - Entry(A,1) [4] - Entry(C,3) [5] - null ...同时在双向链表中它们按照插入顺序被串起来head tail | | v v Entry(A,1) —— Entry(B,2) —— Entry(C,3)LinkedHashMap内部维护了两个特殊指针head指向双向链表的头节点最先插入的tail指向双向链表的尾节点最后插入的4. 各种操作是怎么工作的1插入操作put当你调用put(D, 4)时第一步按照HashMap的逻辑计算哈希值找到对应的哈希桶位置把新节点放进去。第二步LinkedHashMap重写了一个钩子方法afterNodeInsertion把这个新节点追加到双向链表的尾部。插入前的双向链表 A —— B —— C 插入后的双向链表 A —— B —— C —— D ^ tail2查找操作get当你调用get(B)时按照HashMap的逻辑通过哈希值快速定位到节点返回 value。如果是插入顺序模式默认什么额外操作也不做。如果是访问顺序模式后面会讲会把被访问的节点移动到双向链表的尾部。3删除操作remove当你调用remove(B)时第一步按照HashMap的逻辑从哈希桶中移除这个节点。第二步LinkedHashMap重写了钩子方法afterNodeRemoval同时从双向链表中摘除这个节点让它的前驱节点和后继节点直接相连。删除前A —— B —— C —— D 删除后A —— C —— D4遍历操作这是LinkedHashMap最大的优势所在。当你遍历LinkedHashMap时它不是像HashMap那样遍历哈希桶数组遍历数组的顺序和插入顺序无关而是沿着双向链表从 head 走到 tail。for(Map.EntryString,Integerentry:map.entrySet()){System.out.println(entry.getKey() entry.getValue());}输出结果一定是A 1 B 2 C 3因为遍历是沿着双向链表走的而双向链表的顺序就是插入顺序。5. 两种排序模式LinkedHashMap有一个构造方法参数叫accessOrderpublicLinkedHashMap(intinitialCapacity,floatloadFactor,booleanaccessOrder)accessOrder false默认值插入顺序模式。双向链表按照节点被插入的先后顺序排列。遍历时先插入的先出现。accessOrder true访问顺序模式。每次调用get()或put()更新已有 key时被访问的节点会被移动到双向链表的尾部。遍历时最近最少被访问的在前面最近刚被访问的在后面。访问顺序模式的示例LinkedHashMapString,IntegermapnewLinkedHashMap(16,0.75f,true);map.put(A,1);map.put(B,2);map.put(C,3);// 此时链表顺序A - B - Cmap.get(A);// 访问了 AA 被移动到尾部// 此时链表顺序B - C - Amap.get(B);// 访问了 BB 被移动到尾部// 此时链表顺序C - A - B遍历输出C, A, B访问顺序模式有什么用这种模式天然适合实现LRU 缓存Least Recently Used最近最少使用缓存。LRU 缓存的逻辑是缓存空间有限当缓存满了需要淘汰数据时优先淘汰最久没有被使用的数据。在访问顺序模式下双向链表的头部就是最久没有被使用的节点尾部就是最近刚刚使用过的节点。要淘汰时直接移除头部节点即可。LinkedHashMap甚至提供了一个方法让你方便地实现这个功能protectedbooleanremoveEldestEntry(Map.EntryK,Veldest){returnfalse;// 默认永远不自动移除}你只需要继承LinkedHashMap重写这个方法让它在容量超过限制时返回trueclassLRUCacheK,VextendsLinkedHashMapK,V{privateintmaxSize;publicLRUCache(intmaxSize){super(16,0.75f,true);// accessOrder truethis.maxSizemaxSize;}OverrideprotectedbooleanremoveEldestEntry(Map.EntryK,Veldest){returnsize()maxSize;// 当元素数量超过最大容量时自动移除最老的}}每次put新元素后LinkedHashMap都会调用removeEldestEntry方法。如果返回true就会自动移除双向链表头部的那个节点也就是最久没有被访问的节点。6. LinkedHashMap 的源码关键点1节点类定义staticclassEntryK,VextendsHashMap.NodeK,V{EntryK,Vbefore,after;// 双向链表的前驱和后继Entry(inthash,Kkey,Vvalue,NodeK,Vnext){super(hash,key,value,next);}}2头尾指针transientLinkedHashMap.EntryK,Vhead;// 双向链表的头transientLinkedHashMap.EntryK,Vtail;// 双向链表的尾3三个钩子方法HashMap在设计时就预留了三个空方法供子类重写// HashMap 中的定义空实现voidafterNodeAccess(NodeK,Vp){}voidafterNodeInsertion(booleanevict){}voidafterNodeRemoval(NodeK,Vp){}LinkedHashMap重写了这三个方法afterNodeAccess节点被访问后调用。如果是访问顺序模式就把该节点移动到双向链表尾部。afterNodeInsertion新节点插入后调用。检查是否需要移除最老的节点配合removeEldestEntry。afterNodeRemoval节点被移除后调用。从双向链表中摘除该节点。这种设计模式叫做模板方法模式父类HashMap定义了算法骨架在关键步骤处调用钩子方法子类LinkedHashMap通过重写钩子方法来定制行为而不需要修改父类的主逻辑。4linkNodeLast 方法每次新建节点时LinkedHashMap会调用这个方法把节点追加到双向链表的尾部privatevoidlinkNodeLast(LinkedHashMap.EntryK,Vp){LinkedHashMap.EntryK,Vlasttail;tailp;if(lastnull)headp;// 如果链表为空新节点既是头也是尾else{p.beforelast;// 新节点的前驱指向原来的尾节点last.afterp;// 原来的尾节点的后继指向新节点}}5遍历的实现LinkedHashMap的迭代器从head开始沿着after指针一路走到tailabstractclassLinkedHashIterator{LinkedHashMap.EntryK,Vnext;LinkedHashIterator(){nexthead;// 从头节点开始}finalLinkedHashMap.EntryK,VnextNode(){LinkedHashMap.EntryK,Venext;nexte.after;// 移动到下一个节点returne;}}这就保证了遍历顺序和链表顺序一致。7. 性能分析操作时间复杂度说明putO(1)HashMap 的 O(1) 链表尾部追加 O(1)getO(1)HashMap 的 O(1)访问顺序模式下额外移动节点 O(1)removeO(1)HashMap 的 O(1) 双向链表摘除 O(1)遍历O(n)沿链表遍历n 是实际元素数量和HashMap相比LinkedHashMap的每个操作都只多了常数时间的开销维护双向链表的指针。空间上每个节点多了两个指针before和after也只是常数级别的额外开销。值得一提的是LinkedHashMap的遍历效率实际上优于HashMap。因为HashMap遍历时需要扫描整个哈希桶数组包括空桶而LinkedHashMap直接沿链表走只访问实际存在的元素。四、LinkedHashSet 的内部原理1. 一句话总结LinkedHashSet的实现极其简单它继承自HashSet但内部使用LinkedHashMap作为底层存储而不是普通的HashMap。2. 回顾 HashSet 的实现我们先回顾一下HashSet是怎么实现的publicclassHashSetE{privatetransientHashMapE,Objectmap;privatestaticfinalObjectPRESENTnewObject();// 一个占位对象publicHashSet(){mapnewHashMap();}publicbooleanadd(Ee){returnmap.put(e,PRESENT)null;}publicbooleanremove(Objecto){returnmap.remove(o)PRESENT;}publicbooleancontains(Objecto){returnmap.containsKey(o);}}HashSet的本质就是一个HashMap只不过Set 中的元素被当作HashMap的key来存储。HashMap的value统一使用一个叫PRESENT的虚拟占位对象因为我们不关心 value只关心 key 是否存在。3. LinkedHashSet 怎么切换底层实现HashSet有一个包级私有package-private的构造方法专门为LinkedHashSet准备// HashSet 中的构造方法包级私有外部无法调用HashSet(intinitialCapacity,floatloadFactor,booleandummy){mapnewLinkedHashMap(initialCapacity,loadFactor);}注意这里当dummy参数存在时map被初始化为LinkedHashMap而不是HashMap。LinkedHashSet的构造方法就是调用这个特殊的构造方法publicclassLinkedHashSetEextendsHashSetE{publicLinkedHashSet(){super(16,.75f,true);// 调用 HashSet 的特殊构造方法}publicLinkedHashSet(intinitialCapacity){super(initialCapacity,.75f,true);}publicLinkedHashSet(intinitialCapacity,floatloadFactor){super(initialCapacity,loadFactor,true);}publicLinkedHashSet(Collection?extendsEc){super(Math.max(2*c.size(),11),.75f,true);addAll(c);}}你会发现LinkedHashSet自身几乎没有任何额外的代码。它的全部行为都来自于继承HashSet的所有方法add、remove、contains等。底层的map被替换为LinkedHashMap。既然底层是LinkedHashMap那么所有元素就会被双向链表按插入顺序串联起来。遍历LinkedHashSet时就是在遍历LinkedHashMap的双向链表因此输出顺序就是插入顺序。4. 使用示例LinkedHashSetStringsetnewLinkedHashSet();set.add(Java);set.add(Python);set.add(C);set.add(Go);for(Strings:set){System.out.println(s);}输出结果一定是Java Python C Go和插入顺序完全一致。而如果使用普通的HashSet输出顺序则是不确定的。5. LinkedHashSet 不支持访问顺序模式注意一个细节在LinkedHashSet内部创建LinkedHashMap时使用的是两个参数的构造方法mapnewLinkedHashMap(initialCapacity,loadFactor);accessOrder没有传入默认为false。也就是说LinkedHashSet只支持插入顺序模式不支持访问顺序模式。这是合理的因为Set通常只关心元素是否存在和遍历顺序不太需要按访问顺序排列的功能。五、对比总结1. HashMap vs LinkedHashMap对比维度HashMapLinkedHashMap继承关系直接实现 Map 接口继承 HashMap数据结构数组 链表/红黑树数组 链表/红黑树 双向链表遍历顺序无序不保证任何顺序有序插入顺序或访问顺序节点结构Nodehash, key, value, nextEntry 继承 Node额外增加 before、after性能各操作 O(1)各操作 O(1)略有常数开销遍历效率需扫描整个数组包括空桶只沿链表走效率更高适用场景不关心顺序的快速查找需要保持插入顺序或实现 LRU 缓存2. HashSet vs LinkedHashSet对比维度HashSetLinkedHashSet继承关系实现 Set 接口继承 HashSet底层实现使用 HashMap使用LinkedHashMap遍历顺序无序插入顺序自身代码量有完整实现几乎为零全部依赖父类和底层 Map性能各操作 O(1)各操作 O(1)略有常数开销3. 四者之间的依赖关系LinkedHashSet └── 继承自 HashSet └── 底层使用 LinkedHashMap而非 HashMap └── 继承自 HashMap可以看到整个设计层层嵌套复用性非常高HashMap提供核心的哈希存储能力。LinkedHashMap在HashMap基础上增加双向链表提供有序遍历能力。HashSet利用HashMap实现集合功能。LinkedHashSet利用LinkedHashMap实现有序集合功能。六、使用场景指南场景一需要记住插入顺序当你需要一个 Map遍历时按照放入的先后顺序输出直接用LinkedHashMap默认模式。MapString,StringconfignewLinkedHashMap();config.put(host,localhost);config.put(port,8080);config.put(path,/api);// 遍历时一定按 host - port - path 的顺序输出场景二需要去重但保持顺序当你有一组数据需要去除重复项并且保持原来的顺序用LinkedHashSet。ListStringwordsArrays.asList(apple,banana,apple,cherry,banana);LinkedHashSetStringuniqueWordsnewLinkedHashSet(words);// 结果[apple, banana, cherry]顺序和首次出现的顺序一致场景三实现 LRU 缓存用LinkedHashMap的访问顺序模式 重写removeEldestEntry。// 一个最多缓存 100 个元素的 LRU 缓存MapInteger,StringcachenewLinkedHashMap(16,0.75f,true){OverrideprotectedbooleanremoveEldestEntry(Map.EntryInteger,Stringeldest){returnsize()100;}};场景四不关心顺序只要性能如果你完全不需要保持顺序就用普通的HashMap或HashSet避免维护双向链表带来的额外开销虽然很小但没有必要就不要花。七、最终总结LinkedHashMap的设计精髓在于在 HashMap 的哈希桶结构之上额外维护了一条贯穿所有节点的双向链表。每个节点同时存在于两套结构中——哈希桶负责高效查找双向链表负责记录顺序。两套结构各司其职互不干扰。增删改查时两套结构同步更新只增加了常数级别的开销。LinkedHashSet则是一个极简的实现它自身几乎没有代码全部依赖HashSet的框架加上LinkedHashMap的能力通过切换底层 Map 的实现就完成了有序集合的功能。这种设计体现了面向对象编程中继承复用和组合复用的结合LinkedHashMap通过继承HashMap并重写钩子方法来扩展功能HashSet和LinkedHashSet通过内部组合一个Map来实现集合功能。理解了这一层关系Java 集合框架的整体脉络就清晰了。