编程开发 购物 网址 游戏 小说 歌词 地图 快照 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 开发 租车 短信 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
移动开发 架构设计 编程语言 互联网 开发经验 Web前端 开发总结
开发杂谈 系统运维 研发管理 数据库 云 计 算 Java开发
VC(MFC) Delphi VB C++(C语言) C++ Builder 其它开发语言 云计算 Java开发 .Net开发 IOS开发 Android开发 PHP语言 JavaScript
ASP语言 HTML(CSS) HTML5 Apache MSSQL数据库 Oracle数据库 PowerBuilder Informatica 其它数据库 硬件及嵌入式开发 Linux开发资料
  编程开发知识库 -> 编程语言 -> LinkedHashMap源码解析 -> 正文阅读
 

[编程语言]LinkedHashMap源码解析[第1页]

一 简介 1、概念
  LinkedHashMap是HashMap的子类,与HashMap有着同样的存储结构,但它加入了一个双向链表的头结点,将所有put到LinkedHashmap的节点一一串成了一个双向循环链表,因此它保留了节点插入的顺序,可以使节点的输出顺序与输入顺序相同。
LinkedHashMap的遍历速度只和实际的数据有关,和容量无关。
LinkedHashMap是非线程安全的,只在单线程环境下使用。
2、成员变量

//双链表的头结点
private transient Entry<K,V> header;

//该链表遍历的顺序,false为插入顺序,true为访问顺序
private final boolean accessOrder;

//LinkedHashMap的Entry元素。继承HashMap的Entry元素,又保存了其上一个元素before和下一个元素after的引用。
private static class Entry<K,V> extends HashMap.Entry<K,V>

3、构造函数

public LinkedHashMap();

public LinkedHashMap(int initialCapacity);

public LinkedHashMap(int initialCapacity, float loadFactor);

public LinkedHashMap(Map<? extends K, ? extends V> m);

public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder);

  当accessOrder为true时,会去创建一个按照访问的顺序的而排序的LinkedHashMap。这种类型的map适合去构建LRU(最近最少使用)缓存。
  前四个构造方法都将accessOrder设为false,说明LinkedHashMap默认是按照插入顺序排序的,而第五个构造方法可以自定义传入的accessOrder的值,因此可以指定双向循环链表中元素的排序规则,一般要用LinkedHashMap实现LRU算法,就要用该构造方法,将accessOrder置为true。
4、成员方法概览

public void clear();

public boolean containsValue(Object value);

public V get(Object key);

  LinkedHash只覆写了父类的这3个公共方法,其余的还是使用父类的一些成员方法。
5、顺序控制
  accessOrder控制了该链表遍历的顺序,当它false时,表示双向链表中的元素按照Entry插入LinkedHashMap到中的先后顺序排序,即每次put到LinkedHashMap中的Entry都放在双向链表的尾部,这样遍历双向链表时,Entry的输出顺序便和插入的顺序一致,这也是默认的双向链表的存储顺序;当它为true时,表示双向链表中的元素按照访问的先后顺序排列,可以看到,虽然Entry插入链表的顺序依然是按照其put到LinkedHashMap中的顺序,但put和get方法均有调用recordAccess方法(put方法在key相同,覆盖原有的Entry的情况下调用recordAccess方法),该方法判断accessOrder是否为true,如果是,则将当前访问的Entry(put进来的Entry或get出来的Entry)移到双向链表的尾部(key不相同时,put新Entry时,会调用addEntry,它会调用creatEntry,该方法同样将新插入的元素放入到双向链表的尾部,既符合插入的先后顺序,又符合访问的先后顺序,因为这时该Entry也被访问了),否则,什么也不做。
二 源码分析 1、初始化

void init() {
    header = new Entry<>(-1, null, null, null);
    header.before = header.after = header;
}

  该方法覆写父类的init()方法(HashMap中的init方法为空),该方法在父类的构造方法和Clone、readObject中在插入元素前被调用,然后初始化一个空的双向循环链表,头结点中不保存数据,头结点的下一个节点才开始保存数据。
2、顺序调整

void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    if (lm.accessOrder) {
        lm.modCount++;
        remove();
        addBefore(lm.header);
    }
}

  该方法覆写了HashMap中的recordAccess方法(HashMap中该方法为空),LinkedHashMap没有自己实现put方法,当调用父类的put方法,在发现插入的key已经存在时,会调用该方法。调用LinkedHashmap覆写的get方法时,也会调用到该方法。
  当accessOrder为true时,该方法提供了LRU算法的实现,它将最近使用的Entry放到双向循环链表的尾部,保持LinkedHashMap中的键值对顺序是按照访问循序排列。如果accessOrder为false时,该方法不做操作。
3、扩容

void transfer(HashMap.Entry[] newTable) {  
    int newCapacity = newTable.length;  
    for (Entry<K,V> e = header.after; e != header; e = e.after) {  
        int index = indexFor(e.hash, newCapacity);  
        e.next = newTable[index];  
        newTable[index] = e;  
    }  
}

  该方法覆写HashMap中的transfer方法,它在父类的resize方法中被调用,扩容后,将key-value对重新映射到新的newTable中。覆写该方法的目的是为了提高复制的效率,这里充分利用双向循环链表的特点进行迭代,不用对底层的数组进行for循环。
4、get操作

public V get(Object key) {
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null)
        return null;
    e.recordAccess(this);
    return e.value;
} 

  覆写HashMap中的get方法,该方法与父类HashMap中的实现唯一不同的地方在于:如果查询的结果不为空,则调用顺序调整方法recordAccess()去调整LinkedHashMap中的元素顺序。
5、put操纵
  LinkedHashMap没有覆写父类的put方法,只是覆写了put方法中调用的addEntry方法,在增加元素时,同时将元素添加到LinkedHashMap中维护得双向循环链表。

void addEntry(int hash, K key, V value, int bucketIndex) {
    super.addEntry(hash, key, value, bucketIndex);

    // Remove eldest entry if instructed
    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    }
}


void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    e.addBefore(header);
    size++;
}

6、containsValue操作(值存在判断)

public boolean containsValue(Object value) {
    // Overridden to take advantage of faster iterator
    if (value==null) {
        for (Entry e = header.after; e != header; e = e.after)
            if (e.value==null)
                return true;
    } else {
        for (Entry e = header.after; e != header; e = e.after)
            if (value.equals(e.value))
                return true;
    }
    return false;
}

  该方法覆写HashMap中的containsValue方法,覆写该方法的目的同样是为了提高查询的效率,利用双向循环链表的特点进行查询,少了对数组的外层for循环。
7、清除操作

public void clear() {
    super.clear();
    header.before = header.after = header;
}

  清空HashMap,因为LinkedHashMap中额外维护利率一个双向链表,所以需要将双向链表还原为只有头结点的空链表
三 应用 1、使用linkedHashMap实现LRU缓存
  覆写了LinkedHashMap的removeEldestEntry方法,因为LinkedHashMap覆写了父类的addEntry方法,每次put元素时,addEntry方法都会调用该方法去判断是否替换最近最少使用的元素。当达到缓存的容量上线时removeEldestEntry就会返回ture,从而调用removeEntryForKey方法将最近最少使用的元素直接删除。

public class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V>{

    private static final long serialVersionUID = 1L;  

    //定义缓存的容量  
    private int capacity;  

    //带参数的构造器     
    public LRULinkedHashMap(int capacity){  
        //调用LinkedHashMap的构造器,传入以下参数  
        super(16,0.75f,true);  
        //传入指定的缓存最大容量  
        this.capacity=capacity;  
    }  

    //实现LRU的关键方法,如果map里面的元素个数大于了缓存最大容量,则删除链表的顶端元素  
    @Override  
    public boolean removeEldestEntry(Map.Entry<K, V> eldest){    
        return size()>capacity;  
    }    
}

测试类

public class LRUTest {

    public static void main(String[] args) {
        Map<String,Object> map = new LRULinkedHashMap<String,Object>(5);
        map.put("a", "11");
        map.put("b", "22");
        map.put("c", "33");
        map.put("d", "44");
        map.put("e", "55");
        map.put("f", "66");
        map.put("d", "77");
        map.put("b", "88");

        for(Map.Entry<String, Object> entry:map.entrySet())
            System.out.println(entry.getKey()+":"+entry.getValue());
    }

}

结果如下
c:33
e:55
f:66
d:77
b:88
参考链接:http://blog.csdn.net/exceptional_derek/article/details/11713255
阅读全文
版权声明:本文为博主原创文章,未经博主允许不得转载。
本文已收录于以下专栏:

发表评论
HTML/XML objective-c Delphi Ruby PHP C# C++ JavaScript Visual Basic Python Java CSS SQL 其它
相关文章推荐
java 源码解析(02) LinkedHashMap
一、总述 LinkedHashMap是一个有序的HashMap。HashMap源码分析请看《java 源码解析(01) HashMap》。 特点: a、继承于HashMap,基于HashMap实...
Jejay 2017-07-15 23:44 172 [Java容器]LinkedHashMap实现原理与源码解析
LinkedHashMap
u014458048 2017-03-20 22:44 72 JDK之LinkedHashMap源码解析
刚入java一年的萌新,对于简单的使用已毫不满足,最终为了一探究竟,翻开了JDK的源码,以下观点为自己的理解及看了多篇博客的总结,欢迎各位大神指出不对的地方,当然也欢迎和我一样刚学的同学,一起加油努力...
wxl1234579 2017-02-07 17:16 89 LinkedHashMap类源码解析
LinkedHashMap 1.通过链表实现存储继承HashMap 实现Mappublic class LinkedHashMap extends HashMap implemen...
qunxingvip 2016-07-17 11:38 1107 java LinkedHashMap源码解析
本源码解析是基于JDK1.7,本篇与HashMap源码解析较强的关联性LinkedHashMap概要 LinkedHashMap是基于HashTable与LinkedList原理实现的 HashMap...
StubbornAnt 2016-06-13 19:01 1357 LinkedHashMap源码解析 给jdk写注释系列之jdk1.6容器(5)
前面分析了HashMap的实现,我们知道其底层数据存储是一个hash表(数组+单向链表)。接下来我们看一下另一个LinkedHashMap,它是HashMap的一个子类,他在HashMap的基础上维持...
ProfeSir 2016-08-05 21:12 141 LinkedHashMap 源码解析
HashMap使用哈希表来存储数据,并用拉链法来处理冲突。1. 关于容量的问题,使用2的幂方如果给定Map一个初始容量,但看构造器里,会寻找比这个初始值大的2的幂方// Find a power of...
never_cxb 2015-11-22 22:22 351 《Java源码解析》集合框架Map之LinkedHashMap
2016-12-24 16:01 以前都没有贴出来运行环境,今天加上OS和JDK版本,因为发现不同版本实现源码有些许差别: OS : MacOS 10.11 JDK: jdk1....
u010853261 2016-12-24 15:21 234 【源码解析】JDK源码之LinkedHashMap
LinkedHashMap源码,基于jdk1.6.43
kingdz618 2017-04-11 08:21 194 容器学习三:LinkedHashMap源码分析
原文:http://zy19982004.iteye.com/blog/1663303
kevin_li0719 2014-08-04 00:52 321
u013940812 +关注
原创 22 粉丝 0 喜欢 0 码云  
他的最新文章 更多文章
LinkedHashMap源码解析 Hashtable源码解析 ArrayList源码解析 Mongo 聚合框架优化-Aggregate(四)
在线课程

【免费】搜狗机器翻译技术分享
讲师:

深度学习在推荐领域的应用和实践
讲师:吴岸城
热门文章 MongoDB 安装及启动
1167
Dubbo初识
711
Druid连接池
417
面试-力控华康
211
Mongo 聚合框架-Aggregate(三)
169
0
  编程语言 最新文章
洛谷P3916 图的遍历_graph
Java_7
C#使用UdpClient发送和接收UDP数据示例 16进
php必会基础
Java判断是否为整数的5种方法
Socket 双向传输问题
腾讯手QQ核心技术-NDK开发语音消息变声功能
遍历枚举接口的元素
多线程-ThreadLocal
翻译 Spring Boot How To
上一篇文章      下一篇文章      查看所有文章
加:2017-10-30 04:01:06  更:2017-10-30 04:02:53 
VC(MFC) Delphi VB C++(C语言) C++ Builder 其它开发语言 云计算 Java开发 .Net开发 IOS开发 Android开发 PHP语言 JavaScript
ASP语言 HTML(CSS) HTML5 Apache MSSQL数据库 Oracle数据库 PowerBuilder Informatica 其它数据库 硬件及嵌入式开发 Linux开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年6日历
2018-6-21 8:59:07
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  编程开发知识库