分析java。util。LinkedHashMap

　　介绍
　　该实现与HashMap不同的是它维护一个双向链表，可以使HashMap有序。与HashMap一样，该类不安全。结构
　　和HashMap的结构非常相似，只不过LinkedHashMap是一个双向链表
　　LinkedHashMap分为两种节点Entry和TreeNode节点
　　Entry节点结构：classEntryK，VextendsHashMap。NodeK，V｛EntryK，Vbefore，after；Entry（inthash，Kkey，Vvalue，NodeK，Vnext）｛super（hash，key，value，next）；｝｝
　　before和after是双向链表中的前继和后继节点
　　TreeNode节点和HashMap中的一样
　　从这里能看出LinkedHashMap是一个双向链表
　　LinkedHashMap有如下属性：transientLinkedHashMap。EntryK，Vhead；transientLinkedHashMap。EntryK，Vtail；finalbooleanaccessOrder；
　　head和tail很好理解就是双向链表的头和尾
　　HashMap中没有accessOrder这个字段，这也是与HashMap最不同的地方，该类有两种取值分别代表不同的意思：true，按照访问顺序排序false，按照插入顺序排序HashMap预留的一些方法
　　HashMap预留了一些方法提供给LinkedHashMap使用LinkedHashMap重写了以下四个方法来保证双向队列能够正常工作创建一个Node节点NodeK，VnewNode（inthash，Kkey，Vvalue，NodeK，Vnext）｛。。。｝创建树节点TreeNodeK，VnewTreeNode（inthash，Kkey，Vvalue，NodeK，Vnext）｛。。。｝树节点和普通节点相互转换NodeK，VreplacementNode（NodeK，Vp，NodeK，Vnext）｛。。。｝TreeNodeK，VreplacementTreeNode（NodeK，Vp，NodeK，Vnext）｛。。。｝HashMap未实现，留给LinkedHashMap实现后置处理访问节点后如何处理voidafterNodeAccess（NodeK，Vp）｛｝插入节点后如何处理voidafterNodeInsertion（booleanevict）｛｝移除节点后如何处理voidafterNodeRemoval（NodeK，Vp）｛｝
　　afterNodeAccess、afterNodeInsertion、afterNodeRemoval这三个方法保证了LinkedHashMap有序，分别会在get、put、remove后调用
　　put和remove都对顺序没有影响，因为在操作的时候已经调整好了（put放在）。但是get是对顺序有影响的（被访问到了），所以需要重写该方法：publicVget（Objectkey）｛NodeK，Ve；获取节点if（（egetNode（hash（key），key））null）returnnull；改变顺序if（accessOrder）afterNodeAccess（e）；returne。value；｝
　　通过afterNodeAccess来改变该节点（P）的顺序，该方法分为一下几步：拆除需要移动的节点P处理前置节点，前置节点有两种情况前置节点为空，表示P为头节点前置节点不为空，表示P为中间节点处理后置节点后置节点为空，表示P为尾节点后置节点不为空，表示P为中间节点将该节点移动到tail处voidafterNodeAccess（NodeK，Ve）｛movenodetolastLinkedHashMap。EntryK，Vlast；if（accessOrder（lasttail）！e）｛LinkedHashMap。EntryK，Vp（LinkedHashMap。EntryK，V）e，bp。before，ap。after；p。afternull；if（bnull）heada；elseb。aftera；if（a！null）a。beforeb；elselastb；if（lastnull）headp；else｛p。beforelast；last。afterp；｝tailp；modCount；｝｝
　　afterNodeInsertion则在putVal中调用
　　基本逻辑是如果参数为true则尝试删除头节点，但是还需要满足头节点是最老的，具体的与removeEldestEntry配合使用，可以继承LinkedHashMap并定制，LinkedHashMap是恒为false的。protectedbooleanremoveEldestEntry（Map。EntryK，Veldest）｛returnfalse；｝
　　如果所有条件都满足则删除头节点voidafterNodeInsertion（booleanevict）｛possiblyremoveeldestLinkedHashMap。EntryK，Vfirst；if（evict（firsthead）！nullremoveEldestEntry（first））｛Kkeyfirst。key；removeNode（hash（key），key，null，false，true）；｝｝
　　afterNodeRemoval则在removeNode成功删除节点之后调用：
　　用来保证在双向链表中删除一个节点仍然能够使结构不被破坏
　　为被删除节点的头和尾节点建立联系：voidafterNodeRemoval（NodeK，Ve）｛unlinkLinkedHashMap。EntryK，Vp（LinkedHashMap。EntryK，V）e，bp。before，ap。after；p。beforep。afternull；if（bnull）heada；elseb。aftera；if（anull）tailb；elsea。beforeb；｝应用实现LRU
　　LRU是一种缓存置换机制，LRU（LeastRecentlyUsed）将最近最少使用的内容替换掉。实现非常简单，每次访问某个元素，就将这个元素浮动到栈顶。这样最靠近栈顶的页面就是最近经常访问的，而被压在栈底的就是最近最少使用的，只需要删除栈底的元素。
　　LinkedHashMap非常方便实现LRU，LinkedHashMap在put操作时同时会判断是否需要删除最老的元素。只需要重写removeEldestEntry方法，使得超过容量就删除最老的元素。
　　下面是具体实现：publicclassLRUK，VextendsLinkedHashMapK，V｛最大容量pNote：用位运算就不需要将十进制转换为二进制，直接就为二进制。privatefinalintMAXCAPACITY130；缓存的容量privateintcapacity；publicLRU（intcapacity）｛this（true，capacity）；｝publicLRU（booleanaccessOrder，intcapacity）｛this（14，0。75f，accessOrder，capacity）；｝publicLRU（intinitialCapacity，floatloadFactor，booleanaccessOrder，intcapacity）｛super（initialCapacity，loadFactor，accessOrder）；this。capacitycapacity；｝｝
　　测试：LRUInteger，IntegerlrunewLRUInteger，Integer（10）；for（inti0；i10；i）｛lru。put（i，ii）；System。out。println（put：（i，ii））；intrandomKey（int）（Math。random（）i）；System。out。println（getrandomKey：lru。get（randomKey））；System。out。println（headlrutail）；｝
　　结果：put：（0，0）get0：0head｛00｝tailput：（1，1）get0：0head｛11，00｝tailput：（2，4）get1：1head｛00，24，11｝tail
　　喜欢的朋友点赞，转发加关注。