这段时间好好整理了一下基础,发现很多对我来说新的东西,里面博大精深的东西真的很多,经常使用HashMap,对HashMap的结构和原理非常了解,但是忽略了还有LinkedHashMap这个好东西。
先转一篇blog:
LinkedHashMap的特性:
Linked内部含有一个private transient Entry
header;来记录元素插入的顺序或者是元素被访问的顺序。利用这个线性结构的对象,可以帮助记录entry加入的前后顺序或者记录entry被访问的
频率(最少被访问的entry靠前,最近访问的entry靠后)。大致的过程如下:
new LinkedHashMap(10, 0.75, true);
其中前面两个参数就是HashMap构造函数需要的参数,后面的true表明LinkedHashMap按照访问的次序来排序。
按照访问的次序来排序的含义:当调用LinkedHashMap的get(key)或者put(key, value)时,碰巧key在map中被包含,那么LinkedHashMap会将key对象的entry放在线性结构的最后。
按照插入顺序来排序的含义:调用get(key), 或者put(key, value)并不会对线性结构产生任何的影响。
正是因为LinkedHashMap提供按照访问的次序来排序的功能,所以它才需要改写HashMap的get(key)方法(HashMap不需要排序)和HashMap.Entry的recordAccess(HashMap)方法
public Object get(Object key) {
Entry e = (Entry)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
void recordAccess(HashMap m) {
LinkedHashMap lm = (LinkedHashMap)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
注
意addBefore(lm.header)是将该entry放在header线性表的最后。(参考LinkedHashMap.Entry
extends HashMap.Entry 比起HashMap.Entry多了before, after两个域,是双向的)
至于put(key, value)方法, LinkedHashMap不需要去改写,用HashMap的就可以了,因为HashMap在其put(key, value)方法里边已经预留了e.recordAccess(this);
还有一个方法值得关注:
protected boolean removeEldestEntry(Map.Entry eldest) {
return false;
}
当
调用put(key, value)的时候,HashMap判断是否要自动增加map的size的作法是判断是否超过threshold,
LinkedHashMap则进行了扩展,如果removeEldestEntry方法return
false;(默认的实现),那么LinkedHashMap跟HashMap处理扩容的方式一致;如果removeEldestEntry返回
true,那么LinkedHashMap会自动删掉最不常用的那个entry(也就是header线性表最前面的那个)。
这会造成严重的性能问题吗?答案当然是否定的。因为在这儿的链表操作是常量级的。这也是LinkedHashMap/Set在这儿比TreeMap/Set性能更高的原因。
同样,LinkedHashMap/Set也不是thread-safe的。如果在多线程下访问,是需要进行外部同步,或者使用Collections.synchronizedMap()的方法包装成一个thread-safe的Map/Set。
特别需要注意的是,在使用“访问顺序”时,读取节点操作也是“结构变化”的操作。因为,这会改变元素遍历的顺序。所以,在使用
LinkedHashMap的iterator()方法,遍历元素时,如果其它线程有读取操作,也要进行同步。否则,也会抛出同其它fail-fast一
样的由于删除或增加操作而引起的CurrentModificationException的例外。
最后,LinkedHashMap缺省是使用插入顺序的,如何构造一个访问顺序的LinkedHashMap呢?很简单:
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) accessOrder = true 即可。
回来补充一个利用LinkedHashMap来实现LRU的Cache类,看了上面的特性,实现起来实在太简单了!
package lru;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
/**
*
*<p>Test</p>
*<p>Description:</P>
*<p>Company:Cisco CAS</p>
*<p>Department:CAS</p>
*@Author: Tommy Zhou
*@Since: 1.0
*@Version:Date:2011-5-13
*
**/
public class LRUCache<K,V> extends LinkedHashMap<K, V>{
private LinkedHashMap<K,V> cache =null ;
private int cacheSize = 0;
public LRUCache(int cacheSize){
this.cacheSize = cacheSize;
int hashTableCapacity = (int) Math.ceil (cacheSize / 0.75f) + 1;
cache = new LinkedHashMap<K, V>(hashTableCapacity, 0.75f,true)
{
// (an anonymous inner class)
private static final long serialVersionUID = 1;
@Override
protected boolean removeEldestEntry (Map.Entry<K, V> eldest)
{
System.out.println("size="+size());
return size () > LRUCache.this.cacheSize;
}
};
}
public V put(K key,V value){
return cache.put(key, value);
}
public V get(Object key){
return cache.get(key);
}
public static void main(String[] args) {
LRUCache<String, String> lruCache = new LRUCache<String, String>(5);
lruCache.put("1", "1");
lruCache.put("2", "2");
lruCache.put("3", "3");
lruCache.put("4", "4");
System.out.println(lruCache.get("2"));
lruCache.get("2");
lruCache.put("6", "6");
lruCache.put("5", "5");
System.out.println(lruCache.get("1"));
}
}
分享到:
相关推荐
这个demo主要讲解了LinkedHashmap的使用,希望可以帮助需要的同学.
如何用LinkedHashMap实现LRU? 如何用TreeMap实现一致性hash? ConcurrentHashMap是如何在保证并发安全的同时提高性能? ConcurrentHashMap是如何让多线程同时参与扩容? LinkedBlockingQueue、DelayQueue是如何实现...
主要介绍了Java使用LinkedHashMap进行分数排序的相关代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
基于JavaLinkedHashMap实现的 LRU 算法 algorithm.consistentHashing ConsistentHash: 一致性Hash算法 algorithm.cap algorithm.subset 给一个set打印出所有子集 jdk jdk 知识 jdk.autoboxing 自动装箱拆箱 jdk....
LinkedHashMap源代码,Java中Map的一种实现子类。
分成三级对图片进行缓存,第一级采用LinkedHashMap(LRU算法),第二季采用ConcurrentHashMap线程安全控制
这是关于Java学习的主要针对LinkedHashMap的实现原理
Set是使用LinkedHashMap在Go(Golang)中简单的Set数据结构实现。 该库允许您获取一组int64或string而没有重复的项目。 用法 package main import ( "fmt" "github.com/StudioSol/set" ) func main () { ...
ava基础 基础知识 ...Java集合详解5:深入理解LinkedHashMap和LRU缓存 Java集合详解6:TreeMap和红黑树 Java集合详解7:HashSet,TreeSet与LinkedHashSet Java集合详解8:Java集合类细节精讲 JavaWeb
(当然也可以用hashbrown )用法将ritelinked添加到Cargo.toml :ritelinked =" x.y.z"写一些这样的代码:letmut lru_cache= LinkedHashMap::new ();let key="key" .to_owned ();let _cached_val= lru_cache .raw_...
LinkedHashMap是Java中的一种特殊类型的HashMap,它保留了插入顺序,即按照元素插入的先后顺序进行排序
java中HashMap,LinkedHashMap,TreeMap,HashTable的区别
Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存。Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Java的LRULinkedHashMap是直接继承了LinkedHashMap,进行了极少的改动后可以实现LRU...
HashMap,HashTable,LinkedHashMap,TreeMap的区别
深入Java集合学习系列(四): LinkedHashMap的实现原理
要注意一点的是LinkedHashMap是可以实现LRU缓存策略的,前提是你需要将LinkedHashMap中的accessorder属性设置为true。 因此你基本可以认为LinkedHashMap是LinkedList和HashMap的一个组合。 LinkedHashMap简介 ...
Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存。Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Java的LRULinkedHashMap就是直接继承了LinkedHashMap,进行了极少的改动后就可以实现LRU...
java12-fundamentals-cache-implementations-workshop 参考 前言 本次研讨会的目标 理解 LRU 缓存的概念 理解 LFU 缓存的概念 实现 LRU 和 LFU 缓存 看看守卫在列表实现中是如何有用的 工作坊: lfu.workshop , lru....
RiteLinked-类似HashMap的容器,以用户可控制的顺序保存其键值对 提供了LinkedHashMap和... let mut lru_cache = LinkedHashMap :: new (); let key = "key" . to_owned (); let _cached_val = lru_cache .