- 浏览: 41036 次
- 性别:
- 来自: 北京
最新评论
顾名思义LinkedHashMap是比HashMap多了一个链表的结构。与HashMap相比LinkedHashMap维护的是一个具有双重链表的HashMap,LinkedHashMap支持2中排序一种是插入排序,一种是使用排序,最近使用的会移至尾部例如 M1 M2 M3 M4,使用M3后为 M1 M2 M4 M3了,LinkedHashMap输出时其元素是有顺序的,而HashMap输出时是随机的,如果Map映射比较复杂而又要求高效率的话,最好使用LinkedHashMap,但是多线程访问的话可能会造成不同步,所以要用Collections.synchronizedMap来包装一下,从而实现同步。其实现一般为:
Map<String String> map = Collections.synchronizedMap(new LinkedHashMap(<String String));
HashMap,LinkedHashMap,TreeMap都属于Map
Map 主要用于存储键(key)值(value)对,根据键得到值,因此键不允许键重复,但允许值重复。
HashMap 是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值,具有很快的访问速度。HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;HashMap不支持线程的同步,即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步,可以用 Collections的synchronizedMap方法使HashMap具有同步的能力。
LinkedHashMap LinkedHashMap也是一个HashMap,但是内部维持了一个双向链表,可以保持顺序
TreeMap 不仅可以保持顺序,而且可以用于排序
HashMap例子:
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
map.put("a3", "aa");
map.put("a2", "bb");
map.put("b1", "cc");
for (Iterator iterator = map.values().iterator(); iterator.hasNext();) {
String name = (String) iterator.next();
System.out.println(name);
}
}
LinkedHashMap例子:
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<String, String>();
map.put("a3", "aa");
map.put("a2", "bb");
map.put("b1", "cc");
for (Iterator iterator = map.values().iterator(); iterator.hasNext();) {
String name = (String) iterator.next();
System.out.println(name);
}
}
TreeMap例子:
public static void main(String[] args) {
Map<String, String> map = new TreeMap<String, String>(new Comparator<Object>(){
Collator collator = Collator.getInstance();
public int compare(Object o1, Object o2) {
CollationKey key1 = collator.getCollationKey(o1.toString());
CollationKey key2 = collator.getCollationKey(o2.toString());
return key1.compareTo(key2);
//return collator.compare(o1, o2);
}});
map.put("a3", "aa");
map.put("a2", "bb");
map.put("b1", "cc");
for (Iterator iterator = map.values().iterator(); iterator.hasNext();) {
String name = (String) iterator.next();
System.out.println(name);
}
}
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")); } }
发表评论
-
Android的onSaveInstanceState和onRestoreInstanceState用法
2012-03-17 16:40 1024很多不明白Activity类中包含的onSaveInstanc ... -
Android的PreferenceActivity
2012-03-16 15:40 721在开发应用程序的过程中我们有很大的机会需要用到参数设置功能,那 ... -
Android原理揭秘系列之VacantCell缓存
2012-03-15 11:01 757操作过Android手机的朋友应该对在待机界面拖动图标的交互效 ... -
android view的一些常用触发方法
2012-02-28 21:23 1122onFinishInflate() 当View中所有的子控件 ... -
在android模拟器中删除系统应用程序
2012-02-27 21:38 2245首先启动android模拟器。 打开cmd命令行窗口。 ... -
使用Android的 hidden API
2012-02-26 17:17 2213Hidden API之所以被隐藏,是想阻止开发者使用SDK中那 ... -
[转]详解Android中的Parcelable
2012-02-26 17:04 2681一: 转自: http://blog.sina.com. ... -
Android Thumbnail 技术介绍
2012-02-23 16:35 1310Android Thumbnail Images ... -
四大主流移动开发框架介绍
2011-04-08 09:27 666移动Web开发语言被称为 ... -
Android应用程序打包签名
2011-04-02 22:43 1319转自: http://www.cppblog.com/fwxj ... -
学习Android的几大主攻方向
2011-04-02 16:50 819“苹果(Apple)公司的应用程序商店(app store)和 ... -
Android开发环境搭建
2011-03-31 21:22 885一、软件、开发包清单 Android开发首先需要搭建完 ...
相关推荐
这个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 .