一. 概述:
LinkedHashMap是Map接口的哈希表和链接列表实现,具有可预知的迭代顺序。LinkedHashMap实现与HashMap的不同之处在于,LinkedHashMap维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序(insert-order)或者是访问顺序,其中默认的迭代访问顺序就是插入顺序,即可以按插入的顺序遍历元素,这点和HashMap有很大的不同。
二.LinkedHashMap的accessOrder
1.访问顺序
LinkedHashMap除了支持默认的插入顺序,还支持访问顺序。所谓访问顺序(access-order)是指在迭代遍历列表中的元素时最近访问的元素会排在LinkedHashMap的尾部 。从其构造函数中可以看出当accessOrder设为true时即为访问顺序。
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
2.访问顺序时程序举例
public class LinkedHashMapTest {
public static void main(String[] args) {
Map<String, Object> map = new LinkedHashMap<String, Object>(16, 0.75F, true);
for (int i = 1; i <= 5; i++) {
map.put(i + "", i);
}
Iterator<Entry<String, Object>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next().getValue());
}
map.get("2");
map.get("3");
System.out.println("===============split line==================");
Iterator<Entry<String, Object>> iterator2 = map.entrySet().iterator();
while (iterator2.hasNext()) {
System.out.println(iterator2.next().getValue());
}
}
}
输出如下:
1
2
3
4
5
===============separator bar ======================
1
4
5
2
3
通过例子可以看出,最近经常使用的元素就放在后面,最近最少使用的就排在了链表的前面。
三.LinkedHashMap的扩展应用
基于LinkedHashMap的访问顺序的特点,可构造一个LRU(Least Recently Used)最近最少使用简单缓存。也有一些开源的缓存产品如ehcache的淘汰策略(LRU)就是在LinkedHashMap上扩展的。
1.LruCache的简单代码
public class LruCache<K, V> extends LinkedHashMap<K, V> {
private static final long serialVersionUID = -9062508768983283300L;
/** 最大容量 */
private int maxCapacity;
public LruCache(int maxCapacity) {
super(16, 0.75f, true);
this.maxCapacity = maxCapacity;
}
public int getMaxCapacity() {
return this.maxCapacity;
}
public void setMaxCapacity(int maxCapacity) {
this.maxCapacity = maxCapacity;
}
/**
* 当列表中的元素个数大于指定的最大容量时,返回true,并将最老的元素删除。
*/
@Override
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
if (super.size() > maxCapacity) {
return true;
}
return false;
}
}
2.测试代码
public class LruCacheTest {
public static void main(String[] args) {
LruCache<String, Object> cache = new LruCache<String, Object>(10);
for (int i = 1; i <= 15; i++) {
cache.put(i + "", i);
}
// 此时访问指定KEY的元素
cache.get("10");
Iterator<Entry<String, Object>> iterator = cache.entrySet().iterator();
for (; iterator.hasNext();) {
Entry<String, Object> entry = iterator.next();
System.out.println("key=" + entry.getKey() + ",value=" + entry.getValue());
}
}
}
输出如下:
key=7,value=7
key=8,value=8
key=9,value=9
key=11,value=11
key=12,value=12
key=13,value=13
key=14,value=14
key=15,value=15
key=10,value=10
四.LinkedHashMap对上述特性支持的分析
1.添加时删除最老元素
LinkedHashMap如何在添加元素时把最早放入的元素删除的呢,LinkedHashMap没有提供put方法,而是使用基类HashMap的put方法,看下面的HashMap的put(K key, V value)方法的源代码:
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> 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;
//HashMap中这个方法没有实现。
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
LinkedHashMap覆盖了HashMap中的这个addEntry(hash, key, value, i)方法,在 LinkedHashMap类中,removeEldestEntry()永远返回false;
也就是这个方法,提供了子类更强大功能扩展的机会。
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<K,V> eldest = header.after;
//该方法返回false.
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}
2.访问时重组列表
在获取元素时,LinkedHashMap提供了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中这个recordAccess()方法没有实现,只有空的方法体,在LinkedHashMap中的实现如下 ,也就是这个方法,将最近访问的元素给予重组,达到了LRU的目的。
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//accessOrder要指定为true.
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
分享到:
相关推荐
LinkedHashMap源代码,Java中Map的一种实现子类。
这是关于Java学习的主要针对LinkedHashMap的实现原理
这个demo主要讲解了LinkedHashmap的使用,希望可以帮助需要的同学.
java中HashMap,LinkedHashMap,TreeMap,HashTable的区别
HashMap,HashTable,LinkedHashMap,TreeMap的区别
深入Java集合学习系列(四): LinkedHashMap的实现原理
LinkedHashMap是Java中的一种特殊类型的HashMap,它保留了插入顺序,即按照元素插入的先后顺序进行排序
今天说一下LinkedHashMap的主要点,因为有同学不太清楚它和HashMap的区别。今天大概总结一下,也是方便自己进行学习。 写在前面 LinkedHashMap的内部维护了一个双向链表。可以按照元素的插入顺序进行访问,也可以...
JavaLinkedHashMap源码解析Java开发Java经验技巧共7页.pdf.zip
在理解了#7 介绍的HashMap后,我们来学习LinkedHashMap的工作原理及实现。首先还是类似的,我们写一个简单的LinkedHashMap的程序: LinkedHashMap<String> lmap = new LinkedHashMap(); lmap.put(语文, 1)...
主要介绍了Java集合框架源码分析之LinkedHashMap详解,内容包括了linkedhashmap的简介和源码剖析以及关于LinkedHashMap的源码总结,内容丰富,需要的朋友可以参考下。
本教程特点: 1.更适合零基础学员: ·自Java语言起源始,循序渐进,知识点剖析细致且每章配备大量随堂练习,让你步步为营,学得透彻、练得明白 ·拒绝晦涩难懂的呆板教学,宋老师语言生动幽默,举例形象生动深入浅...
Java集合系列(LinkedHashMap+LinkedList+ArrayList)
主要介绍了 java HashMap,TreeMap与LinkedHashMap的详解的相关资料,这里提供实例代码,帮助大家学习理解 这部分的内容,需要的朋友可以参考下
将LinkedHashMap转换为json,反之亦然 如何使用 LinkedHashMap requestData = new LinkedHashMap(); LinkedHashMap auth =新的LinkedHashMap(); auth.put(“ ServiceName”,“ Login”); auth.put(“ ...
主要介绍了Java使用LinkedHashMap进行分数排序的相关代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
RiteLinked——类似HashMap的容器,以用户可控的顺序保存它们的键值对RiteLinked提供了LinkedHashMap和LinkedHashSet更多最新版本。您可以在std或no_std环境中轻松使用它。一些实用的功能组合,支持,帮助您更好地将...
主要为大家详细介绍了Java集合系列之LinkedHashMap源码分析,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
Set是使用LinkedHashMap在Go(Golang)中简单的Set数据结构实现。 该库允许您获取一组int64或string而没有重复的项目。 用法 package main import ( "fmt" "github.com/StudioSol/set" ) func main () { ...