关于HashMap与LinkedHashMap.docx

关于HashMap与LinkedHashMap2011-01-21 15:11:49|分类： java |标签：hashmapkeyvalueentityutil |字号订阅 关于HashMap与LinkedHashMap2011-01-21HashMap是无序的，HashMap在put的时候是根据key的hashcode进行hash然后放入对应的地方。所以在按照一定顺序put进HashMap中，然后遍历出HashMap的顺序跟put的顺序不同（除非在put的时候key已经按照hashcode排序号了，这种几率非常小）单纯的HashMap是无法实现排序的，这的排序是指，我们将键值对按照一定的顺序put进HashMap里，然后在进行取键值对的操作的时候，是按照put进去的顺序把键值对取出来的。JAVA在JDK1.4以后提供了LinkedHashMap来帮助我们实现了有序的HashMap！LinkedHashMap取键值对时，是按照你放入的顺序来取的。EG：import java.util.HashMap;import java.util.Iterator;import java.util.LinkedHashMap;import java.util.Map;import java.util.Map.Entry;/* * author TEANA E-mail: * version 创建时间：2011-1-21 下午02:23:07 * DO LinkedHashMap与HashMap */public class LinkedMappublic static void main(String args)/LinkedHashMap 有序Map maps = new LinkedHashMap();maps.put(1, 张三);maps.put(2, 李四);maps.put(3, 王五);maps.put(4, 赵六);System.out.println(LinkedHashMap(有序):);Iterator it = maps.entrySet().iterator();while(it.hasNext()Map.Entry entity = (Entry) it.next();System.out.println( key = + entity.getKey() + , value = + entity.getValue() + );/HashMap 无序Map map = new HashMap();map.put(1, 张三);map.put(2, 李四);map.put(3, 王五);map.put(4, 赵六);it = null;System.out.println(HashMap(无序):);it = map.entrySet().iterator();while(it.hasNext()Map.Entry entity = (Entry) it.next();System.out.println( key = + entity.getKey() + , value = + entity.getValue() + );执行结果如下：LinkedHashMap(有序): key = 1, value = 张三 key = 2, value = 李四 key = 3, value = 王五 key = 4, value = 赵六 HashMap(无序): key = 3, value = 王五 key = 2, value = 李四 key = 1, value = 张三 key = 4, value = 赵六 HashMap,LinkedHashMap,TreeMap应用简介共同点： HashMap,LinkedHashMap,TreeMap都属于Map；Map 主要用于存储键(key)值(value)对，根据键得到值，因此键不允许键重复,但允许值重复。 不同点:1.HashMap里面存入的键值对在取出的时候是随机的,也是我们最常用的一个Map.它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。在Map 中插入、删除和定位元素，HashMap 是最好的选择。 2.TreeMap取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。 3. LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现. 代码实例： package com.lrm.study.testcase; import java.util.HashMap;import java.util.Iterator;import java.util.LinkedHashMap;import java.util.Map;import java.util.TreeMap; public class MapAppTest /* Create on Nov 9, 2009 by lrm*/public static void main(String args) / TODO Auto-generated method stub MapAppTest.noOrder(); MapAppTest.hasOrder(); MapAppTest.likedHashMap(); public static void noOrder() System.out.println(-无序（随机输出-); Map map = new HashMap(); map.put(1, Level 1); map.put(2, Level 2); map.put(3, Level 3); map.put(4, Level 4); map.put(F, Level F); map.put(Q, Level Q); Iterator it = map.entrySet().iterator(); while (it.hasNext() Map.Entry e = (Map.Entry) it.next(); System.out.println(Key: + e.getKey() + ; Value: + e.getValue(); / 有序(默认排序，不能指定)public static void hasOrder() System.out.println(-有序（但是按默认顺充，不能指定）-); Map map = new TreeMap(); map.put(F, Level F); map.put(7, Level 1); map.put(8, Level 2); map.put(4, Level 3); map.put(4, Level 4); map.put(Q, Level Q); map.put(E, Level E); Iterator it = map.entrySet().iterator(); while (it.hasNext() Map.Entry e = (Map.Entry) it.next(); System.out.println(Key: + e.getKey() + ; Value: + e.getValue(); public static void likedHashMap() System.out.println(-有序（根据输入的顺序输出）-); Map map = new LinkedHashMap(); map.put(F, Level F); map.put(7, Level 1); map.put(8, Level 2); map.put(4, Level 3); map.put(4, Level 4); map.put(Q, Level Q); map.put(E, Level E); Iterator it = map.entrySet().iterator(); while (it.hasNext() Map.Entry e = (Map.Entry) it.next(); System.out.println(Key: + e.getKey() + ; Value: + e.getValue(); 输出结果： -无序（随机输出-Key: 3; Value: Level 3Key: F; Value: Level FKey: 2; Value: Level 2Key: 4; Value: Level 4Key: Q; Value: Level QKey: 1; Value: Level 1-有序（但是按默认顺充，不能指定）-Key: 4; Value: Level 4Key: 7; Value: Level 1Key: 8; Value: Level 2Key: E; Value: Level EKey: F; Value: Level FKey: Q; Value: Level Q-有序（根据输入的顺序输出）-Key: F; Value: Level FKey: 7; Value: Level 1Key: 8; Value: Level 2Key: 4; Value: Level 4Key: Q; Value: Level QKey: E; Value: Level E HashMap原理 分类： j2se 2009-12-14 20:39 592人阅读 评论(3) 收藏 举报 原文地址：/blog/544497版权声明：所有版权皆归原作者所有HashMap是一种十分常用的数据结构，作为一个应用开发人员，对其原理、实现的加深理解有助于更高效地进行数据存取。本文所用的jdk版本为1.5。 使用HashMap Effective JAVA中认为，99%的情况下，当你覆盖了equals方法后，请务必覆盖hashCode方法。默认情况下，这两者会采用Object的“原生”实现方式，即： Java代码 1. protectednativeinthashCode(); 2. publicbooleanequals(Objectobj) 3. return(this=obj); 4. java view plaincopy1. protectednativeinthashCode();2. publicbooleanequals(Objectobj)3. return(this=obj);4. hashCode方法的定义用到了native关键字，表示它是由C或C+采用较为底层的方式来实现的，你可以认为它返回了该对 象的内存地址；而缺省equals则认为，只有当两者引用同一个对象时，才认为它们是相等的。如果你只是覆盖了equals()而没有重新定义 hashCode()，在读取HashMap的时候，除非你使用一个与你保存时引用完全相同的对象作为key值，否则你将得不到该key所对应的值。 另一方面，你应该尽量避免使用“可变”的类作为HashMap的键。如果你将一个对象作为键值并保存在HashMap中，之后又改变了其状态，那么HashMap就会产生混乱，你所保存的值可能丢失（尽管遍历集合可能可以找到）。可参考/developerworks/cn/java/j-jtp02183/ HashMap存取机制 Hashmap实际上是一个数组和链表的结合体，利用数组来模拟一个个桶（类似于Bucket Sort）以快速存取不同hashCode的key，对于相同hashCode的不同key，再调用其equals方法从List中提取出和key所相对应的value。 JAVA 中hashMap的初始化主要是为initialCapacity和loadFactor这两个属性赋值。前者表示hashMap中用来区分不同hash 值的key空间长度，后者是指定了当hashMap中的元素超过多少的时候，开始自动扩容，。默认情况下initialCapacity为 16，loadFactor为0.75，它表示一开始hashMap可以存放16个不同的hashCode，当填充到第12个的时候，hashMap会自 动将其key空间的长度扩容到32，以此类推；这点可以从源码中看出来： Java代码 1. voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex) 2. Entrye=tablebucketIndex; 3. tablebucketIndex=newEntry(hash,key,value,e); 4. if(size+=threshold) 5. resize(2*table.length); 6. java view plaincopy1. voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex)2. Entrye=tablebucketIndex;3. tablebucketIndex=newEntry(hash,key,value,e);4. if(size+=threshold)5. resize(2*table.length);6. 而每当hashMap扩容后，内部的每个元素存放的位置都会发生变化（因为元素的最终位置是其hashCode对key空间长度取 模而得），因此resize方法中又会调用transfer函数，用来重新分配内部的元素；这个过程成为rehash，是十分消耗性能的，因此在可预知元 素的个数的情况下，一般应该避免使用缺省的initialCapacity，而是通过构造函数为其指定一个值。例如我们可能会想要将数据库查询所得 1000条记录以某个特定字段（比如ID）为key缓存在hashMap中，为了提高效率、避免rehash，可以直接指定 initialCapacity为2048。 另一个值得注意的地方是，hashMap其key空间的长度一定为2的N次方，这一点可以从一下源码中看出来： Java代码 1. intcapacity=1; 2. while(capacityinitialCapacity) 3. capacity=1;java view plaincopy1. intcapacity=1;2. while(capacityinitialCapacity)3. capacity=1;即使我们在构造函数中指定的initialCapacity不是2的平方数，capacity还是会被赋值为2的N次方。 为什么Sun Microsystem的工程师要将hashMap key空间的长度设为2的N次方呢？这里参考R.W.Floyed给出的衡量散列思想的三个标准： 一个好的hash算法的计算应该是非常快的 一个好的hash算法应该是冲突极小化 如果存在冲突,应该是冲突均匀化 为了将各元素的hashCode保存至长度为Length的key数组中，一般采用取模的方式，即index = hashCode % Length。不可避免的，存在多个不同对象的hashCode被安排在同一位置，这就是我们平时所谓的“冲突”。如果仅仅是考虑元素均匀化与冲突极小 化，似乎应该将Length取为素数（尽管没有明显的理论来支持这一点，但数学家们通过大量的实践得出结论，对素数取模的产生结果的无关性要大于其它数 字）。为此，Craig Larman and Rhett GuthrieJava Performence中对此也大加抨击。为了弄清楚这个问题，Bruce Eckel（Thinking in JAVA的作者）专程采访了java.util.hashMap的作者Joshua Bloch，并将他采用这种设计的原因放到了网上（/javatutorials/javahashmap.shtml） 。 上述设计的原因在于，取模运算在包括JAVA在内的大多数语言中的效率都十分低下，而当除数为2的N次方时，取模运算将退化为最简单的位运算，其效率明显提升（按照Bruce Eckel给出的数据，大约可以提升58倍） 。看看JDK中是如何实现的： Java代码 1. staticintindexFor(inth,intlength) 2. returnh&(length-1); 3. java view plaincopy1. staticintindexFor(inth,intlength)2. returnh&(length-1);3. 当key空间长度为2的N次方时，计算hashCode为h的元素的索引可以用简单的与操作来代替笨拙的取模操作！假设某个对象的 hashCode为35（二进制为100011），而hashMap采用默认的initialCapacity（16），那么indexFor计算所得结 果将会是100011 & 1111 = 11，即十进制的3，是不是恰好是35 Mod 16。 上面的方法有一个问题，就是 它的计算结果仅有对象hashCode的低位决定，而高位被统统屏蔽了；以上面为例，19（10011）、35（100011）、67（1000011） 等就具有相同的结果。针对这个问题， Joshua Bloch采用了“防御性编程”的解决方法，在使用各对象的hashCode之前对其进行二次Hash，参看JDK中的源码： Java代码 1. staticinthash(Objectx) 2. inth=x.hashCode(); 3. h+=(h14); 5. h+=(h10); 7. returnh; 8. java view plaincopy1. staticinthash(Objectx)2. inth=x.hashCode();3. h+=(h14);5. h+=(h10);7. returnh;8. 采用这种旋转Hash函数的主要目的是让原有hashCode的高位信息也能被充分利用，且兼顾计算效率以及数据统计的特性，其具体的原理已超出了本文的领域。 加快Hash效率的另一个有效途径是编写良好的自定义对象的HashCode，String的实现采用了如下的计算方法： Java代码 1. for(inti=0;ilen;i+) 2. h=31*h+valoff+; 3. 4. hash=h;java view plaincopy1. for(inti=0;ilen;i+)2. h=31*h+valoff+;3. 4. hash=h;这种方法HashCode的计算方法可能最早出现在Brian W. Kernighan和Dennis M. Ritchie的The C Programming Language中，被认为是性价比最高的算法（又被称为times33算法，因为C中乘数常量为33，JAVA中改为31），实际上，包括List在 内的大多数的对象都是用这种方法计算Hash值。 另一种比较特殊的hash算法称为布隆过滤器，它以牺牲细微精度为代价，换来存储空间的大量节俭，常用于诸如判断用户名重复、是否在黑名单上等等，可以参考李开复的数学之美系列第13篇（/2006/08/blog-post.html） Fail-Fast机制 众所周知，HashMap不是线程安全的集合类。但在某些容错能力较好的应用中，如果你不想仅仅因为1%的可能性而去承受hashTable的同步开销，则可以考虑利用一下HashMap的Fail-Fast机制，其具体实现如下： Java代码 1. EntrynextEntry() 2. if(modCount!=expectedModCount) 3. thrownewConcurrentModificationException(); 4. 5. java view plaincopy1. EntrynextEntry()2. if(modCount!=expectedModCount)3. thrownewConcurrentModificationException();4. 5. 其中modCount为HashMap的一个实例变量，并且被声明为volatile，表示任何线程都可以看到该变量被其它线程修 改的结果（根据JVM内存模型的优化，每一个线程都会存一份自己的工作内存，此工作内存的内容与本地内存并非时时刻刻都同步，因此可能会出现线程间的修改 不可见的问题） 。使用Iterator开始迭代时，会将modCount的赋值给expectedModCount，在迭代过程中，通过每次比较两者是否相等来判断 HashMap是否在内部或被其它线程修改。HashMap的大多数修改方法都会改变ModCount，参考下面的源码：Java代码 1. publicVput(Kkey,Vvalue) 2. Kk=maskNull(key); 3. inthash=hash(k); 4. inti=indexFor(hash,table.length); 5. for(Entrye=tablei;e!=null;e=e.next) 6. if(e.hash=hash&eq(k,e.key) 7. VoldValue=e.value; 8. e.value=value; 9. e.recordAccess(this); 10. returnoldValue; 11. 12. 13. modCount+; 14. addEntry(hash,k,value,i); 15. returnnull; 16. java view plaincopy1. publicVput(Kkey,Vvalue)2. Kk=maskNull(key);3. inthash=hash(k);4. inti=indexFor(hash,table.length);5. for(Entrye=tablei;e!=null;e=e.next)6. if(e.hash=hash&eq(k,e.key)7. VoldValue=e.value;8. e.value=value;9. e.recordAccess(this);10. returnoldValue;11. 12. 13. modCount+;14. addEntry(hash,k,value,i);15. returnnull;16. 以put方法为例，每次往HashMap中添加元素都会导致modCount自增。其它诸如remove、clear方法也都包含类似的操作。 从上面可以看出，HashMap所采用的Fail-Fast机制本质上是一种乐观锁机制，通过检查状态没有问题则忽略有问题则抛出异常的方式，来避免线程同步的开销，下面给出一个在单线程环境下发生Fast-Fail的例子： Java代码 1. classTest 2. publicstaticvoidmain(Stringargs) 3. java.util.HashMapmap=newjava.util.HashMap(); 4. map.put(newObject(),a); 5. map.put(newObject(),b); 6. java.util.Iteratorit=map.keySet().iterator(); 7. while(it.hasNext() 8. it.next(); 9. map.put(,); 10. System.out.println(map.size(); 11. 12. java view plaincopy1. classTest2. publicstaticvoidmain(Stringargs)3. java.util.HashMapmap=newjava.util.HashMap();4. map.put(newObject(),a);5. map.put(newObject(),b);6. java.util.Iteratorit=map.keySet().iterator();7. while(it.hasNext()8. it.next();9. map.put(,);10. System.out.println(map.size();11. 12. 运行上面的代码会抛出java.util.ConcurrentModificationException，因为在迭代过程中修 改了HashMap内部的元素导致modCount自增。若将上面代码中 map.put(new Object(), b) 这句注释掉，程序会顺利通过，因为此时HashMap中只包含一个元素，经过一次迭代后已到了尾部，所以不会出现问题，也就没有抛出异常的必要了。 在通常并发环境下，还是建议采用同步机制。这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止意外的非同步访问。 LinkedHashMap 遍 历HashMap所得到的数据是杂乱无章的，这在某些情况下客户需要特定遍历顺序时是十分有用的。比如，这种数据结构很适合构建 LRU 缓存。调用 put 或 get 方法将会访问相应的条目（假定调用完成后它还存在）。putAll 方法以指定映射的条目集合迭代器提供的键-值映射关系的顺序，为指定映射的每个映射关系生成一个条目访问。Sun提供的J2SE说明文档特别规定任何其他 方法均不生成条目访问，尤其，collection 集合类的操作不会影响底层映射的迭代顺序。 LinkedHashMap的实现与 HashMap 的不同之处在于，前者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是集合中元素的插入顺序。该类定义了 header、before与after三个属性来表示该集合类的头与前后“指针”，其具体用法类似于数据结构中的双链表，以删除某个元素为例： Java代码 1. privatevoidremove() 2. before.after=after; 3. after.before=before; 4. java view plaincopy1. privatevoidremove()2. before.after=after;3. after.before=before;4. 实际上就是改变前后指针所指向的元素。 显然，由于增加了维护链接列表的开支，其性能要比 HashMap 稍逊一筹，不过有一点例外：LinkedHashMap的迭代所需时间与其的所包含的元素成比例；而HashMap 迭代时间很可能开支较大，因为它所需要的时间与其容量（分配给Key空间的长度）成比例。一言以蔽之，随机存取用HashMap，顺序存取或是遍历用 LinkedHashMap。 LinkedHashMap还重写了removeEldestEntry方法以实现自动清除过期数据的功 能，这在HashMap中是无法实现的，因为后者其内部的元素是无序的。默认情况下，LinkedHashMap中的removeEldestEntry 的作用被关闭，其具体实现如下： Java代码 1. protectedbooleanremoveEldestEntry(Map.Entryeldest) 2. returnfalse; 3. java view plaincopy1. protectedbooleanremoveEldestEntry(Map.Entryeldest)2. returnfalse;3. 可以使用如下的代码覆盖removeEldestEntry： Java代码 1. privatestaticfinalintMAX_ENTRIES=100; 2. 3. protectedbooleanremoveEldestEntry(Map.Entryeldest) 4. returnsize()MAX_ENTRIES; 5. java view plaincopy1. privatestaticfinalintMAX_ENTRIES=100;2. 3. protectedbooleanremoveEldestEntry(Map.Entryeldest)4. returnsize()MAX_ENTRIES;5. 它表示，刚开始，LinkedHashMap中的元素不断增长；当它内部的元素超过MAX_ENTRIES（100）后，每当有新的元素被插入时，都会自动删除双链表中最前端（最旧）的元素，从而保持LinkedHashMap的长度稳定。 缺 省情况下，LinkedHashMap采取的更新策略是类似于队列的FIFO，如果你想实现更复杂的更新逻辑比如LRU（最近最少使用） 等，可以在构造函数中指定其accessOrder为true，因为的访问元素的方法（get）内部会调用一个“钩子”，即recordAccess，其 具体实现如下： Java代码 1. voidrecordAccess(HashMapm) 2. LinkedHashMaplm=(LinkedHashMap)m; 3. if(lm.accessOrder) 4. lm.modCount+; 5. remove(); 6. addBefore(lm.header); 7. 8. java view plaincopy1. voidrecordAccess(HashMapm)2. LinkedHashMaplm=(LinkedHashMap)m;3. if(lm.accessOrder)4. lm.modCount+;5. remove();6. addBefore(lm.header);7. 8. 上述代码主要实现了这样的功能：如果accessOrder被设置为true，则每次访问元素时，都将该元素移至headr的前面，即链表的尾部。将removeEldestEntry与accessOrder一起使用，就可以实现最基本的内存缓存，具体代码可参考/blog/180236。 WeakHashMap 99%的JAVA教材教导我们不要去干预JVM的垃圾回收机制，但JAVA中确实存在着与其密切相关的四种引用：强引用、软引用、弱引用以及幻象引用。 JAVA中默认的HashMap采用的是采用类似于强引用的强键来管理的，这意味着即使作为key的对象已经不存在了（指没有任何一个引用指向它），也仍然会保留在HashMap中，在某些情况下（例如内存缓存）中，这些过期的条目可能会造成内存泄漏等问题。 WeakHashMap 采用的策略是，只要作为key的对象已经不存在了（超出生命周期），就不会阻止垃圾收集器清空此条目，即使当前机器的内存并不紧张。不过，由于GC是一个 优先级很低的线程，因此不一定会很快发现那些只具有弱引用的对象，除非你显示地调用它，可以参考下面的例子： Java代码 1. publicstaticvoidmain(Stringargs) 2. Mapmap=newWeakHashMap(); 3. map.put(newString(Alibaba),alibaba); 4. while(map.containsKey(Alibaba) 5. try 6. Thread.sleep(500); 7. catch(InterruptedExceptionignored) 8. 9. System.out.println(Checkingforempty); 10. System.gc(); 11. java view plaincopy1. publicstaticvoidmain(Stringargs)2. Mapmap=newWeakHashMap();3. map.put(newString(Alibaba),alibaba);4. while(map.containsKey(Alibaba)5. try6. Thread.sleep(500);7. catch(InterruptedExceptionignored)8. 9. System.out.println(Checkingforempty);10. System.gc();11. 上述代码输出一次Checking for empty就退出了主线程，意味着GC在最近的一次垃圾回收周期中清除了new String(“Alibaba”),同时WeakHashMap也做出了及时的反应，将该键对应的条目删除了。如果将map的类型改为HashMap的 话，由于其内部采用的是强引用机制，因此即使GC被显示调用，map中的条目依然存在，程序会不断地打出Checking for empty字样。另