It so life

love as life

深入理解HashMap

Posted on

深入理解HashMap

您还未登录 ! 我的应用 登录 注册

JavaEye-最棒的软件开发交流社区

论坛首页 → Java编程和Java企业应用版 → Java综合 →

深入理解HashMap

全部 Hibernate Spring Struts iBATIS 企业应用 设计模式 DAO 领域模型 OO Tomcat SOA JBoss Swing Java综合

myApps快速开发平台，配置即开发、所见即所得，节约85%工作量

« 上一页 1 2 3 … 8 9 下一页 » 浏览 17789 次 主题：深入理解HashMap

该帖已经被评为精华帖 作者 正文 * annegu

  • 等级: 三星会员
  • annegu的博客
  • 文章: 38
  • 积分: 360
  • 来自: 杭州
  • 发表时间：2009-12-02 最后修改：2010-05-16

< > 猎头职位: 安徽: 合肥,杭州,苏州：诚聘java架构师

相关文章:

  • 一道面试题所牵涉到的JAVA知识(一)
  • 《算法导论》读书笔记7 (散列表)
  • ConcurrentHashMap之实现细节 推荐圈子: JAVA 3T 更多相关推荐 /// /@author annegu /@date 2009-12-02 // Hashmap是一种非常常用的、应用广泛的数据类型，最近研究到相关的内容，就正好复习一下。网上关于hashmap的文章很多，但到底是自己学习的总结，就发出来跟大家一起分享，一起讨论。 1、hashmap的数据结构 要知道hashmap是什么，首先要搞清楚它的数据结构，在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，hashmap也不例外。Hashmap实际上是一个数组和链表的结合体（在数据结构中，一般称之为“链表散列“），请看下图（横排表示数组，纵排表示数组元素【实际上是一个链表】）。 从图中我们可以看到一个hashmap就是一个数组结构，当新建一个hashmap的时候，就会初始化一个数组。我们来看看java代码： /// / The table, resized as necessary. Length MUST Always be a power of two. / FIXME 这里需要注意这句话，至于原因后面会讲到 // transient Entry[] table; static class Entry implements Map.Entry { final K key; V value; final int hash; Entry next; .......... }
      上面的Entry就是数组中的元素，它持有一个指向下一个元素的引用，这就构成了链表。
   当我们往hashmap中put元素的时候，先根据key的hash值得到这个元素在数组中的位置（即下标），然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了，那么在同一个位子上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。从hashmap中get元素时，首先计算key的hashcode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。从这里我们可以想象得到，如果每个位置上的链表只有一个元素，那么hashmap的get效率将是最高的，但是理想总是美好的，现实总是有困难需要我们去克服，哈哈~
    2、hash算法 我们可以看到在hashmap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合，所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。 所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，能不能找一种更快速，消耗更小的方式那？java中时这样做的， static int indexFor(int h, int length) { return h & (length-1); } 首先算得key得hashcode值，然后跟数组的长度-1做一次“与”运算（&）。看上去很简单，其实比较有玄机。比如数组的长度是2的4次方，那么hashcode就会和2的4次方-1做“与”运算。很多人都有这个疑问，为什么hashmap的数组初始化大小都是2的次方大小时，hashmap的效率最高，我以2的4次方举例，来解释一下为什么数组大小为2的幂时hashmap访问的性能最高。
       看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！

        所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
    说到这里，我们再回头看一下hashmap中默认的数组大小是多少，查看源代码可以得知是16，为什么是16，而不是15，也不是20呢，看到上面annegu的解释之后我们就清楚了吧，显然是因为16是2的整数次幂的原因，在小数据量的情况下16比15和20更能减少key之间的碰撞，而加快查询的效率。
    所以，在存储大容量数据的时候，最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话，也会以大于且最接近指定值大小的2次幂来初始化的，代码如下(HashMap的构造方法中)： // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; 3、hashmap的resize
     当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
   那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小/*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16/*0.75=12的时候，就把数组的大小扩展为2/*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过上面annegu已经说过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75/*1000 < 1000, 也就是说为了让0.75 /* size > 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题。
    4、key的hashcode与equals方法改写 在第一部分hashmap的数据结构中，annegu就写了get方法的过程：首先计算key的hashcode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。所以，hashcode与equals方法对于找到对应元素是两个关键方法。 Hashmap的key可以是任何类型的对象，例如User这种对象，为了保证两个具有相同属性的user的hashcode相同，我们就需要改写hashcode方法，比方把hashcode值的计算与User对象的id关联起来，那么只要user对象拥有相同id，那么他们的hashcode也能保持一致了，这样就可以找到在hashmap数组中的位置了。如果这个位置上有多个元素，还需要用key的equals方法在对应位置的链表中找到需要的元素，所以只改写了hashcode方法是不够的，equals方法也是需要改写滴~当然啦，按正常思维逻辑，equals方法一般都会根据实际的业务内容来定义，例如根据user对象的id来判断两个user是否相等。 在改写equals方法的时候，需要满足以下三点： (1) 自反性：就是说a.equals(a)必须为true。 (2) 对称性：就是说a.equals(b)=true的话，b.equals(a)也必须为true。 (3) 传递性：就是说a.equals(b)=true，并且b.equals(c)=true的话，a.equals(c)也必须为true。 通过改写key对象的equals和hashcode方法，我们可以将任意的业务对象作为map的key(前提是你确实有这样的需要)。 总结：
      本文主要描述了HashMap的结构，和hashmap中hash函数的实现，以及该实现的特性，同时描述了hashmap中resize带来性能消耗的根本原因，以及将普通的域模型对象作为key的基本要求。尤其是hash函数的实现，可以说是整个HashMap的精髓所在，只有真正理解了这个hash函数，才可以说对HashMap有了一定的理解。
    这是hashmap第一篇，主要讲了一下hashmap的数据结构和计算hash的算法。接下去annegu还会写第二篇，主要讲讲LinkedHashMap和LRUHashMap。先做个预告，呵呵~

  • 大小: 78.6 KB

  • 大小: 62.9 KB

  • 查看图片附件

声明：JavaEye文章版权属于作者，受法律保护。没有作者书面许可不得转载。 推荐链接

  • adobe 返回顶楼 * luobo25
  • 等级: 初级会员
  • luobo25的博客
  • 文章: 2
  • 积分: 0
  • 来自: 北京
  • 发表时间：2009-12-03

当length=2^n时，hashcode & (length-1) == hashcode % length，难怪这么巧 ，楼主的研究有价值 返回顶楼 回帖地址

0 0 请登录后投票 * mycybyb

  • 等级: 初级会员
  • mycybyb的博客
  • 文章: 126
  • 积分: 30
  • 来自: 沈阳
  • 发表时间：2009-12-03

写的很好。 不过，以前学数据结构的时候都学过。 返回顶楼 回帖地址

0 0 请登录后投票 * 火星来客

  • 等级: 初级会员
  • 火星来客的博客
  • 文章: 26
  • 积分: 30
  • 来自: 火星
  • 发表时间：2009-12-03

mycybyb 写道

写的很好。 不过，以前学数据结构的时候都学过。 楼上应该没有看楼主的这篇文章，数据结构中应该不会有JDK中map的hash函数的实现说明，而楼主详细的分析了jdk中的hashmap中hash函数真正的原理和价值所在，网上HashMap的文章一堆一堆的，但是没有人能说清楚h&length-1的奥妙所在 返回顶楼 回帖地址

0 0 请登录后投票 * mycybyb

  • 等级: 初级会员
  • mycybyb的博客
  • 文章: 126
  • 积分: 30
  • 来自: 沈阳
  • 发表时间：2009-12-03 最后修改：2009-12-03

火星来客 写道

mycybyb 写道

写的很好。 不过，以前学数据结构的时候都学过。 楼上应该没有看楼主的这篇文章，数据结构中应该不会有JDK中map的hash函数的实现说明，而楼主详细的分析了jdk中的hashmap中hash函数真正的原理和价值所在，网上HashMap的文章一堆一堆的，但是没有人能说清楚h&length-1的奥妙所在 没看能说好吗？ 我说写的很好，说的就是h & length -1这个。 其他的，都是常识了。 返回顶楼 回帖地址

0 0 请登录后投票 * 火星来客

  • 等级: 初级会员
  • 火星来客的博客
  • 文章: 26
  • 积分: 30
  • 来自: 火星
  • 发表时间：2009-12-03 最后修改：2009-12-03

mycybyb 写道

火星来客 写道

mycybyb 写道

写的很好。 不过，以前学数据结构的时候都学过。 楼上应该没有看楼主的这篇文章，数据结构中应该不会有JDK中map的hash函数的实现说明，而楼主详细的分析了jdk中的hashmap中hash函数真正的原理和价值所在，网上HashMap的文章一堆一堆的，但是没有人能说清楚h&length-1的奥妙所在 没看能说好吗？ 我说写的很好，说的就是h & length -1这个。 其他的，都是常识了。 恩，同意，其他确实是常识，只是从我的面试结果来看，没有常识的程序员比较多。 返回顶楼 回帖地址

0 0 请登录后投票 * dennis_zane

  • 等级: 四钻会员
  • dennis_zane的博客
  • 文章: 1350
  • 积分: 1968
  • 来自: 杭州
  • 发表时间：2009-12-03

火星来客 写道

mycybyb 写道

写的很好。 不过，以前学数据结构的时候都学过。 楼上应该没有看楼主的这篇文章，数据结构中应该不会有JDK中map的hash函数的实现说明，而楼主详细的分析了jdk中的hashmap中hash函数真正的原理和价值所在，网上HashMap的文章一堆一堆的，但是没有人能说清楚h&length-1的奥妙所在 h&length-1，这个也算是常识吧，对数学或者位运算了解点就知道了。 返回顶楼 回帖地址

0 2 请登录后投票 * 火星来客

  • 等级: 初级会员
  • 火星来客的博客
  • 文章: 26
  • 积分: 30
  • 来自: 火星
  • 发表时间：2009-12-03 最后修改：2009-12-03

dennis_zane 写道

h&length-1，这个也算是常识吧，对数学或者位运算了解点就知道了。 &运算本身当然是常识，任何一本计算机图书中几乎都会提到，但是将其和： int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; 组合起来使用，得到%的效果，但是性能比%高，这一点我没有想到，所以这一点上对我个人来说没有将其视为常识。 返回顶楼 回帖地址

0 0 请登录后投票 * yuyee

  • 等级: 初级会员
  • yuyee的博客
  • 文章: 618
  • 积分: 0
  • 来自: 杭州
  • 发表时间：2009-12-03

的确蛮仔细的 返回顶楼 回帖地址

0 0 请登录后投票 * lwyx2000

  • 等级: 初级会员
  • lwyx2000的博客
  • 文章: 5
  • 积分: 30
  • 来自: 福建省
  • 发表时间：2009-12-03

很不错！！ 返回顶楼 回帖地址

0 0 请登录后投票

« 上一页 1 2 3 … 8 9 下一页 » 论坛首页 → Java编程和Java企业应用版 → Java综合 跳转论坛:Java编程和Java企业应用 Web前端技术 移动编程和手机应用开发 C/C++编程 Ruby编程 Python编程 PHP编程 Flash编程和RIA Microsoft .Net 综合技术 软件开发和项目管理 行业应用 入门讨论 招聘求职 海阔天空

© 2003-2010 JavaEye.com. 上海炯耐计算机软件有限公司版权所有 [ 沪ICP备05023328号 ]

直接拿来用！超实用的Java数组技巧攻略

Posted on

直接拿来用！超实用的Java数组技巧攻略

直接拿来用！超实用的Java数组技巧攻略

本文分享了关于Java数组最顶级的11大方法，帮助你解决工作流程问题，无论是运用在团队环境或是在私人项目中，你都可以直接拿来用！

0. 声明一个数组（Declare an array）

[js] view plaincopy

  1. String[] aArray = new String[5];
  2. String[] bArray = {"a","b","c", "d", "e"};
  3. String[] cArray = new String[]{"a","b","c","d","e"};
    1. 在Java中输出一个数组（Print an array in Java）

[js] view plaincopy

  1. int[] intArray = { 1, 2, 3, 4, 5 };
  2. String intArrayString = Arrays.toString(intArray);
  4. // print directly will print reference value
  5. System.out.println(intArray);
  6. // [I@7150bd4d
  8. System.out.println(intArrayString);
  9. // [1, 2, 3, 4, 5]
    2. 从数组中创建数组列表（Create an ArrayList from an array）

[js] view plaincopy

  1. String[] stringArray = { "a", "b", "c", "d", "e" };
  2. ArrayList arrayList = new ArrayList(Arrays.asList(stringArray));
  3. System.out.println(arrayList);
  4. // [a, b, c, d, e]
    3. 检查数组中是否包含特定值（Check if an array contains a certain value）

[js] view plaincopy

  1. String[] stringArray = { "a", "b", "c", "d", "e" };
  2. boolean b = Arrays.asList(stringArray).contains("a");
  3. System.out.println(b);
  4. // true
    4. 连接两个数组（ Concatenate two arrays）

[js] view plaincopy

  1. int[] intArray = { 1, 2, 3, 4, 5 };
  2. int[] intArray2 = { 6, 7, 8, 9, 10 };
  3. // Apache Commons Lang library
  4. int[] combinedIntArray = ArrayUtils.addAll(intArray, intArray2);
    5. 声明一个数组内链（Declare an array inline ）

[js] view plaincopy

  1. method(new String[]{"a", "b", "c", "d", "e"});

6. 将数组元素加入到一个独立的字符串中（Joins the elements of the provided array into a single String）

[js] view plaincopy

  1. // containing the provided list of elements
  2. // Apache common lang
  3. String j = StringUtils.join(new String[] { "a", "b", "c" }, ", ");
  4. System.out.println(j);
  5. // a, b, c
    7. 将数组列表转换成一个数组 （Covnert an ArrayList to an array）

[js] view plaincopy

  1. String[] stringArray = { "a", "b", "c", "d", "e" };
  2. ArrayList arrayList = new ArrayList(Arrays.asList(stringArray));
  3. String[] stringArr = new String[arrayList.size()];
  4. arrayList.toArray(stringArr);
  5. for (String s : stringArr)
  6. System.out.println(s);
    8. 将数组转换成一个集合（Convert an array to a set）

[js] view plaincopy

  1. Set set = new HashSet(Arrays.asList(stringArray));
  2. System.out.println(set);
  3. //[d, e, b, c, a]
    9. 反向数组（Reverse an array）

[js] view plaincopy

  1. int[] intArray = { 1, 2, 3, 4, 5 };
  2. ArrayUtils.reverse(intArray);
  3. System.out.println(Arrays.toString(intArray));
  4. //[5, 4, 3, 2, 1]
    10. 删除数组元素（Remove element of an array）

[js] view plaincopy

  1. int[] intArray = { 1, 2, 3, 4, 5 };
  2. int[] removed = ArrayUtils.removeElement(intArray, 3);//create a new array
  3. System.out.println(Arrays.toString(removed));
    One more – convert int to byte array

[js] view plaincopy

  1. byte[] bytes = ByteBuffer.allocate(4).putInt(8).array();
  3. for (byte t : bytes) {
  4. System.out.format("0x%x ", t);
  5. }
    来源： [http://www.csdn.net/article/2013-09-16/2816947-methods-for-java-arrays](http://www.csdn.net/article/2013-09-16/2816947-methods-for-java-arrays)

Top 10 Methods for Java Arrays

The following are top 10 methods for Java Array. They are the most voted questions from stackoverflow.

0. Declare an array String[] aArray = new String[5];String[] bArray = {"a","b","c", "d", "e"};String[] cArray = new String[]{"a","b","c","d","e"};

1. Print an array in Java

int[] intArray = { 1, 2, 3, 4, 5 };String intArrayString = Arrays.toString(intArray); // print directly will print reference valueSystem.out.println(intArray);// [I@7150bd4d System.out.println(intArrayString);// [1, 2, 3, 4, 5]

2. Create an ArrayList from an array

String[] stringArray = { "a", "b", "c", "d", "e" };ArrayList arrayList = new ArrayList(Arrays.asList(stringArray));System.out.println(arrayList);// [a, b, c, d, e]

3. Check if an array contains a certain value

String[] stringArray = { "a", "b", "c", "d", "e" };boolean b = Arrays.asList(stringArray).contains("a");System.out.println(b);// true

4. Concatenate two arrays

int[] intArray = { 1, 2, 3, 4, 5 };int[] intArray2 = { 6, 7, 8, 9, 10 };// Apache Commons Lang libraryint[] combinedIntArray = ArrayUtils.addAll(intArray, intArray2);

5. Declare an array inline

method(new String[]{"a", "b", "c", "d", "e"});

6. Joins the elements of the provided array into a single String

// containing the provided list of elements// Apache common langString j = StringUtils.join(new String[] { "a", "b", "c" }, ", ");System.out.println(j);// a, b, c

7. Covnert an ArrayList to an array

String[] stringArray = { "a", "b", "c", "d", "e" };ArrayList arrayList = new ArrayList(Arrays.asList(stringArray));String[] stringArr = new String[arrayList.size()];arrayList.toArray(stringArr);for (String s : stringArr) System.out.println(s);

8. Convert an array to a set

Set set = new HashSet(Arrays.asList(stringArray));System.out.println(set);//[d, e, b, c, a]

9. Reverse an array

int[] intArray = { 1, 2, 3, 4, 5 };ArrayUtils.reverse(intArray);System.out.println(Arrays.toString(intArray));//[5, 4, 3, 2, 1]

10. Remove element of an array

int[] intArray = { 1, 2, 3, 4, 5 };int[] removed = ArrayUtils.removeElement(intArray, 3);//create a new arraySystem.out.println(Arrays.toString(removed));

One more – convert int to byte array

byte[] bytes = ByteBuffer.allocate(4).putInt(8).array(); for (byte t : bytes) { System.out.format("0x%x ", t);} 来源： [http://www.programcreek.com/2013/09/top-10-methods-for-java-arrays/](http://www.programcreek.com/2013/09/top-10-methods-for-java-arrays/)

淘宝面试题：如何充分利用多核CPU，计算很大的List中所有整数的和

Posted on

淘宝面试题：如何充分利用多核CPU，计算很大的List中所有整数的和

永久链接：http://flysnow.iteye.com/blog/711162 引用

前几天在网上看到一个淘宝的面试题：有一个很大的整数list，需要求这个list中所有整数的和，写一个可以充分利用多核CPU的代码，来计算结果。 一：分析题目 从题中可以看到“很大的List”以及“充分利用多核CPU”，这就已经充分告诉我们要采用多线程(任务)进行编写。具体怎么做呢？大概的思路就是分割List，每一小块的List采用一个线程(任务)进行计算其和，最后等待所有的线程(任务)都执行完后就可得到这个“很大的List”中所有整数的和。 二：具体分析和技术方案 既然我们已经决定采用多线程(任务)，并且还要分割List，每一小块的List采用一个线程(任务)进行计算其和，那么我们必须要等待所有的线程(任务)完成之后才能得到正确的结果，那么怎么才能保证“等待所有的线程(任务)完成之后输出结果呢”？这就要靠java.util.concurrent包中的CyclicBarrier类了。它是一个同步辅助类，它允许一组线程(任务)互相等待，直到到达某个公共屏障点 (common barrier point)。在涉及一组固定大小的线程(任务)的程序中，这些线程(任务)必须不时地互相等待，此时 CyclicBarrier 很有用。简单的概括其适应场景就是：当一组线程(任务)并发的执行一件工作的时候，必须等待所有的线程(任务)都完成时才能进行下一个步骤。具体技术方案步骤如下：

  • 分割List，根据采用的线程(任务)数平均分配，即list.size()/threadCounts。
  • 定义一个记录“很大List”中所有整数和的变量sum，采用一个线程(任务)处理一个分割后的子List，计算子List中所有整数和(subSum)，然后把和(subSum)累加到sum上。
  • 等待所有线程(任务)完成后输出总和(sum)的值。 示意图如下： 三：详细编码实现 代码中有很详细的注释，这里就不解释了。 Java代码 收藏代码
  1. ///
  2. /* 计算List中所有整数的和
  3. /* 采用多线程，分割List计算
  4. /* @author 飞雪无情
  5. /* @since 2010-7-12
  6. /*/
  7. public class CountListIntegerSum {
  8. private long sum;//存放整数的和
  9. private CyclicBarrier barrier;//障栅集合点(同步器)
  10. private List list;//整数集合List
  11. private int threadCounts;//使用的线程数
  12. public CountListIntegerSum(List list,int threadCounts) {
  13. this.list=list;
  14. this.threadCounts=threadCounts;
  15. }
  16. ///
  17. /* 获取List中所有整数的和
  18. /* @return
  19. /*/
  20. public long getIntegerSum(){
  21. ExecutorService exec=Executors.newFixedThreadPool(threadCounts);
  22. int len=list.size()/threadCounts;//平均分割List
  23. //List中的数量没有线程数多（很少存在）
  24. if(len==0){
  25. threadCounts=list.size();//采用一个线程处理List中的一个元素
  26. len=list.size()/threadCounts;//重新平均分割List
  27. }
  28. barrier=new CyclicBarrier(threadCounts+1);
  29. for(int i=0;i<threadCounts;i++){
  30. //创建线程任务
  31. if(i==threadCounts-1){//最后一个线程承担剩下的所有元素的计算
  32. exec.execute(new SubIntegerSumTask(list.subList(i/*len,list.size())));
  33. }else{
  34. exec.execute(new SubIntegerSumTask(list.subList(i/len, len/(i+1)>list.size()?list.size():len/*(i+1))));
  35. }
  36. }
  37. try {
  38. barrier.await();//关键，使该线程在障栅处等待，直到所有的线程都到达障栅处
  39. } catch (InterruptedException e) {
  40. System.out.println(Thread.currentThread().getName()+":Interrupted");
  41. } catch (BrokenBarrierException e) {
  42. System.out.println(Thread.currentThread().getName()+":BrokenBarrier");
  43. }
  44. exec.shutdown();
  45. return sum;
  46. }
  47. ///
  48. /* 分割计算List整数和的线程任务
  49. /* @author lishuai
  50. /*
  51. /*/
  52. public class SubIntegerSumTask implements Runnable{
  53. private List subList;
  54. public SubIntegerSumTask(List subList) {
  55. this.subList=subList;
  56. }
  57. public void run() {
  58. long subSum=0L;
  59. for (Integer i : subList) {
  60. subSum += i;
  61. }
  62. synchronized(CountListIntegerSum.this){//在CountListIntegerSum对象上同步
  63. sum+=subSum;
  64. }
  65. try {
  66. barrier.await();//关键，使该线程在障栅处等待，直到所有的线程都到达障栅处
  67. } catch (InterruptedException e) {
  68. System.out.println(Thread.currentThread().getName()+":Interrupted");
  69. } catch (BrokenBarrierException e) {
  70. System.out.println(Thread.currentThread().getName()+":BrokenBarrier");
  71. }
  72. System.out.println("分配给线程："+Thread.currentThread().getName()+"那一部分List的整数和为：\tSubSum:"+subSum);
  73. }
  75. }
  77. }

///

/ 计算List中所有整数的和
/ 采用多线程，分割List计算

/ @author 飞雪无情 / @since 2010-7-12

/*/ public class CountListIntegerSum {

private long sum;//存放整数的和
private CyclicBarrier barrier;//障栅集合点(同步器)

private List<Integer> list;//整数集合List
private int threadCounts;//使用的线程数

public CountListIntegerSum(List<Integer> list,int threadCounts) {
    this.list=list;

    this.threadCounts=threadCounts;
}

//*/*
 /* 获取List中所有整数的和

 /* @return
 /*/

public long getIntegerSum(){
    ExecutorService exec=Executors.newFixedThreadPool(threadCounts);

    int len=list.size()/threadCounts;//平均分割List
    //List中的数量没有线程数多（很少存在）

    if(len==0){
        threadCounts=list.size();//采用一个线程处理List中的一个元素

        len=list.size()/threadCounts;//重新平均分割List
    }

    barrier=new CyclicBarrier(threadCounts+1);
    for(int i=0;i<threadCounts;i++){

        //创建线程任务
        if(i==threadCounts-1){//最后一个线程承担剩下的所有元素的计算

            exec.execute(new SubIntegerSumTask(list.subList(i/*len,list.size())));
        }else{

            exec.execute(new SubIntegerSumTask(list.subList(i/*len, len/*(i+1)>list.size()?list.size():len/*(i+1))));
        }

    }
    try {

        barrier.await();//关键，使该线程在障栅处等待，直到所有的线程都到达障栅处
    } catch (InterruptedException e) {

        System.out.println(Thread.currentThread().getName()+":Interrupted");
    } catch (BrokenBarrierException e) {

        System.out.println(Thread.currentThread().getName()+":BrokenBarrier");
    }

    exec.shutdown();
    return sum;

}
//*/*

 /* 分割计算List整数和的线程任务
 /* @author lishuai

 /*
 /*/

public class SubIntegerSumTask implements Runnable{
    private List<Integer> subList;

    public SubIntegerSumTask(List<Integer> subList) {
        this.subList=subList;

    }
    public void run() {

        long subSum=0L;
        for (Integer i : subList) {

            subSum += i;
        } 

        synchronized(CountListIntegerSum.this){//在CountListIntegerSum对象上同步
            sum+=subSum;

        }
        try {

            barrier.await();//关键，使该线程在障栅处等待，直到所有的线程都到达障栅处
        } catch (InterruptedException e) {

            System.out.println(Thread.currentThread().getName()+":Interrupted");
        } catch (BrokenBarrierException e) {

            System.out.println(Thread.currentThread().getName()+":BrokenBarrier");
        }

        System.out.println("分配给线程："+Thread.currentThread().getName()+"那一部分List的整数和为：\tSubSum:"+subSum);
    }


}

} 有人可能对barrier=new CyclicBarrier(threadCounts+1);//创建的线程数和主线程main有点不解，不是采用的线程(任务)数是threadCounts个吗？怎么为CyclicBarrier设置的给定数量的线程参与者比我们要采用的线程数多一个呢？答案就是这个多出来的一个用于控制main主线程的，主线程也要等待，它要等待其他所有的线程完成才能输出sum值，这样才能保证sum值的正确性，如果main不等待的话，那么结果将是不可预料的。 Java代码 收藏代码

  1. ///
  2. /* 计算List中所有整数的和测试类
  3. /* @author 飞雪无情
  4. /* @since 2010-7-12
  5. /*/
  6. public class CountListIntegerSumMain {
  8. ///
  9. /* @param args
  10. /*/
  11. public static void main(String[] args) {
  12. List list = new ArrayList();
  13. int threadCounts = 10;//采用的线程数
  14. //生成的List数据
  15. for (int i = 1; i <= 1000000; i++) {
  16. list.add(i);
  17. }
  18. CountListIntegerSum countListIntegerSum=new CountListIntegerSum(list,threadCounts);
  19. long sum=countListIntegerSum.getIntegerSum();
  20. System.out.println("List中所有整数的和为:"+sum);
  21. }
  23. }

///

/ 计算List中所有整数的和测试类 / @author 飞雪无情

/ @since 2010-7-12 //

public class CountListIntegerSumMain {

//*/*
 /* @param args

 /*/
public static void main(String[] args) {

    List<Integer> list = new ArrayList<Integer>();
    int threadCounts = 10;//采用的线程数

    //生成的List数据
    for (int i = 1; i <= 1000000; i++) {

        list.add(i);
    }

    CountListIntegerSum countListIntegerSum=new CountListIntegerSum(list,threadCounts);
    long sum=countListIntegerSum.getIntegerSum();

    System.out.println("List中所有整数的和为:"+sum);
}

} 四：总结 本文主要通过一个淘宝的面试题为引子，介绍了并发的一点小知识，主要是介绍通过CyclicBarrier同步辅助器辅助多个并发任务共同完成一件工作。Java SE5的java.util.concurrent引入了大量的设计来解决并发问题，使用它们有助于我们编写更加简单而健壮的并发程序。 附mathfox提到的ExecutorService.invokeAll()方法的实现 这个不用自己控制等待，invokeAll执行给定的任务，当所有任务完成时，返回保持任务状态和结果的 Future 列表。sdh5724也说用了同步，性能不好。这个去掉了同步，根据返回结果的 Future 列表相加就得到总和了。

Java代码 收藏代码

  1. ///
  2. /* 使用ExecutorService的invokeAll方法计算
  3. /* @author 飞雪无情
  4. /*
  5. /*/
  6. public class CountSumWithCallable {
  8. ///
  9. /* @param args
  10. /* @throws InterruptedException
  11. /* @throws ExecutionException
  12. /*/
  13. public static void main(String[] args) throws InterruptedException, ExecutionException {
  14. int threadCounts =19;//使用的线程数
  15. long sum=0;
  16. ExecutorService exec=Executors.newFixedThreadPool(threadCounts);
  17. List> callList=new ArrayList>();
  18. //生成很大的List
  19. List list = new ArrayList();
  20. for (int i = 0; i <= 1000000; i++) {
  21. list.add(i);
  22. }
  23. int len=list.size()/threadCounts;//平均分割List
  24. //List中的数量没有线程数多（很少存在）
  25. if(len==0){
  26. threadCounts=list.size();//采用一个线程处理List中的一个元素
  27. len=list.size()/threadCounts;//重新平均分割List
  28. }
  29. for(int i=0;i<threadCounts;i++){
  30. final List subList;
  31. if(i==threadCounts-1){
  32. subList=list.subList(i/*len,list.size());
  33. }else{
  34. subList=list.subList(i/len, len/(i+1)>list.size()?list.size():len/*(i+1));
  35. }
  36. //采用匿名内部类实现
  37. callList.add(new Callable(){
  38. public Long call() throws Exception {
  39. long subSum=0L;
  40. for(Integer i:subList){
  41. subSum+=i;
  42. }
  43. System.out.println("分配给线程："+Thread.currentThread().getName()+"那一部分List的整数和为：\tSubSum:"+subSum);
  44. return subSum;
  45. }
  46. });
  47. }
  48. List> futureList=exec.invokeAll(callList);
  49. for(Future future:futureList){
  50. sum+=future.get();
  51. }
  52. exec.shutdown();
  53. System.out.println(sum);
  54. }
  56. }
    ///

/ 使用ExecutorService的invokeAll方法计算 / @author 飞雪无情

/ //

public class CountSumWithCallable {

//*/*
 /* @param args

 /* @throws InterruptedException
 /* @throws ExecutionException

 /*/
public static void main(String[] args) throws InterruptedException, ExecutionException {

    int threadCounts =19;//使用的线程数
    long sum=0;

    ExecutorService exec=Executors.newFixedThreadPool(threadCounts);
    List<Callable<Long>> callList=new ArrayList<Callable<Long>>();

    //生成很大的List
    List<Integer> list = new ArrayList<Integer>();

    for (int i = 0; i <= 1000000; i++) {
        list.add(i);

    }
    int len=list.size()/threadCounts;//平均分割List

    //List中的数量没有线程数多（很少存在）
    if(len==0){

        threadCounts=list.size();//采用一个线程处理List中的一个元素
        len=list.size()/threadCounts;//重新平均分割List

    }
    for(int i=0;i<threadCounts;i++){

        final List<Integer> subList;
        if(i==threadCounts-1){

            subList=list.subList(i/*len,list.size());
        }else{

            subList=list.subList(i/*len, len/*(i+1)>list.size()?list.size():len/*(i+1));
        }

        //采用匿名内部类实现
        callList.add(new Callable<Long>(){

            public Long call() throws Exception {
                long subSum=0L;

                for(Integer i:subList){
                    subSum+=i;

                }
                System.out.println("分配给线程："+Thread.currentThread().getName()+"那一部分List的整数和为：\tSubSum:"+subSum);

                return subSum;
            }

        });
    }

    List<Future<Long>> futureList=exec.invokeAll(callList);
    for(Future<Long> future:futureList){

        sum+=future.get();
    }

    exec.shutdown();
    System.out.println(sum);

}

} 一些感言 这篇文章是昨天夜里11点多写好的，我当时是在网上看到了这个题目，就做了一下分析，写了实现代码，由于水平有限，难免有bug，这里感谢xifo等人的指正。这些帖子从发表到现在不到24小时的时间里创造了近9000的浏览次数，回复近100，这是我没有想到的，javaeye很久没这么疯狂过啦。这不是因为我的算法多好，而是因为这个题目、这篇帖子所体现出的意义。大家在看完这篇帖子后不光指正错误，还对方案进行了改进，关键是思考，人的思维是无穷的，只要我们善于发掘，善于思考，总能想出一些意想不到的方案。 从算法看，或者从题目场景对比代码实现来看，或许不是一篇很好的帖子，但是我说这篇帖子是很有意义的，方案也是在很多场景适用，有时我们可以假设这不是计算和，而是把数据写到一个个的小文件里，或者是分割进行网络传输等等，都有一定的启发，特别是回帖中的讨论。 单说一下回帖，我建议进来的人尽量看完所有的回帖，因为这里是很多人集思广益的精华，这里有他们分析问题，解决问题的思路，还有每个人提到的解决方案，想想为什么能用?为什么不能用?为什么好?为什么不好? 我一直相信：讨论是解决问题、提高水平的最佳方式！

存取之美 —— HashMap原理、源码、实践

Posted on

存取之美 —— HashMap原理、源码、实践

首页 新闻 论坛 问答 博客 招聘 更多 ▼

专栏 圈子 搜索

您还未登录 ! 我的应用 登录 注册

小白的博客

永久域名 http://grunt1223.javaeye.com/

54顶 9踩

利用方法拦截器优化Ibatis更新策略 —— ...

2009-12-09

存取之美 —— HashMap原理、源码、实践

文章分类:Java编程 HashMap是一种十分常用的数据结构，作为一个应用开发人员，对其原理、实现的加深理解有助于更高效地进行数据存取。本文所用的jdk版本为1.5。 使用HashMap 《Effective JAVA》中认为，99%的情况下，当你覆盖了equals方法后，请务必覆盖hashCode方法。默认情况下，这两者会采用Object的“原生”实现方式，即： protected native int hashCode(); public boolean equals(Object obj) { return (this == obj); } hashCode方法的定义用到了native关键字，表示它是由C或C++采用较为底层的方式来实现的，你可以认为它返回了该对象的内存地址；而缺省equals则认为，只有当两者引用同一个对象时，才认为它们是相等的。如果你只是覆盖了equals()而没有重新定义hashCode()，在读取HashMap的时候，除非你使用一个与你保存时引用完全相同的对象作为key值，否则你将得不到该key所对应的值。 另一方面，你应该尽量避免使用“可变”的类作为HashMap的键。如果你将一个对象作为键值并保存在HashMap中，之后又改变了其状态，那么HashMap就会产生混乱，你所保存的值可能丢失（尽管遍历集合可能可以找到）。可参考http://www.ibm.com/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，以此类推；这点可以从源码中看出来： void addEntry(int hash, K key, V value, int bucketIndex) { Entry e = table[bucketIndex]; table[bucketIndex] = new Entry(hash, key, value, e); if (size++ >= threshold) resize(2 /* table.length); } 而每当hashMap扩容后，内部的每个元素存放的位置都会发生变化（因为元素的最终位置是其hashCode对key空间长度取模而得），因此resize方法中又会调用transfer函数，用来重新分配内部的元素；这个过程成为rehash，是十分消耗性能的，因此在可预知元素的个数的情况下，一般应该避免使用缺省的initialCapacity，而是通过构造函数为其指定一个值。例如我们可能会想要将数据库查询所得1000条记录以某个特定字段（比如ID）为key缓存在hashMap中，为了提高效率、避免rehash，可以直接指定initialCapacity为2048。 另一个值得注意的地方是，hashMap其key空间的长度一定为2的N次方，这一点可以从一下源码中看出来： int capacity = 1; while (capacity < initialCapacity) 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 Guthrie《Java Performence》中对此也大加抨击。为了弄清楚这个问题，Bruce Eckel（Thinking in JAVA的作者）专程采访了java.util.hashMap的作者Joshua Bloch，并将他采用这种设计的原因放到了网上（http://www.roseindia.net/javatutorials/javahashmap.shtml） 。 上述设计的原因在于，取模运算在包括JAVA在内的大多数语言中的效率都十分低下，而当除数为2的N次方时，取模运算将退化为最简单的位运算，其效率明显提升（按照Bruce Eckel给出的数据，大约可以提升5～8倍） 。看看JDK中是如何实现的： static int indexFor(int h, int length) { return h & (length-1); } 当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中的源码： static int hash(Object x) { int h = x.hashCode(); h += ~(h << 9); h ^= (h >>> 14); h += (h << 4); h ^= (h >>> 10); return h; } 采用这种旋转Hash函数的主要目的是让原有hashCode的高位信息也能被充分利用，且兼顾计算效率以及数据统计的特性，其具体的原理已超出了本文的领域。 加快Hash效率的另一个有效途径是编写良好的自定义对象的HashCode，String的实现采用了如下的计算方法： for (int i = 0; i < len; i++) { h = 31/h + val[off++]; } hash = h; 这种方法HashCode的计算方法可能最早出现在Brian W. Kernighan和Dennis M. Ritchie的《The C Programming Language》中，被认为是性价比最高的算法（又被称为times33算法，因为C中乘数常量为33，JAVA中改为31），实际上，包括List在内的大多数的对象都是用这种方法计算Hash值。 另一种比较特殊的hash算法称为布隆过滤器，它以牺牲细微精度为代价，换来存储空间的大量节俭，常用于诸如判断用户名重复、是否在黑名单上等等，可以参考李开复的数学之美系列第13篇（http://googlechinablog.com/2006/08/blog-post.html） Fail-Fast机制 众所周知，HashMap不是线程安全的集合类。但在某些容错能力较好的应用中，如果你不想仅仅因为1%的可能性而去承受hashTable的同步开销，则可以考虑利用一下HashMap的Fail-Fast机制，其具体实现如下： Entry nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); …… } 其中modCount为HashMap的一个实例变量，并且被声明为volatile，表示任何线程都可以看到该变量被其它线程修改的结果（根据JVM内存模型的优化，每一个线程都会存一份自己的工作内存，此工作内存的内容与本地内存并非时时刻刻都同步，因此可能会出现线程间的修改不可见的问题） 。使用Iterator开始迭代时，会将modCount的赋值给expectedModCount，在迭代过程中，通过每次比较两者是否相等来判断HashMap是否在内部或被其它线程修改。HashMap的大多数修改方法都会改变ModCount，参考下面的源码： public V put(K key, V value) { K k = maskNull(key); int hash = hash(k); int i = indexFor(hash, table.length); for (Entry e = table[i]; e != null; e = e.next) { if (e.hash == hash && eq(k, e.key)) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, k, value, i); return null; } 以put方法为例，每次往HashMap中添加元素都会导致modCount自增。其它诸如remove、clear方法也都包含类似的操作。 从上面可以看出，HashMap所采用的Fail-Fast机制本质上是一种乐观锁机制，通过检查状态——没有问题则忽略——有问题则抛出异常的方式，来避免线程同步的开销，下面给出一个在单线程环境下发生Fast-Fail的例子： class Test { public static void main(String[] args) { java.util.HashMap map=new java.util.HashMap(); map.put(new Object(), "a"); map.put(new Object(), "b"); java.util.Iterator it=map.keySet().iterator(); while(it.hasNext()){ it.next(); map.put("", ""); System.out.println(map.size()); } } 运行上面的代码会抛出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三个属性来表示该集合类的头与前后“指针”，其具体用法类似于数据结构中的双链表，以删除某个元素为例： private void remove() { before.after = after; after.before = before; } 实际上就是改变前后指针所指向的元素。 显然，由于增加了维护链接列表的开支，其性能要比 HashMap 稍逊一筹，不过有一点例外：LinkedHashMap的迭代所需时间与其的所包含的元素成比例；而HashMap 迭代时间很可能开支较大，因为它所需要的时间与其容量（分配给Key空间的长度）成比例。一言以蔽之，随机存取用HashMap，顺序存取或是遍历用LinkedHashMap。 LinkedHashMap还重写了removeEldestEntry方法以实现自动清除过期数据的功能，这在HashMap中是无法实现的，因为后者其内部的元素是无序的。默认情况下，LinkedHashMap中的removeEldestEntry的作用被关闭，其具体实现如下： protected boolean removeEldestEntry(Map.Entry eldest) { return false; } 可以使用如下的代码覆盖removeEldestEntry： private static final int MAX_ENTRIES = 100; protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_ENTRIES; } 它表示，刚开始，LinkedHashMap中的元素不断增长；当它内部的元素超过MAX_ENTRIES（100）后，每当有新的元素被插入时，都会自动删除双链表中最前端（最旧）的元素，从而保持LinkedHashMap的长度稳定。 缺省情况下，LinkedHashMap采取的更新策略是类似于队列的FIFO，如果你想实现更复杂的更新逻辑比如LRU（最近最少使用） 等，可以在构造函数中指定其accessOrder为true，因为的访问元素的方法（get）内部会调用一个“钩子”，即recordAccess，其具体实现如下： void recordAccess(HashMap m) { LinkedHashMap lm = (LinkedHashMap)m; if (lm.accessOrder) { lm.modCount++; remove(); addBefore(lm.header); } } 上述代码主要实现了这样的功能：如果accessOrder被设置为true，则每次访问元素时，都将该元素移至headr的前面，即链表的尾部。将removeEldestEntry与accessOrder一起使用，就可以实现最基本的内存缓存，具体代码可参考[http://bluepopopo.javaeye.com/blog/180236*](http://grunt1223.javaeye.com/blog/http://bluepopopo.javaeye.com/blog/180236)。 WeakHashMap 99%的JAVA教材教导我们不要去干预JVM的垃圾回收机制，但JAVA中确实存在着与其密切相关的四种引用：强引用、软引用、弱引用以及幻象引用。 JAVA中默认的HashMap采用的是采用类似于强引用的强键来管理的，这意味着即使作为key的对象已经不存在了（指没有任何一个引用指向它），也仍然会保留在HashMap中，在某些情况下（例如内存缓存）中，这些过期的条目可能会造成内存泄漏等问题。 WeakHashMap采用的策略是，只要作为key的对象已经不存在了（超出生命周期），就不会阻止垃圾收集器清空此条目，即使当前机器的内存并不紧张。不过，由于GC是一个优先级很低的线程，因此不一定会很快发现那些只具有弱引用的对象，除非你显示地调用它，可以参考下面的例子： public static void main(String[] args) { Mapmap = new WeakHashMap(); map.put(new String("Alibaba"), "alibaba"); while (map.containsKey("Alibaba")) { try { Thread.sleep(500); } catch (InterruptedException ignored) { } System.out.println("Checking for empty"); System.gc(); } 上述代码输出一次Checking for empty就退出了主线程，意味着GC在最近的一次垃圾回收周期中清除了new String(“Alibaba”),同时WeakHashMap也做出了及时的反应，将该键对应的条目删除了。如果将map的类型改为HashMap的话，由于其内部采用的是强引用机制，因此即使GC被显示调用，map中的条目依然存在，程序会不断地打出Checking for empty字样。另外，在使用WeakHashMap的情况下，若是将 map.put(new String("Alibaba"), "alibaba"); 改为 map.put("Alibaba", "alibaba"); 程序还是会不断输出Checking for empty。这与前面我们分析的WeakHashMap的弱引用机制并不矛盾，因为JVM为了减小重复创建和维护多个相同String的开销，其内部采用了蝇量模式（《JAVA与模式》），此时的“Alibaba”是存放在常量池而非堆中的，因此即使没有对象指向“Alibaba”，它也不会被GC回收。弱引用特别适合以下对象：占用大量内存，但通过垃圾回收功能回收以后很容易重新创建。 介于HashMap和WeakHashMap之中的是SoftHashMap，它所采用的软引用的策略指的是，垃圾收集器并不像其收集弱可及的对象一样尽量地收集软可及的对象，相反，它只在真正 “需要” 内存时才收集软可及的对象。软引用对于垃圾收集器来说是一种“睁一只眼，闭一只眼”方式，即 “只要内存不太紧张，我就会保留该对象。但是如果内存变得真正紧张了，我就会去收集并处理这个对象。” 就这一点看，它其实要比WeakHashMap更适合于实现缓存机制。遗憾的是，JAVA中并没有实现相关的SoftHashMap类（Apache和Google提供了第三方的实现），但它却是提供了两个十分重要的类java.lang.ref.SoftReference以及ReferenceQueue，可以在对象应用状态发生改变是得到通知，可以参考com.alibaba.common.collection.SofthashMap中processQueue方法的实现: private ReferenceQueue queue = new ReferenceQueue(); ValueCell vc; Map hash = new HashMap(initialCapacity, loadFactor); …… while ((vc = (ValueCell) queue.poll()) != null) { if (vc.isValid()) { hash.remove(vc.key); } else { valueCell.dropped--; } } } processQueue方法会在几乎所有SoftHashMap的方法中被调用到，JVM会通过ReferenceQueue的poll方法通知该对象已经过期并且当前的内存现状需要将它释放，此时我们就可以将其从hashMap中剔除。事实上，默认情况下，Alibaba的MemoryCache所使用的就是SoftHashMap。

54 顶9 踩 利用方法拦截器优化Ibatis更新策略 —— ...

16 楼 beneo 2010-06-18 引用

是不是叫做Floyed的人都是神啊 15 楼 usiboy 2009-12-27 引用

这篇文章分析的很透彻，无论是从算法的角度还是从应用的层面都讲的挺详细的，本人也在研究HashMap的写法，但不足的是少了一点HashMap的设计模式，从《Effective Java》这本书来看，也提到了一点HashMap的模式，我最不明白的是Entry的设计，希望能和楼主一起讨论这个Entry设计的目的。

14 楼 dvaknheo 2009-12-15 引用

有没有碰到过 hash 碰撞的诡异现象？ 13 楼 liuxuejin 2009-12-15 引用

写得真好，我现在正在研究这个东西！

12 楼 longhua828 2009-12-14 引用

真强，本人第一次发帖，好不容易通过了论坛发帖规则测试，太难了 11 楼 kellersoon 2009-12-12 引用

好文章， 感觉下边这段很巧妙 static int indexFor(int h, int length) { return h & (length-1); }

10 楼 liusu 2009-12-11 引用

Test '%' and '&' package test; /// / Why HashMap use operation '&' replace '%' ? / / Test: / % Cost 2844ms / & Cost 921ms / / So. / @author seany1 / // public class ModolTest { public static void main(String[] args) { int base = 1 << 4; int all = 100000000; System.out.println(base); String hashTest = new String("Test hash"); long start = System.currentTimeMillis(); for (int i = 0; i < all; i++) { int x = hashTest.hashCode() % base; } long end = System.currentTimeMillis(); System.out.println("'%' Cost " + (end - start) + "ms"); start = System.currentTimeMillis(); for (int i = 0; i < all; i++) { int x = hashTest.hashCode() & base; } end = System.currentTimeMillis(); System.out.println("'&' Cost " + (end - start) + "ms"); } } 9 楼 andyu2008 2009-12-11 引用

看完了，楼主写的的确很不错！

8 楼 Aguo 2009-12-11 引用

very well 7 楼 J-catTeam 2009-12-10 引用

为什么都要说hashcode就是地址呢··· 呵呵 ~散列码

6 楼 challengerjiang 2009-12-10 引用

真的很好哦 5 楼 idealab 2009-12-10 引用

4 楼 enhydra 2009-12-10 引用

真不错 3 楼 lijiecong 2009-12-09 引用

写的非常好，数学之美不是李开复写的：）

2 楼 猫尾摆摆 2009-12-09 引用

研究的很透彻了，对旋转hash没明白，呵呵 1 楼 mylazygirl 2009-12-09 引用

写的不错~~

发表评论

您还没有登录，请登录后发表评论(快捷键 Alt+S / Ctrl+Enter)

grunt1223的博客

grunt1223

搜索本博客

最近访客 >>更多访客

mmBlue的博客

mmBlue

nickevin的博客

nickevin yingmu0591的博客

yingmu0591

xlongbuilder的博客

xlongbuilder

博客分类

最近加入圈子

存档

最新评论

© 2014 RobinChia