LinkedHashMap相关信息介绍（转）

 
Java中的LinkedHashMap
此实现与 HashMap 的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。
此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）。

LinkedHashMap和TreeMap的区别 
首先2个都是map，所以用key取值肯定是没区别的，区别在于用Iterator遍历的时候 
LinkedHashMap保存了记录的插入顺序，先插入的先遍历到 
TreeMap默认是按升序排，也可以指定排序的比较器。遍历的时候按升序遍历。 
http://blog.csdn.net/scelong/article/details/7187142

一.LinkedHashMap的存储结构

  1. LinkedHashMap是继承HashMap，也就继承了HashMap的结构，也就是图中的结构2，在下文中我用"Entry数组+next链表"来描述。而LinkedHashMap有其自己的变量header，也就是图中的结构1，下文中我用"header链表"来描述。
  2. 结构1中的Entry和结构2中的Entry本是同一个，结构1中应该就只有一个header，它指向的是结构2中的e1 e2，但这样会使结构图难画。为了说明问题的方便，我把结构2里的e1 e2在结构1中多画一个。

 

二.LinkedHashMap成员变量

Java代码  

  1. // LinkedHashMap维护了一个链表，header是链表头。此链表不同于HashMap里面的那个next链表  
  2. private transient Entry<K, V> header;  
  3.   
  4. // LRU:Least Recently Used最近最少使用算法  
  5. // accessOrder决定是否使用此算法，accessOrder=true使用  
  6. private final boolean accessOrder;  

 

三.LinkedHashMap里的Entry对象

Java代码  

  1.       // 继承了HashMap.Entry，其他几个方法边用边分析  
  2. rivate static class Entry<K, V> extends HashMap.Entry<K, V> {  
  3. // 增加了两个属性，每个Entry有before Entry和after Entry，就构成了一个链表  
  4. Entry<K, V> before, after;  
  5.   
  6. Entry(int hash, K key, V value, HashMap.Entry<K, V> next) {  
  7.     super(hash, key, value, next);  
  8. }  
  9.   
  10. private void addBefore(Entry<K, V> existingEntry) {  
  11.     .....  
  12. }  
  13.   
  14. void recordAccess(HashMap<K, V> m) {  
  15.     .....  
  16. }  
  17.   
  18. void recordRemoval(HashMap<K, V> m) {  
  19.     .....  
  20. }  
  21.   
  22. private void remove() {  
  23.     .....  
  24. }  

 

四.构造函数

Java代码  

  1. //默认accessOrder为false  
  2. //调用HashMap构造函数  
  3. public LinkedHashMap() {  
  4.     super();  
  5.     accessOrder = false;  
  6. }  
  7.   
  8. //如果想实现LRU算法，参考这个构造函数  
  9. public LinkedHashMap(int initialCapacity, float loadFactor,  
  10.         boolean accessOrder) {  
  11.     super(initialCapacity, loadFactor);  
  12.     this.accessOrder = accessOrder;  
  13. }  
  14.   
  15. //模板方法模式，HashMap构造函数里面的会调用init()方法  
  16. //初始化的时候map里没有任何Entry，让header.before = header.after = header  
  17. void init() {  
  18.     header = new Entry<K, V>(-1, null, null, null);  
  19.     header.before = header.after = header;  
  20. }  

 

五.存数据

Java代码  

  1. //LinkedHashMap没有put(K key, V value)方法，只重写了被put调用的addEntry方法  
  2. //1是HashMap里原有的逻辑，23是LinkedHashMap特有的  
  3. void addEntry(int hash, K key, V value, int bucketIndex) {  
  4.     createEntry(hash, key, value, bucketIndex);  
  5.   
  6.     Entry<K, V> eldest = header.after;  
  7.     //3.如果有必要，移除LRU里面最老的Entry，否则判断是否该resize  
  8.     if (removeEldestEntry(eldest)) {  
  9.         removeEntryForKey(eldest.key);  
  10.     } else {  
  11.         if (size >= threshold)  
  12.             resize(2 * table.length);  
  13.     }  
  14. }  
  15.   
  16. void createEntry(int hash, K key, V value, int bucketIndex) {  
  17.     //1.同HashMap一样：在Entry数组+next链表结构里面加入Entry  
  18.     HashMap.Entry<K, V> old = table[bucketIndex];  
  19.     Entry<K, V> e = new Entry<K, V>(hash, key, value, old);  
  20.     table[bucketIndex] = e;  
  21.     //2.把新Entry也加到header链表结构里面去  
  22.     e.addBefore(header);  
  23.     size++;  
  24. }  
  25.   
  26. //默认是false，我们可以重写此方法  
  27. protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {  
  28.     return false;  
  29. }  
  30.   
  31. private static class Entry<K, V> extends HashMap.Entry<K, V> {  
  32.     //链表插入元素四个步骤，对着图看  
  33.     private void addBefore(Entry<K, V> existingEntry) {  
  34.         after = existingEntry;                //1  
  35.         before = existingEntry.before;     //2  
  36.         before.after = this;                   //3  
  37.         after.before = this;                   //4  
  38.     }  
  39.        }  
  40.        
  41.         //如果走到resize，会调用这里重写的transfer  
  42. //HashMap里面的transfer是n * m次运算，LinkedHashtable重写后是n + m次运算  
  43. void transfer(HashMap.Entry[] newTable) {  
  44.     int newCapacity = newTable.length;  
  45.     //直接遍历header链表，HashMap里面是遍历Entry数组  
  46.     for (Entry<K, V> e = header.after; e != header; e = e.after) {  
  47.         int index = indexFor(e.hash, newCapacity);  
  48.         e.next = newTable[index];  
  49.         newTable[index] = e;  
  50.     }  
  51.  }  

     下面三个图是初始化LinkedHashMap------->添加Entry e1------>添加Entry e2时，LinkedHashMap结构的变化。

 

六.取数据

Java代码  

  1. //重写了get(Object key)方法  
  2. public V get(Object key) {  
  3.     //1.调用HashMap的getEntry方法得到e  
  4.     Entry<K, V> e = (Entry<K, V>) getEntry(key);  
  5.     if (e == null)  
  6.         return null;  
  7.     //2.LinkedHashMap牛B的地方  
  8.     e.recordAccess(this);  
  9.     return e.value;  
  10. }  
  11.   
  12.        // 继承了HashMap.Entry  
  13. private static class Entry<K, V> extends HashMap.Entry<K, V> {  
  14.     //1.此方法提供了LRU的实现  
  15.     //2.通过12两步，把最近使用的当前Entry移到header的before位置，而LinkedHashIterator遍历的方式是从header.after开始遍历，先得到最近使用的Entry  
  16.     //3.最近使用是什么意思：accessOrder为true时，get(Object key)方法会导致Entry最近使用；put(K key, V value)/putForNullKey(value)只有是覆盖操作时会导致Entry最近使用。它们都会触发recordAccess方法从而导致Entry最近使用  
  17.     //4.总结LinkedHashMap迭代方式：accessOrder=false时，迭代出的数据按插入顺序；accessOrder=true时，迭代出的数据按LRU顺序+插入顺序  
  18.     //  HashMap迭代方式：横向数组 * 竖向next链表  
  19.     void recordAccess(HashMap<K, V> m) {  
  20.         LinkedHashMap<K, V> lm = (LinkedHashMap<K, V>) m;  
  21.         //如果使用LRU算法  
  22.         if (lm.accessOrder) {  
  23.             lm.modCount++;  
  24.             //1.从header链表里面移除当前Entry  
  25.             remove();  
  26.             //2.把当前Entry移到header的before位置  
  27.             addBefore(lm.header);  
  28.         }  
  29.     }  
  30.       
  31.     //让当前Entry从header链表消失  
  32.     private void remove() {  
  33.         before.after = after;  
  34.         after.before = before;  
  35.     }  
  36.        }  

 

七.删数据

Java代码  

  1.        // 继承了HashMap.Entry  
  2. private static class Entry<K, V> extends HashMap.Entry<K, V> {  
  3.     //LinkedHashMap没有重写remove(Object key)方法，重写了被remove调用的recordRemoval方法  
  4.     //这个方法的设计也和精髓，也是模板方法模式  
  5.     //HahsMap remove(Object key)把数据从横向数组 * 竖向next链表里面移除之后（就已经完成工作了，所以HashMap里面recordRemoval是空的实现调用了此方法  
  6.     //但在LinkedHashMap里面，还需要移除header链表里面Entry的after和before关系  
  7.     void recordRemoval(HashMap<K, V> m) {  
  8.         remove();  
  9.     }  
  10.       
  11.     //让当前Entry从header链表消失  
  12.     private void remove() {  
  13.         before.after = after;  
  14.         after.before = before;  
  15.     }  
  16. }  

 

八.LinkedHashMap EntrySet遍历

Java代码  

  1.        private abstract class LinkedHashIterator<T> implements Iterator<T> {  
  2.     //从header.after开始遍历  
  3.     Entry<K, V> nextEntry = header.after;  
  4.       
  5.     Entry<K, V> nextEntry() {  
  6.         if (modCount != expectedModCount)  
  7.             throw new ConcurrentModificationException();  
  8.         if (nextEntry == header)  
  9.             throw new NoSuchElementException();  
  10.   
  11.         Entry<K, V> e = lastReturned = nextEntry;  
  12.         nextEntry = e.after;  
  13.         return e;  
  14.     }  
  15. }  
  1. 上图中，遍历的结果是先e1然后e2。
  2. accessOrder为true时，get(e1.key)或者put(e1.key, value)一下，则结构1变成e2------e1------header，遍历的结果就是先e2然后e1。

 

九.总结

  1. LinkedHashMap继承HashMap，结构2里数据结构的变化交给HashMap就行了。
  2. 结构1里数据结构的变化就由LinkedHashMap里重写的方法去实现。
  3. 简言之：LinkedHashMap比HashMap多维护了一个链表。

http://zy19982004.iteye.com/blog/1663303

LinkedHashMap保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。

 

如果需要输出的顺序和输入的相同,那么用LinkedHashMap 可以实现,它还可以按读取顺序来排列.

优点：可前后查询
缺点：效率没有hashmap高

LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。
在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关

LinkedHashMap输出时其元素是有顺序的，而HashMap输出时是随机的，如果Map映射比较复杂而又要求高效率的话，最好使用LinkedHashMap，但是多线程访问的话可能会造成不同步，所以要用Collections.synchronizedMap来包装一下，从而实现同步。其实现一般为：
    Map<String String> map = Collections.synchronizedMap(new LinkedHashMap(<String String));

 

LinkedHashMap和HashMap的区别在于它们的基本数据结构上，看一下LinkedHashMap的基本数据结构，也就是Entry：

private static class Entry<K,V> extends HashMap.Entry<K,V> {
    // These fields comprise the doubly linked list used for iteration.
    Entry<K,V> before, after;

Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
        super(hash, key, value, next);
    }
    ...
}

列一下Entry里面有的一些属性吧：

1、K key

2、V value

3、Entry<K, V> next

4、int hash

5、Entry<K, V> before

6、Entry<K, V> after

其中前面四个，也就是红色部分是从HashMap.Entry中继承过来的；后面两个，也就是蓝色部分是LinkedHashMap独有的。不要搞错了next和before、After，next是用于维护HashMap指定table位置上连接的Entry的顺序的，before、After是用于维护Entry插入的先后顺序的。

还是用图表示一下，列一下属性而已：

 

public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder)；
 initialCapacity   初始容量
 loadFactor    加载因子，一般是 0.75f
 accessOrder   false 基于插入顺序  true  基于访问顺序（get一个元素后，这个元素被加到最后，使用了LRU 最  近最少被使用的调度算法）
如 boolean accessOrder = true；
      Map<String, String> m = new LinkedHashMap<String, String>(20, .80f,  accessOrder  );
      m.put("1", "my"));
      m.put("2", "map"));
      m.put("3", "test"));
      m.get("1");
      m.get("2");
      Log.d("tag",  m);
     若 accessOrder == true;  输出 {3=test, 1=my, 2=map}
         accessOrder == false;  输出 {1=my, 2=map，3=test}

 

顾名思义，LRUCache就是基于LRU算法的Cache（缓存），这个类继承自LinkedHashMap，而类中看到没有什么特别的方法，这说明LRUCache实现缓存LRU功能都是源自LinkedHashMap的。LinkedHashMap可以实现LRU算法的缓存基于两点：

1、LinkedList首先它是一个Map，Map是基于K-V的，和缓存一致

2、LinkedList提供了一个boolean值可以让用户指定是否实现LRU

那么，首先我们了解一下什么是LRU：LRU即Least Recently Used，最近最少使用，也就是说，当缓存满了，会优先淘汰那些最近最不常访问的数据。比方说数据a，1天前访问了；数据b，2天前访问了，缓存满了，优先会淘汰数据b。

我们看一下LinkedList带boolean型参数的构造方法：

public LinkedHashMap(int initialCapacity,
         float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

就是这个accessOrder，它表示：

（1）false，所有的Entry按照插入的顺序排列

（2）true，所有的Entry按照访问的顺序排列

第二点的意思就是，如果有1 2 3这3个Entry，那么访问了1，就把1移到尾部去，即2 3 1。每次访问都把访问的那个数据移到双向队列的尾部去，那么每次要淘汰数据的时候，双向队列最尾的那个数据不就是最不常访问的那个数据了吗？换句话说，双向链表最尾的那个数据就是要淘汰的数据。

"访问"，这个词有两层意思：

1、根据Key拿到Value，也就是get方法

2、修改Key对应的Value，也就是put方法

http://www.mamicode.com/info-detail-1154295.html

 

时间： 2024-10-11 20:26:02

LinkedHashMap相关信息介绍（转）的相关文章

PHP获取音频文件的相关信息

  这篇文章主要介绍了PHP获取音频文件的相关信息的相关资料,非常的实用,有需要的小伙伴可以参考下. 项目需求:现在有一个音频文件上传的功能,在上传后PHP需要获取这个音频文件的相关信息,例如:时长等,由于这个文件是放在买的空间上的,没有像ffmpeg这样的扩展来处理,那么PHP能不能获取到这些信息? 下面是之前在项目中用到的一个用PHP进行音频文件头部信息的读取与写入操作的实现,主要针对 WMA 和 MP3 两种格式,供参考. ? 1 2 3 4 5 6 7 8 9 10 11 12 13 1

火车采集器的相关术语介绍

  火车采集器的相关术语介绍           1.采集任务 采集任务是火车采集器中对于数据采集和数据发布任务的完整配置,包含采集规则和发布模块. 2.采集规则 即我们对如何采集和采集什么的问题给出一些设置让采集器按照设置的规则来执行, 这个设置可以从火车采集器里面导出保存为.ljobx文件,也可以再次导入火车采集器. 3.发布模块 在火车采集器中,发布模块是对"将已经采集到的数据发布到哪里"进行的设置. 包括WEB在线发布模块和数据库发布模块,其设置分别可以导出保存为.wpm文件和

Extjs 点击复选框在表格中增加相关信息行_javascript技巧

功能效果:点击复选框在表格中自动增加相关信息行,复选框取消则表格中内容自动删除 初始效果大概是这样~~~~~ // 定义初始 存放表格数据 var gridItems = []; //省份复选框 var $provinceCheckbox01 = new Ext.form.CheckboxGroup({ xtype: 'checkboxgroup', fieldLabel: '省份选择', labelWidth: 60, columns: 9, vertical: true, margin: '

流媒体相关知识介绍 及其 RTP 应用

一.流媒体简介 随着Internet的日益普及,在网络上传输的数据已经不再局限于文字和图形,而是逐渐向声音和视频等多媒体格式过渡.目前在网络上传输音频/视频(Audio/Video,简称A/V)等多媒体文件时,基本上只有下载和流式传输两种选择.通常说来,A/V文件占据的存储空间都比较大,在带宽受限的网络环境中下载可能要耗费数分钟甚至数小时,所以这种处理方法的延迟很大.如果换用流式传输的话,声音.影像.动画等多媒体文件将由专门的流媒体服务器负责向用户连续.实时地发送,这样用户可以不必等到整个文件全

c#-在C# 项目中，怎么样获取到天气的相关信息

问题描述 在C# 项目中,怎么样获取到天气的相关信息 利用C# 实现如下需求: 1.怎么样获取到当前目前所在位置区域(省.市); 2.根据获取到的当前目前所在位置区域得到该地区的天气预报情况; 例如获取到当前目前所在位置区域的天气预报信息如下: 目前的温度.污染指数.风力.湿度以及是否为晴天,阴天等相关比较全面的天气预报信息; 请问有没有相关提供的API或其它相关参考资料可以实现上面的功能需求,谢谢! 解决方案 第一个可以根据GPS(如果有)或者IP数据库查找位置 第二个,参考http://zh

使用jquery实现鼠标滑过弹出更多相关信息层附源码下载_jquery

当要在有限的空间展示更多的信息时,我们经常会采取鼠标滑过弹出更多相关信息层,提高互动性.尤其可以应用在公司照片墙.招聘网站求职者信息展示等等场景. 本文结合实例和大家分享下使用jQuery实现滑过图片展示信息效果.当鼠标滑向照片时,会弹出对应的照片的详细介绍信息,请看演示效果: 效果展示     源码下载 HTML 首先我们准备页面素材,页面上由多组图片<li>密集组成,同时有图片对应的相关说明信息,用于展示详细信息效果. <div class="demo">

编程实战——电影管理器之利用MediaInfo获取高清视频文件的相关信息

随着高速(20M)宽带.HTPC.大容量硬盘(3T)的普及,下载高清片并利用大屏幕观看也成为普通的事情. 随着下载影片的增多,管理就有了问题,有时在茫茫文件夹下找寻一个影片也是一件费时费力的事. 于是萌生了自己编写电影管理器的想法,并逐步逐步在实现.利用博客记录编写的过程,也是和网友之间的交流.期望在交流的过程中,网友能提出一些中肯的意见,使自己少走些弯路.   我在拿到一个高清视频文件时.我希望能有办法获知以下的信息 文件名:视频文件的文件名,这个比较简单,利用FileInfo类就能获得 文件

SqlServer如何通过SQL语句获取处理器(CPU)、内存（Memory）、磁盘（Disk）以及操作系统相关信息

在SQL SERVER中如何通过SQL语句获取服务器硬件和系统信息呢?下面介绍一下如何通过SQL语句获取处理器(CPU).内存(Memory).磁盘(Disk)以及操作系统相关信息.如有不足和遗漏,敬请补充.谢谢! 一:查看数据库服务器CPU的信息 ---SQL 1:获取数据库服务器的CPU型号 EXEC xp_instance_regread 'HKEY_LOCAL_MACHINE', 'HARDWARE\DESCRIPTION\System\CentralProcessor\0', 'Pro

c++-本地电脑连接着设备，我想远程用C++编的控制软件控制这台设备，怎样才能获得这台设备的相关信息？

问题描述 本地电脑连接着设备,我想远程用C++编的控制软件控制这台设备,怎样才能获得这台设备的相关信息? 本地电脑连接着设备,我想远程用C++编的控制软件控制这台设备,怎样才能获得这台设备的相关信息? 解决方案 拿到设备相应的api接口即可,进行对应的编程控制. 解决方案二: http://blog.csdn.net/ouyang_linux007/article/details/7637141