听说同学你搞不懂Java的LinkedHashMap，可笑
同学们好啊，还记得 HashMap 那篇吗？我自己感觉写得非常棒啊，既通俗易懂，又深入源码，真的是分析得透透彻彻、清清楚楚、明明白白的。（一不小心又上仨成语？）HashMap 哪哪都好，真的，只要你想用键值对，第一时间就应该想到它。 但俗话说了，“金无足赤人无完人”，HashMap 也不例外。有一种需求它就满足不了，假如我们需要一个按照插入顺序来排列的键值对集合，那 HashMap 就无能为力了。因为为了提高查找效率，HashMap 在插入的时候对键做了一次哈希算法，这就导致插入的元素是无序的。 对这一点还不太明白的同学，可以再回到 HashMap 那一篇，看看我对 put() 方法的讲解。 finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){HashMap.Node<K,V>[]tab;HashMap.Node<K,V>p;intn,i;//①、数组table为null时，调用resize方法创建默认大小的数组if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;//②、计算下标，如果该位置上没有值，则填充if((p=tab[i=(n-1)&hash])==null)tab[i]=newNode(hash,key,value,null);} 这个公式 i = (n - 1) & hash 计算后的值并不是按照 0、1、2、3、4、5 这样有序的下标将键值对插入到数组当中的，而是有一定的随机性。 那 LinkedHashMap 就是为这个需求应运而生的。LinkedHashMap 继承了 HashMap，所以 HashMap 有的关于键值对的功能，它也有了。 publicclassLinkedHashMap<K,V>extendsHashMap<K,V>implementsMap<K,V>{} 此外，LinkedHashMap 内部又追加了双向链表，来维护元素的插入顺序。注意下面代码中的 before 和 after，它俩就是用来维护当前元素的前一个元素和后一个元素的顺序的。 staticclassEntry<K,V>extendsHashMap.Node<K,V>{LinkedHashMap.Entry<K,V>before,after;Entry(inthash,Kkey,Vvalue,HashMap.Node<K,V>next){super(hash,key,value,next);}} 关于双向链表，同学们可以回头看一遍我写的 LinkedList 那篇文章，会对理解本篇的 LinkedHashMap 有很大的帮助。 在继续下面的内容之前，我先贴一张图片，给大家增添一点乐趣——看我这心操的。UUID 那篇文章的标题里用了“可笑”和“你”，结果就看到了下面这么乐呵的留言。 （到底是知道还是不知道，我搞不清楚了。。。）那 LinkedHashMap 这篇也用了“你”和“可笑”，不知道到时候会不会有人继续对号入座啊，想想就觉得特别欢乐。 01、插入顺序 在 HashMap 那篇文章里，我有讲解到一点，不知道同学们记不记得，就是 null 会插入到 HashMap 的第一位。 Map<String,String>hashMap=newHashMap<>();hashMap.put("沉","沉默王二");hashMap.put("默","沉默王二");hashMap.put("王","沉默王二");hashMap.put("二","沉默王二");hashMap.put(null,null);for(Stringkey:hashMap.keySet()){System.out.println(key+":"+hashMap.get(key));} 输出的结果是： null:null默:沉默王二沉:沉默王二王:沉默王二二:沉默王二 虽然 null 最后一位 put 进去的，但在遍历输出的时候，跑到了第一位。 那再来对比看一下 LinkedHashMap。 Map<String,String>linkedHashMap=newLinkedHashMap<>();linkedHashMap.put("沉","沉默王二");linkedHashMap.put("默","沉默王二");linkedHashMap.put("王","沉默王二");linkedHashMap.put("二","沉默王二");linkedHashMap.put(null,null);for(Stringkey:linkedHashMap.keySet()){System.out.println(key+":"+linkedHashMap.get(key));} 输出结果是： 沉:沉默王二默:沉默王二王:沉默王二二:沉默王二null:null null 在最后一位插入，在最后一位输出。 输出结果可以再次证明，HashMap 是无序的，LinkedHashMap 是可以维持插入顺序的。 那 LinkedHashMap 是如何做到这一点呢？我相信同学们和我一样，非常希望知道原因。 要想搞清楚，就需要深入研究一下 LinkedHashMap 的源码。LinkedHashMap 并未重写 HashMap 的 put() 方法，而是重写了 put() 方法需要调用的内部方法 newNode()。 HashMap.Node<K,V>newNode(inthash,Kkey,Vvalue,HashMap.Node<K,V>e){LinkedHashMap.Entry<K,V>p=newLinkedHashMap.Entry<>(hash,key,value,e);linkNodeLast(p);returnp;} 前面说了，LinkedHashMap.Entry 继承了 HashMap.Node，并且追加了两个字段 before 和 after。 那，紧接着来看看 linkNodeLast() 方法： privatevoidlinkNodeLast(LinkedHashMap.Entry<K,V>p){LinkedHashMap.Entry<K,V>last=tail;tail=p;if(last==null)head=p;else{p.before=last;last.after=p;}} 看到了吧，LinkedHashMap 在添加第一个元素的时候，会把 head 赋值为第一个元素，等到第二个元素添加进来的时候，会把第二个元素的 before 赋值为第一个元素，第一个元素的 afer 赋值为第二个元素。 这就保证了键值对是按照插入顺序排列的，明白了吧？ 注：我用到的 JDK 版本为 14。 02、访问顺序 LinkedHashMap 不仅能够维持插入顺序，还能够维持访问顺序。访问包括调用 get() 方法、remove() 方法和 put() 方法。 要维护访问顺序，需要我们在声明 LinkedHashMap 的时候指定三个参数。 LinkedHashMap<String,String>map=newLinkedHashMap<>(16,.75f,true); 第一个参数和第二个参数，看过 HashMap 的同学们应该很熟悉了，指的是初始容量和负载因子。 第三个参数如果为 true 的话，就表示 LinkedHashMap 要维护访问顺序；否则，维护插入顺序。默认是 false。 Map<String,String>linkedHashMap=newLinkedHashMap<>(16,.75f,true);linkedHashMap.put("沉","沉默王二");linkedHashMap.put("默","沉默王二");linkedHashMap.put("王","沉默王二");linkedHashMap.put("二","沉默王二");System.out.println(linkedHashMap);linkedHashMap.get("默");System.out.println(linkedHashMap);linkedHashMap.get("王");System.out.println(linkedHashMap); 输出的结果如下所示： {沉=沉默王二,默=沉默王二,王=沉默王二,二=沉默王二}{沉=沉默王二,王=沉默王二,二=沉默王二,默=沉默王二}{沉=沉默王二,二=沉默王二,默=沉默王二,王=沉默王二} 当我们使用 get() 方法访问键位“默”的元素后，输出结果中，默=沉默王二 在最后；当我们访问键位“王”的元素后，输出结果中，王=沉默王二 在最后，默=沉默王二 在倒数第二位。 也就是说，最不经常访问的放在头部，这就有意思了。有意思在哪呢？ 我们可以使用 LinkedHashMap 来实现 LRU 缓存，LRU 是 Least Recently Used 的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。 publicclassMyLinkedHashMap<K,V>extendsLinkedHashMap<K,V>{privatestaticfinalintMAX_ENTRIES=5;publicMyLinkedHashMap(intinitialCapacity,floatloadFactor,booleanaccessOrder){super(initialCapacity,loadFactor,accessOrder);}@OverrideprotectedbooleanremoveEldestEntry(Map.Entryeldest){returnsize()>MAX_ENTRIES;}} MyLinkedHashMap 是一个自定义类，它继承了 LinkedHashMap，并且重写了 removeEldestEntry() 方法——使 Map 最多可容纳 5 个元素，超出后就淘汰。 我们来测试一下。 MyLinkedHashMap<String,String>map=newMyLinkedHashMap<>(16,0.75f,true);map.put("沉","沉默王二");map.put("默","沉默王二");map.put("王","沉默王二");map.put("二","沉默王二");map.put("一枚有趣的程序员","一枚有趣的程序员");System.out.println(map);map.put("一枚有颜值的程序员","一枚有颜值的程序员");System.out.println(map);map.put("一枚有才华的程序员","一枚有才华的程序员");System.out.println(map); 输出结果如下所示： {沉=沉默王二,默=沉默王二,王=沉默王二,二=沉默王二,一枚有趣的程序员=一枚有趣的程序员}{默=沉默王二,王=沉默王二,二=沉默王二,一枚有趣的程序员=一枚有趣的程序员,一枚有颜值的程序员=一枚有颜值的程序员}{王=沉默王二,二=沉默王二,一枚有趣的程序员=一枚有趣的程序员,一枚有颜值的程序员=一枚有颜值的程序员,一枚有才华的程序员=一枚有才华的程序员} 沉=沉默王二 和 默=沉默王二 依次被淘汰出局。 假如在 put “一枚有才华的程序员”之前 get 了键位为“默”的元素： MyLinkedHashMap<String,String>map=newMyLinkedHashMap<>(16,0.75f,true);map.put("沉","沉默王二");map.put("默","沉默王二");map.put("王","沉默王二");map.put("二","沉默王二");map.put("一枚有趣的程序员","一枚有趣的程序员");System.out.println(map);map.put("一枚有颜值的程序员","一枚有颜值的程序员");System.out.println(map);map.get("默");map.put("一枚有才华的程序员","一枚有才华的程序员");System.out.println(map); 那输出结果就变了，对吧？ {沉=沉默王二,默=沉默王二,王=沉默王二,二=沉默王二,一枚有趣的程序员=一枚有趣的程序员}{默=沉默王二,王=沉默王二,二=沉默王二,一枚有趣的程序员=一枚有趣的程序员,一枚有颜值的程序员=一枚有颜值的程序员}{二=沉默王二,一枚有趣的程序员=一枚有趣的程序员,一枚有颜值的程序员=一枚有颜值的程序员,默=沉默王二,一枚有才华的程序员=一枚有才华的程序员} 沉=沉默王二 和 王=沉默王二 被淘汰出局了。 那 LinkedHashMap 是如何来维持访问顺序呢？同学们感兴趣的话，可以研究一下下面这三个方法。 voidafterNodeAccess(Node<K,V>p){}voidafterNodeInsertion(booleanevict){}voidafterNodeRemoval(Node<K,V>p){} afterNodeAccess() 会在调用 get() 方法的时候被调用，afterNodeInsertion() 会在调用 put() 方法的时候被调用，afterNodeRemoval() 会在调用 remove() 方法的时候被调用。 我来以 afterNodeAccess() 为例来讲解一下。 voidafterNodeAccess(HashMap.Node<K,V>e){//movenodetolastLinkedHashMap.Entry<K,V>last;if(accessOrder&&(last=tail)!=e){LinkedHashMap.Entry<K,V>p=(LinkedHashMap.Entry<K,V>)e,b=p.before,a=p.after;p.after=null;if(b==null)head=a;elseb.after=a;if(a!=null)a.before=b;elselast=b;if(last==null)head=p;else{p.before=last;last.after=p;}tail=p;++modCount;}} 哪个元素被 get 就把哪个元素放在最后。了解了吧？ 那同学们可能还想知道，为什么 LinkedHashMap 能实现 LRU 缓存，把最不经常访问的那个元素淘汰？ 在插入元素的时候，需要调用 put() 方法，该方法最后会调用 afterNodeInsertion() 方法，这个方法被 LinkedHashMap 重写了。 voidafterNodeInsertion(booleanevict){//possiblyremoveeldestLinkedHashMap.Entry<K,V>first;if(evict&&(first=head)!=null&&removeEldestEntry(first)){Kkey=first.key;removeNode(hash(key),key,null,false,true);}} removeEldestEntry() 方法会判断第一个元素是否超出了可容纳的最大范围，如果超出，那就会调用 removeNode() 方法对最不经常访问的那个元素进行删除。 03、最后 由于 LinkedHashMap 要维护双向链表，所以 LinkedHashMap 在插入、删除操作的时候，花费的时间要比 HashMap 多一些。 这也是没办法的事，对吧，欲戴皇冠必承其重嘛。既然想要维护元素的顺序，总要付出点代价才行。 那这篇文章就到此戛然而止了，同学们要觉得意犹未尽，请肆无忌惮地留言告诉我哦。（一不小心又在文末甩仨成语，有点文化底蕴，对吧？） ------------------ 公众号：沉默王二（ID：cmower）CSDN：沉默王二这是一个有颜值却靠才华吃饭的程序员，你知道，他的文章风趣幽默，读起来就好像花钱一样爽快。 长按下图二维码关注，你将感受到一个有趣的灵魂，且每篇文章都有干货。 ------------------ 原创不易，莫要白票，如果觉得有点用的话，请毫不留情地素质三连吧，分享、点赞、在看，我不挑，因为这将是我写作更多优质文章的最强动力。 PS：公布一下周日的中奖名单，有小伙伴表示，人生第一次中奖啊，激动啊，二哥，你咋这么棒！哎呀，那股激动的劲啊，放心，还会有的，只要你们想白嫖，二哥就给机会。 本文分享自微信公众号 - 沉默王二（cmower）。如有侵权，请联系 support@oschina.cn 删除。本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
