博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[Java] LinkedHashMap 源码简要分析
阅读量:6787 次
发布时间:2019-06-26

本文共 3359 字,大约阅读时间需要 11 分钟。

 

 特点

* 各个元素不仅仅按照HashMap的结构存储,而且每个元素包含了before/after指针,通过一个头元素header,形成一个双向循环链表。使用循环链表,保存了元素插入的顺序。
* 可设置参数,让每次get()后的元素排在双向链表的最后。
 
Entry类
private static class Entry
extends HashMap.Entry
// 继承自HashMap的Entry(已有key/value/hash/next字段){ // 双向链表 Entry
before; Entry
after; // 构造函数 Entry(int hash, K key, V value, HashMap.Entry
next) { super(hash, key, value, next); } // 删除当前结点 private void remove(){ before.after = after; after.before = before; } // 在当前结点的前面添加结点 private void addBefore(Entry
existingEntry){ after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; } // 如果设定某个参数,get()命中后,把当前元素放到链表最后 void recoreAccess(HashMap
m) { LinkedHashMap
lm = (LinkedHashMap
)m; // 把调用者的this转化成LinkedHashMap if(lm.accessOrder){ remove(); // 删除当前结点 addBefore(lm.header); // 插入到header前面 } }}

  

源码简要分析

public class LinkedHashMap
extends HashMap
{ private Entry
header; // 双向链表的头部。 private final boolean accessOrder; // 默认false。如果true表示get()命中后,把当前元素放到链表最后。 // init() void init() { header = new Entry<>(-1, null, null, null); header.before = header.after = header; // 双向链表首尾相连 } // put() 继承自 HashMap // 添加元素时,不仅按照HashMap的方式散列存储,而且还通过双向链表记录先后顺序 public V put(K key, V value) { int hash = hash(key.hashCode()); // key的特殊hash值 int i = indexFor(hash,table.length); // 槽位 index // key是否已经存在,存在则返回value。 for (Entry
e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); //LinkedHashMap特有 return oldValue; } } // key不存在就添加Entry addEntry(hash,key,value,i); return null; } void addEntry(int hash, K key, V value, int bucketIndex) { createEntry(hash, key, value, bucketIndex); // Remove eldest entry if instructed, else grow capacity if appropriate Entry
eldest = header.after; if (removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); } else { if (size >= threshold) resize(2 * table.length); } } void createEntry(int hash, K key, V value, int bucketIndex/*槽位index*/) { HashMap.Entry
old = table[bucketIndex]; Entry
e = new Entry<>(hash, key, value, old); table[bucketIndex] = e; e.addBefore(header); size++; } // get() // 取元素是按照散列而不是双向链表进行查找,速度快 public V get(Object key) { Entry
e = (Entry
)getEntry(key); // getEntry()使用了HashMap的getEntry,即按照HashMap的方式寻找元素。 if (e == null) return null; e.recordAccess(this); return e.value; }}

  

添加元素的过程示意图

初始化时,头元素header的before/after均指向自身。

 

插入元素e1后,header的before/after均指向e1;e1的before/after均指向header。

 

插入元素e2后,header的after继续指向e1,e1的after指向e2,e1的before指向header。header的before指向e2。e2的before指向e1,e2的after指向header。

转载于:https://www.cnblogs.com/caca/p/java_LinkedHashMap.html

你可能感兴趣的文章
HTTP协议中POST、GET、HEAD、PUT等请求方法 (自己学习)
查看>>
c++11: bind用法
查看>>
讨论:C#Gridview增加超链接列
查看>>
python---内置函数,匿名函数,嵌套函数,高阶函数,序列化
查看>>
Service
查看>>
canvas 画板
查看>>
TYVJ P1045 &&洛谷 1388 最大的算式 Label:dp
查看>>
10+31=100小组项目第五周总结报告
查看>>
Python 爬取高清桌面壁纸
查看>>
测试-html格式
查看>>
选择排序
查看>>
安装nginx&&node环境nginx转发端口
查看>>
Java知多少(7)类与对象
查看>>
评论递归无极显示
查看>>
用学习逃避成长,听新知缓解焦虑
查看>>
selenium 如何处理table
查看>>
从流程浅析网站性能优化点
查看>>
Java笔试题库之选题题篇【71-140题】
查看>>
spring的依赖注入(DI)、控制反转(IOC)和面向切面(AOP)
查看>>
Web前端面试宝典(最新)
查看>>