- 浏览: 248003 次
- 性别:
- 来自: 南京
文章分类
最新评论
-
mabusyao:
漠北空城 写道请问下,你这个是JDK版本是多少呢?!忘记了,应 ...
HashMap 源码解读 -
漠北空城:
请问下,你这个是JDK版本是多少呢?!
HashMap 源码解读 -
schumee:
完美团队~
项目沉思录 - 1.1 -
winie:
整理下 搞成引擎嘛 国产需要这样的engine
简单工作流引擎 -
mabusyao:
某位同学给我提供的堪称完美的解决方案:1. 将三个int数组放 ...
CraneWork
HashMap是我们在日常写代码时最常用到的一个数据结构,它为我们提供key-value形式的数据存储。同时,它的查询,插入效率都非常高。
在之前的排序算法总结里面里,我大致学习了HashMap的实现原理,并制作了一个简化版本的HashMap。 今天,趁着项目的间歇期,我又仔细阅读了Java中的HashMap的实现。
HashMap的初始化:
initialCapacity表示了HashMap中初始的大小,loadFactor则表示每次当HashMap中的空间不够时,按什么样的比例来扩展空间。
我们来看下HashMap是怎样扩展空间的:
可以看到这个方法并不是public的,因此用户无法手动去调用这个方法。
变量threshod维持着HashMap下一次增长将要到达的长度。而MAXIMUM_CAPACITY则包含了最大可能长度:1 << 30。
注意,这个长度是2的倍数,我们在后面会经常看到2的幂数,事实上,HashMap规定了它的table长度只能是2的幂数,因此,即使你设置了loadFactor, 它也未必按照你的想法来增长。这点,从构造器方法里面可以看出:
可以看见capacity的构建方法,先是设置为1,然后不停的左移直到大于等于initialCapacity。
trasfer方法的实现需要好好看一下:
首先是onentry方法, 这个方法先判断是否有其它的线程在操作该HashMap进行resize,如果没有,将contentionFlag 设为1, 如果已经有了,就设为2,表示已经有冲突了。如果已经有冲突存在了,直接抛exception。
无怪网上都说HashMap是非线程安全的,而HashTable才是线程安全的。从这个角度理解,确实是这样的。
而当onexit时,如果contentionFlag为1,则直接结束,如果为2,表示在onentry时已经有冲突,那么直接抛出excpetion。
这一部分内容非常有意思,可以在别的地方借鉴这种用法。想起来之前有人问我关于线程同步的问题,我想这个应该是个很好的解决办法,等回头看看HashTable这个号称可以支持多线程的结构之后,在综合分析一下这块内容。 而在最新版本的JDK6b17中,似乎已经去掉了该部分的代码。
而对于transfer0这个方法名,实在是太难听了。
这个方法主要是创建了一个新数组,并把旧数组里面的数据放到新数组里。这里有两个很重要的内容,我们一个一个看。
a. 链表的结构
我们已经知道了hashmap中对于相同hashcode的值,是通过链表的形式挂在数组位上面的,但当我们在做resize的时候,整个链表的顺序其实是被颠倒了。 因为是private代码,所以其实并没有对此有太多的解释。我所奇怪的是,如果不把链表的顺序颠倒的话,这段代码会很容易写,性能也会高很多,可是为什么要特意去做这件事情呢?
我曾经怀疑java中是个环状的链表,可是看代码似乎又不是。。。奇怪的东西。
b. indexFor方法
这里要先看看源码
indexFor的代码里面,通过h和length-1做并操作,因为length的值永远是2的幂数(参见排序算法),因此这个方法就是对h进行取模,h % 2^p, 返回的将是h的p个最低位组成的数字。这样做究竟有什么好处呢?
最大的好处就是,对于hashcode值大于table长度的,可以将之映射到table长度以内的值。其它的,我还真没看出有什么好处。
再看hash方法,事实上,java中的HashMap并不是直接去的object的hashcode值,而是先对他进行了一个简单的调整,也就是hash这个方法。
看对于该方法的介绍,该方法保证了load因子为8,即使该hashcode使用的是将每位的值乘以一个常数。
我们知道我们常常设计hashcode的方法是,比如一个string,就把每一位取出来,乘以一个常数,通常是质数,然后相加,这样得到的hashcode,会在这里得到更好的调整。
算法导论里面是这么说的:
假设机器的字长是w,那么我们就可以选择A的值为 s/2^w, s为0到2^w之间的整数,这样s=A× 2^w 用k 乘以s,取低位,再从低位中取p位,这几位就形成了k的hash值。官方建议A可以取黄金分割0.618。
这块内容是在是太复杂了,现在我也只能深入到这一步,再继续下去也看不太懂了。 JDK的作者建议去看看程序设计艺术第三卷,可惜我连第一卷都没看完。看来是要等将来解决这个问题了。
不过有一点要提的是,这种方法只在最新版本的HashMap中才有,老版本的都是直接用了key对象的hashcode。
HashMap中的其它方法都比较常规,这里就不赘述了。值得一提的是,put方法,如果key已经存在的话,会用新的value替代旧的value,并将旧value返回,否则返回空。
最后,有一个从来没用过的关键字吸引了我:
transient volatile int modCount;
查了下书,volatile是用来处理线程同步的,这里就直接转southking的一篇博文:
我们知道,在Java中设置变量值的操作,除了long和double类型的变量外都是原子操作,也就是说,对于变量值的简单读写操作没有必要进行同步。
这在JVM 1.2之前,Java的内存模型实现总是从主存读取变量,是不需要进行特别的注意的。而随着JVM的成熟和优化,现在在多线程环境下volatile关键字的使用变得非常重要。
在当前的Java内存模型下,线程可以把变量保存在本地内存(比如机器的寄存器)中,而不是直接在主存中进行读写。这就可能造成一个线程在主存中修改了一个变量的值,而另外一个线程还继续使用它在寄存器中的变量值的拷贝,造成数据的不一致。
要解决这个问题,只需要像在本程序中的这样,把该变量声明为volatile(不稳定的)即可,这就指示JVM,这个变量是不稳定的,每次使用它都到主存中进行读取。一般说来,多任务环境下各任务间共享的标志都应该加volatile修饰。
Volatile修饰的成员变量在每次被线程访问时,都强迫从共享内存中重读该成员变量的值。而且,当成员变量发生变化时,强迫线程将变化值回写到共享内存。这样在任何时刻,两个不同的线程总是看到某个成员变量的同一个值。
Java语言规范中指出:为了获得最佳速度,允许线程保存共享成员变量的私有拷贝,而且只当线程进入或者离开同步代码块时才与共享成员变量的原始值对比。
这样当多个线程同时与某个对象交互时,就必须要注意到要让线程及时的得到共享成员变量的变化。
而volatile关键字就是提示VM:对于这个成员变量不能保存它的私有拷贝,而应直接与共享成员变量交互。
使用建议:在两个或者更多的线程访问的成员变量上使用volatile。当要访问的变量已在synchronized代码块中,或者为常量时,不必使用。
由于使用volatile屏蔽掉了VM中必要的代码优化,所以在效率上比较低,因此一定在必要时才使用此关键字。
本想单独为HashTable写一篇博文的,但是等学习完之后,觉得大部分跟HashMap是一样的,我所期待的线程同步居然仅仅是通过synchronized 来实现的。 想想还是算了,就在这里列出HashTable与HashMap的几个区别:
1. 数组的长度不必是2的倍数,而是可以为任意数值。
2. 求index的办法也便简单了:(hash & 0x7FFFFFFF) % array.length
3. 对于hash值不再做特殊处理,直接使用。
即使我对HashMap的实现方法还有疑惑,但是毫无疑虑,那些算法可以提高效率。 而在Hashtable中,这些提高效率的算法都没有了,同时,过多的sychronized定义,必然会降低performance。
忘记了,应该是1.5左右吧。很老的版本了,新版本貌似已经改了很多。
在之前的排序算法总结里面里,我大致学习了HashMap的实现原理,并制作了一个简化版本的HashMap。 今天,趁着项目的间歇期,我又仔细阅读了Java中的HashMap的实现。
HashMap的初始化:
public HashMap(int initialCapacity, float loadFactor) public HashMap(int initialCapacity) public HashMap() public HashMap(Map<? extends K, ? extends V> m)
initialCapacity表示了HashMap中初始的大小,loadFactor则表示每次当HashMap中的空间不够时,按什么样的比例来扩展空间。
我们来看下HashMap是怎样扩展空间的:
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); }
可以看到这个方法并不是public的,因此用户无法手动去调用这个方法。
变量threshod维持着HashMap下一次增长将要到达的长度。而MAXIMUM_CAPACITY则包含了最大可能长度:1 << 30。
注意,这个长度是2的倍数,我们在后面会经常看到2的幂数,事实上,HashMap规定了它的table长度只能是2的幂数,因此,即使你设置了loadFactor, 它也未必按照你的想法来增长。这点,从构造器方法里面可以看出:
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init(); }
可以看见capacity的构建方法,先是设置为1,然后不停的左移直到大于等于initialCapacity。
trasfer方法的实现需要好好看一下:
private transient int contentionFlag = 0; void transfer(Entry[] newTable) { onEntry(); try { transfer0(newTable); } finally { onExit(); } } private synchronized void onEntry() { switch(contentionFlag) { case(0): contentionFlag=1; /* Free -> Busy */ break; case(1): contentionFlag=2; /* Busy -> Contended */ //FALLTHRU case(2): throw new ConcurrentModificationException( "concurrent access to HashMap attempted by " + Thread.currentThread()); default: throw new RuntimeException( "Unexpected contentionFlag " + contentionFlag); } } private synchronized void onExit() { int oldContentionFlag=contentionFlag; contentionFlag=0; switch(oldContentionFlag) { case(1): break; /* Busy -> Free */ case(2): throw new ConcurrentModificationException( /* Contended -> Free */ "concurrent access to HashMap attempted by " + Thread.currentThread()); default: throw new RuntimeException( "Unexpected contentionFlag " + oldContentionFlag); } } private void transfer0(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }
首先是onentry方法, 这个方法先判断是否有其它的线程在操作该HashMap进行resize,如果没有,将contentionFlag 设为1, 如果已经有了,就设为2,表示已经有冲突了。如果已经有冲突存在了,直接抛exception。
无怪网上都说HashMap是非线程安全的,而HashTable才是线程安全的。从这个角度理解,确实是这样的。
而当onexit时,如果contentionFlag为1,则直接结束,如果为2,表示在onentry时已经有冲突,那么直接抛出excpetion。
这一部分内容非常有意思,可以在别的地方借鉴这种用法。想起来之前有人问我关于线程同步的问题,我想这个应该是个很好的解决办法,等回头看看HashTable这个号称可以支持多线程的结构之后,在综合分析一下这块内容。 而在最新版本的JDK6b17中,似乎已经去掉了该部分的代码。
而对于transfer0这个方法名,实在是太难听了。
这个方法主要是创建了一个新数组,并把旧数组里面的数据放到新数组里。这里有两个很重要的内容,我们一个一个看。
a. 链表的结构
我们已经知道了hashmap中对于相同hashcode的值,是通过链表的形式挂在数组位上面的,但当我们在做resize的时候,整个链表的顺序其实是被颠倒了。 因为是private代码,所以其实并没有对此有太多的解释。我所奇怪的是,如果不把链表的顺序颠倒的话,这段代码会很容易写,性能也会高很多,可是为什么要特意去做这件事情呢?
我曾经怀疑java中是个环状的链表,可是看代码似乎又不是。。。奇怪的东西。
b. indexFor方法
这里要先看看源码
static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } /** * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); }
indexFor的代码里面,通过h和length-1做并操作,因为length的值永远是2的幂数(参见排序算法),因此这个方法就是对h进行取模,h % 2^p, 返回的将是h的p个最低位组成的数字。这样做究竟有什么好处呢?
最大的好处就是,对于hashcode值大于table长度的,可以将之映射到table长度以内的值。其它的,我还真没看出有什么好处。
再看hash方法,事实上,java中的HashMap并不是直接去的object的hashcode值,而是先对他进行了一个简单的调整,也就是hash这个方法。
看对于该方法的介绍,该方法保证了load因子为8,即使该hashcode使用的是将每位的值乘以一个常数。
我们知道我们常常设计hashcode的方法是,比如一个string,就把每一位取出来,乘以一个常数,通常是质数,然后相加,这样得到的hashcode,会在这里得到更好的调整。
算法导论里面是这么说的:
假设机器的字长是w,那么我们就可以选择A的值为 s/2^w, s为0到2^w之间的整数,这样s=A× 2^w 用k 乘以s,取低位,再从低位中取p位,这几位就形成了k的hash值。官方建议A可以取黄金分割0.618。
这块内容是在是太复杂了,现在我也只能深入到这一步,再继续下去也看不太懂了。 JDK的作者建议去看看程序设计艺术第三卷,可惜我连第一卷都没看完。看来是要等将来解决这个问题了。
不过有一点要提的是,这种方法只在最新版本的HashMap中才有,老版本的都是直接用了key对象的hashcode。
HashMap中的其它方法都比较常规,这里就不赘述了。值得一提的是,put方法,如果key已经存在的话,会用新的value替代旧的value,并将旧value返回,否则返回空。
最后,有一个从来没用过的关键字吸引了我:
transient volatile int modCount;
查了下书,volatile是用来处理线程同步的,这里就直接转southking的一篇博文:
我们知道,在Java中设置变量值的操作,除了long和double类型的变量外都是原子操作,也就是说,对于变量值的简单读写操作没有必要进行同步。
这在JVM 1.2之前,Java的内存模型实现总是从主存读取变量,是不需要进行特别的注意的。而随着JVM的成熟和优化,现在在多线程环境下volatile关键字的使用变得非常重要。
在当前的Java内存模型下,线程可以把变量保存在本地内存(比如机器的寄存器)中,而不是直接在主存中进行读写。这就可能造成一个线程在主存中修改了一个变量的值,而另外一个线程还继续使用它在寄存器中的变量值的拷贝,造成数据的不一致。
要解决这个问题,只需要像在本程序中的这样,把该变量声明为volatile(不稳定的)即可,这就指示JVM,这个变量是不稳定的,每次使用它都到主存中进行读取。一般说来,多任务环境下各任务间共享的标志都应该加volatile修饰。
Volatile修饰的成员变量在每次被线程访问时,都强迫从共享内存中重读该成员变量的值。而且,当成员变量发生变化时,强迫线程将变化值回写到共享内存。这样在任何时刻,两个不同的线程总是看到某个成员变量的同一个值。
Java语言规范中指出:为了获得最佳速度,允许线程保存共享成员变量的私有拷贝,而且只当线程进入或者离开同步代码块时才与共享成员变量的原始值对比。
这样当多个线程同时与某个对象交互时,就必须要注意到要让线程及时的得到共享成员变量的变化。
而volatile关键字就是提示VM:对于这个成员变量不能保存它的私有拷贝,而应直接与共享成员变量交互。
使用建议:在两个或者更多的线程访问的成员变量上使用volatile。当要访问的变量已在synchronized代码块中,或者为常量时,不必使用。
由于使用volatile屏蔽掉了VM中必要的代码优化,所以在效率上比较低,因此一定在必要时才使用此关键字。
本想单独为HashTable写一篇博文的,但是等学习完之后,觉得大部分跟HashMap是一样的,我所期待的线程同步居然仅仅是通过synchronized 来实现的。 想想还是算了,就在这里列出HashTable与HashMap的几个区别:
1. 数组的长度不必是2的倍数,而是可以为任意数值。
2. 求index的办法也便简单了:(hash & 0x7FFFFFFF) % array.length
3. 对于hash值不再做特殊处理,直接使用。
即使我对HashMap的实现方法还有疑惑,但是毫无疑虑,那些算法可以提高效率。 而在Hashtable中,这些提高效率的算法都没有了,同时,过多的sychronized定义,必然会降低performance。
评论
2 楼
mabusyao
2015-06-30
漠北空城 写道
请问下,你这个是JDK版本是多少呢?!
忘记了,应该是1.5左右吧。很老的版本了,新版本貌似已经改了很多。
1 楼
漠北空城
2015-06-12
请问下,你这个是JDK版本是多少呢?!
发表评论
-
各种语言写的wordcount
2015-09-24 16:07 0Java版本: String input ... -
数组双指针算法的研究
2015-07-14 16:59 2423双指针算法在数组/链 ... -
初识ThreadLocal
2015-07-07 13:15 1471最近公司在进行Java开发人员的招聘活动,其中有一道面试题 ... -
摩尔投票法
2015-06-30 20:13 18286摩尔投票法 提问: 给定一个int型数组,找出该数 ... -
小心寄存器
2012-11-08 13:53 4试试这段代码就知道了 public cla ... -
简单工作流引擎
2012-07-06 16:58 2351从公司的一个项目中挖出来的工作流引擎的代码,虽然是一个很简单的 ... -
Always clean the ThreadLocal variables.
2012-05-24 09:16 1178Any variable stored in ThreadLo ... -
STRUTS2 源码 - Logging System
2012-05-24 08:51 1364看了STRUTS2的源码,了解了它的logging系统,觉得还 ... -
在线词典的数据结构实现。
2012-05-18 08:37 0昨天在网上看到了一道百度的面试题: Baidu写道 ... -
Log4j 代码学习 - Factory
2012-05-17 08:47 1079我们最早提到,Log4j的初始代码在LogManager的静态 ... -
Log4j 代码学习 - Appender
2012-05-16 09:09 1315在上一篇文章里,我们 ... -
Log4j 代码学习
2012-05-15 14:58 1126最近闲来无事,正好手头上有Log4j的代码,于是就拿来学习了下 ... -
java7中的ThreadLocalRandom(转)
2012-01-20 09:08 4299今天早上看到一个关于java7中的ThreadLocalRan ... -
(转)追MM与23种设计模式
2011-11-16 14:13 9641、FACTORY—追MM少不了请吃饭了,麦当劳的鸡翅和肯德 ... -
(转)Java 参数列表
2011-11-05 19:48 2859下面的讨论以Windows ... -
(转)TOMCAT源码分析
2011-10-17 16:06 2066TOMCAT源码分析(启动框架 ... -
java写的四则运算器
2011-08-19 22:19 2665本打算做一个从RE到NFA的转换器,思路已经理清了,但是在动手 ... -
MBeanServer中instantiate 和 invoke的区别
2011-06-02 11:52 1267JMX中有两种方式调用另一个MBean中的方法 先创建一个M ... -
JMX 的一个简单例子
2011-05-30 17:41 1027废话不多说,上代码: HelloWorldMBean接口 ... -
执行JAR文件的一些问题(转)
2011-03-25 13:41 1354大家都知道一个java应用项目可以打包成一个jar,当然你必须 ...
相关推荐
HashMap之resize()方法源码解读,分两部分概述扩容方法涉及到的处理:创建新数组,将旧数组元素转移到新数组上
hashmap源码解读,并且会对比JDK7和8实现的不同,已更新ConcurrentHashMap部分,且结合记录了多个视频的笔记。可以在https://blog.csdn.net/hancoder/article/details/105424922 获取最新笔记地址,下载过旧文件的...
大厂HashMap面试源码解读,适合面试、初学者的人,HahsMap源码解读
对HashMap的put方法的源码进行详细解读,分析put方法源码中的内在逻辑关系,欣赏源码独特之美,从中学习更为精致的编程思维
HashMap中红黑树TreeNode的split方法源码解读,对split方法源码的上下文/变量定义,及所调用的关键方法都给出了详细解释说明,欢迎指正
HashMap$TreeNode确保根节点为头节点的moveRootToFront方法源码解读,分析其各个步骤,并配有示意图
本文主要以几个方面来讲解一下HashMap: 1、HashMap默认容量 2、HashMap如何扩容 3、HashMap的数组大小为什么一定要是2的幂 ...(HashMap的源码翻译) 假如你创建HashMap的时候传入一个不是2的幂的初始值,HashMap会
HashMap、ConcurrentHashMap源码级解读,并且对比了JDK7和8实现的不同,进行了大量的解释,结合了多个学习视频
在本套课程中,将会非常深入、非常详细、非常全面的解读HashMap以及源码底层设计的思想。从底层的数据结构到底层源码分析以及怎样使用提高HashMap集合的效率问题等进行分析。如果掌握本套课程,那么再看其他javase的...
本仓库记录了我的Java学习进阶之路,涵盖了Java基础、JDK源码、JVM中...Java集合框架源码解读(2)——HashMap Java集合框架源码解读(3)——LinkedHashMap Java集合框架源码解读(4)——WeakHashMap Java集合框架源码解读
HashMap之往红黑树添加元素-putTreeVal方法源码解读:当要put的元素所在数组索引位置已存在元素,且是红黑树类型时,就会调用putTreeVal方法添加元素到红黑树上,具体操作步骤如下: 1. 从根节点开始,到左右子树,...
08HashMap与ConcurrenthashMap源码解读 09MySQL深度原理解析 10Netty深度源码解读 11SpringCloud微服务框架源码解读 12彻底搞懂分布式锁架构设计原理 13分布式数据一致性设计原理 14分布式消息中间件 15实战新零售...
java forkjoin 源码 -- -- geomesa -- spring -- 算法 ...[乐观锁&悲观锁,重入锁&非重入锁,公平锁&非公平锁,锁粒度] ...[HashMap, ConcurrentHashMap源码] [ArrayList, LinkedList, CopyOnWriteArrayList源码]
java所有集合类底层源码解析汇总,包括ArrayList、HashMap、HashSet、LinkedList、TreeMap、HashSet、ConcurrentHashMap等集合框架的底层实现源码大白话解读。
java集合框架总结 Collection体系结构 ArrayList源码解读 HashMap HashSet 深入讲解java集合框架
源码解读 String源码系列 List源码系列 ArrayList LinkedList CopyOnWriteArrayList Vector Map源码系列 HashMap LinkedHashMap ConcurrentHashMap TreeMap Hashtable Set源码系列 HashSet LinkedHashSet TreeSet ...
限于个人水平出现的解读错误 编辑错误 排版不统一 如发现有错,欢迎指正! 如果对你有用,不妨点个star吧 !(。・ω・。) 近期计划:以jdk为主,java.lang和java.util下一些重要的类以及juc,将来可能会写web框架...