linkedhashmap的数据结构（LinkedHashSet和LinkedHashMap手记）

LinkedHashSet和LinkedHashMap

这两个类维护一个双向链表    
    
    
    
  ，可以记住插入元素的顺序    
    
    
    
。

实例：LinkedHashMap

可以使用访问顺序来迭代处理映射条目


     


     


     


     
，当get或者put访问元素时
 




 




 




 




，受影响的条目从当前位置删除   

   

   

   

 ，然后放到末尾 

     

     

     

     ，只影响链表

  




  




  




  




，不影响散列表的桶     


     


     


     


  。

LinkedHashMap<K,V>(initialCapacity, loadFactor,true) //构造访问顺序迭代处理的Map

这样的好处是  


  


  


  


，可以保持    
    
    
    
”最近最少使用原则“  
     
     
     
     ，这样当容器满的时候可以通过覆盖removeEldestEntry来删掉前面的很少使用的缓存


   




   




   




   



，




 




 




 




 
。

// 定义一个容量为10 



 



 



 



，装填因子为0.75                      ，访问顺序的cache



    




    




    




    


， // 当size/容量>装填因子时



















，散列表就会再次散列
   

   

   

   

。 var cache = new LinkedHashMap<String,Integer>(10, 0.75F, true){ // 复写该方法                      ，则会删除掉Map中最不常访问的元素     

     

     

     

 。 protected boolean removeEldestEntry(Map.Entry<String,Integer> eldest){ // 当容器的内容>5时删掉最不常访问的元素 return size() > 5; } }; cache.put("zs", 1); cache.put("ls", 2); cache.put("ww", 2); cache.put("zs",3); // 对张s进行覆盖



     



     



     



     

，则会出现在最后访问之后 cache.forEach((k,v)->{ System.out.println(k+":"+v); }); /* ls:2 ww:2 zs:3 */ System.out.println("================"); cache.put("ml", 1); cache.put("zl", 3); cache.forEach((k,v)->{ System.out.println(k+":"+v); }); /*此时Map的size已经到5



















，添加一个元素后    
    
    
    
  ，将最不常访问到的第一个元素删除 ls:2 ww:2 zs:3 ml:1 zl:3 */ System.out.println("***************"); cache.put("lll", 4); cache.forEach((k,v)->{ System.out.println(k+":"+v); }); /* ww:2 zs:3 ml:1 zl:3 lll:4 */