HashMap源码解析

对于HashMap,如果是java程序员,那么定然不会陌生,对于HashMap,应该说是最常用的一种Map结构了,同样在面试当中也会屡屡被提问到,常见的几种题目:

  • HashMap的默认容量?
  • HashMap是如何扩容的?
  • HashMap的数组大小为什么一定是2的幂?
  • HashMap为什么是线程安全的?
  • Java7到Java8做了哪些改进?为什么?

因为重要,所以我也就学习源码,并且将学习心得记录下来,与大家一起学习。

首先 再看HashMap之前,我们来简单回顾一下哈希表

哈希表是由一些基于哈希值的桶和链表所构成的。哈希桶就是可以快速检索的数据结构,举个例子 如果要寻找电话本的人的联系方式,我们可以利用拼音的首字母快速定位到这个联系人,存放这些字母的就叫哈希桶。本质上,哈希桶就是 将一个元素映射成一个可以快速检索的哈希值。

哈希桶加上数组就构成了哈希表,数组的好处是随机寻址的速度与长度无关,时间复杂度是O(1),但是哈希表最大的缺点是会发生碰撞,如果多个元素的哈希值是相同的,那么我们就说哈希值发生了碰撞,为了解决这个问题,我们将数组换成了链表,找到哈希值时,通过哈希桶里可以精确的找到所要查找的元素。平均差找时间都是O(1)。在java世界中,我们用来表达哈希表的数据结构就是HashMap。

HashMap源码解析

哈希桶的实现是由hashcode实现的int hashcode 底下有对象:object1,object2….

我们先来看java7的HashMap。

经典的数据结构:数组加链表。

通过查看源码 我们可以知晓HashMap的默认容量为你16,如果改变负载因子 并且将初始值设为17 结果会怎么样么?再次点开源码,我们会发现他会向上取整为2的幂也就是变成了32.之后我们可以看到负载因子是0.75.

这里有一个问题,就是桶的初始化容量是16个,而我们的HashCode值是-2^31~2^31-1,42亿个数。那么我们怎么从任意一个int变成0~n-1。聪明的你肯定想到了取余这个想法,但是在这个方法有两个缺点:

  • 负数取模还是负数,所以我们需要把负数变为正数
  • 速率较慢

那么我们点开源码发现,为了寻找要插入的元素的索引值,做了一个鬼畜的操作:hash&(length-1),做这样一个位运算,那么这操作正好可以解释为什么我们需要输进去的HashMap的初始容量是2的幂,我们可以看出hash&(2^n-1),最后的下标就是Hashmap对应的2^n-1的个数下标,之所以把容量定为2的幂,就是因为让2^n-1位运算时拿到的值全部是1,这样做与运算就可以快速找到下标并且分布还是均匀的(妙啊)。

解释完这个问题 ,我们来看看是怎么扩容的,根据源码,我么可以看到,当所需要的容量超过 原始容量*负载因子(0.75) 时,就需要进行扩容,扩容的大小是之前的两倍。而在扩容的过程中就包含了一个rehash的操作。那么在扩容的时候,会进行transfer也就是将之前的数据进行迁移的操作,遍历所有的元素,并且重新计算哈希值,找到在新表里的索引,把它放进去。这是一个巨坑!!!为了避免高位不同,低位相同,进行了高位与低位的异或操作。

在Java7中的HashMap会有很多问题:

  1. 会碰到死
  2. CVE-2011-1858  TOMCAT邮件组的讨论

对于死锁问题,其实多数是程序员自己的问题,因为HashMap本身就不是线程安全的,当在多个线程中使用hashmap的时候,就必须给他加入同步的环境.

对于TOMCAT邮件组的讨论,是说一个安全问题,如果我们的多个元素映射成同一个哈希值时,会把哈希表退化成一个链表,而链表的查询的时间复杂度的o(n),那么这个查询速度是很可怕的,如果是被黑客利用精心构造的成千上万个元素,具有同样的哈希值,就可以引起Dos攻击,针对这个问题,sun公司提供了一个小补丁,就是如果检查到元素是String的话那么就该用另外一种不同于默认的hash算法来去避免潜在的危险。

此时,针对于这两个问题,我们迎来了Java8之后的HashMap

Java8对于之前的HashMap之前做了哪些改进呢?

  • 由之前数组/链表—>数组/红黑树
  • 扩容时插入顺序的改进
  • 函数方法
    • foreach
    • compute系列
    • merge
    • replace

在Java8的源码中,为什么变成树的阈值是8?我们可以看到对于红黑树的容量服从参数为0.5的泊松分布,大于8的桶中的容量是10万分之一,不易发生碰撞。

在进行put操作时,如果超过阈值,就把桶变为红黑树,如果没超过,还是用链表来实现。

在进行扩容操作时,掌握了java7时的操作,我们可以想到,扩容为二倍,要么索引值和之前一样,要么就是最高位是在之前索引值的基础上再加一个一,就相当于是把原先的变成了两个链表,一个是高位的链表,一个是低位的链表,在把它赋值给新的桶中去。从而缓解了死锁问题(生成环的问题)。

原文 

http://www.cnblogs.com/xiaobaoa/p/11846044.html

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » HashMap源码解析

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址