文档章节

Java HashMap的工作原理 及各种Map区别

 盼望明天
发布于 2015/03/30 16:54
字数 2284
阅读 1288
收藏 0

一、Java HashMap的工作原理

jdk1.7下HashMap数据结构:数组加链表,链表长度没有8的限制;

jdk1.8 HashMap数据结构:数组+链表+红黑树;链表超过8会转存为红黑树;

1.jdk1.8 中HashMap的put工作原理:

1)、对key做null检查。如果key是null,会被存储到table[0],因为null的hash值总是0。

2)、判断当前桶是否为空,空的就需要初始化(resize 中会判断是否进行初始化)

给定的默认容量为 16,负载因子为 0.75。Map 在使用过程中不断的往里面存放数据,当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容,而扩容这个过程涉及到 rehash、复制数据等操作,所以非常消耗性能。

3)、获取key的hashCode值(可以理解为内存地址位置,如:3254239),并对该32位hashCode值进行高低16位的异或运算;得到hash值(如:3812);(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

4)、将获取到的hash值进行一个求模运算(相当于3812%16),得到该key对应的索引位置;if ((p = tab[i = (n - 1) & hash]) == null);该位置肯定不会超过16位;

5)、根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空,为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。

6)、如果当前桶有值( Hash 冲突),那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等,相等就赋值给 e,在第 8 步的时候会统一进行赋值及返回。

7)、如果当前桶为红黑树,那就要按照红黑树的方式写入数据。

8)、如果是个链表,就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面(形成链表)。

9)、接着判断当前链表的大小是否大于预设的阈值,大于时就要转换为红黑树。

10)、如果在遍历过程中找到 key 相同时直接退出遍历。

11)、如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。

12)、最后判断是否需要进行扩容。

2.jdk1.8 中HashMap的get工作原理:
1)、计算hash部分跟put相同;

2)、首先将 key hash 之后取得所定位的桶。

3)、如果桶为空则直接返回 null 。

4)、否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key,是就直接返回 value。

5)、如果第一个不匹配,则判断它的下一个是红黑树还是链表。

6)、红黑树就按照树的查找方式返回值。

7)、不然就按照链表的方式遍历匹配返回值。

问题1:HashMap为何要进行hash计算?hash函数是怎么运算的?

尽量让node落点分布均匀,减少碰撞的一个概率,如果碰撞概率高了,就势必导致数组下标下的链表长度太长;

运算方式:将获取到的32位hash值,分成高16位和低16位,再将高16位移到低16位进行异或运算; 

32位:3254239,通过异或运算后,3812,

table[3812]越界,再做个求模运算3812%16=,一定不会超过16位;hash%n===(n-1)&hash,速度快,效率高;
问题2:数组扩容,2倍扩容;为什么是2的N次幂;就是因为hash算法这(n-1)&hash;要符合这算法;必须是这样;

resize()方法中的扩容:newThr = oldThr << 1; // double threshold

问题3:但是 HashMap 原有的问题也都存在,比如在并发场景下使用时容易出现死循环。

HashMap 扩容的时候会调用 resize() 方法,就是这里的并发操作容易在一个桶上形成环形链表;这样当获取一个不存在的 key 时,计算出的 index 正好是环形链表的下标就会出现死循环。

 


二、Hashtable、LinkedHashMap、TreeMap、SortedMap、WeakHashMap、IdentityHashMap、ConcurrentHashMap的区别:
(1) HashMap与HashTable的区别:
a.Hashtable中的对象是线程安全的。而HashMap则是异步的,因此HashMap中的对象并不是线程安全的。因为同步的要求会影响执行的效率,所以如果你不需要线程安全的集合那么使用

HashMap是一个很好的选择,这样可以避免由于同步带来的不必要的性能开销,从而提高效率。
b.值:HashMap可以让你将空值作为一个表的条目的key或value,但是Hashtable是不能放入空值的。HashMap最多只有一个key值为null,但可以有无数多个value值为null。
注意:
1、用作key的对象必须实现hashCode和equals方法。
2、不能保证其中的键值对的顺序
3、尽量不要使用可变对象作为它们的key值。
(2) LinkedHashMap:
     它的父类是HashMap,使用双向链表来维护键值对的次序,迭代顺序与键值对的插入顺序保持一致。LinkedHashMap需要维护元素的插入顺序,插入性能略低于HashMap,但在迭代访问元

素时有很好的性能,因为它是以链表来维护内部顺序。
(3) TreeMap和SortedMap:
Map接口派生了一个SortMap子接口,SortMap的实现类为TreeMap。TreeMap也是基于红黑树对所有的key进行排序,有两种排序方式:自然排序和定制排序。HashMap通常比TreeMap快一点(树

和哈希表的数据结构使然),建议多使用HashMap,在需要排序的Map时候才用TreeMap。
(4) WeakHashMap:
 WeakHashMap与HashMap的用法基本相同,区别在于:后者的key保留对象的强引用,即只要HashMap对象不被销毁,其对象所有key所引用的对象不会被垃圾回收;WeakHashMap适合短时间内就过期的缓存时最好使用weakHashMap,它包含了一个自动调用的方法expungeStaleEntries,这样就会在值被引用后直接执行这个隐含的方法,将不用的键清除掉。
(5) IdentityHashMap类:
IdentityHashMap与HashMap基本相似,只是当两个key严格相等时,即key1==key2时,它才认为两个key是相等的 。IdentityHashMap也允许使用null,但不保证键值对之间的顺序。
(6) EnumMap类:
1、EnumMap中所有key都必须是单个枚举类的枚举值,创建EnumMap时必须显示或隐式指定它对应的枚举类。
2、EnumMap根据key的自然顺序,即枚举值在枚举类中定义的顺序,来维护键值对的次序。
3、EnumMap不允许使用null作为key值,但value可以。
(7) ConcurrentHashMap:
1.ConcurrentHashMap对整个桶数组进行了分段,而HashMap则没有
2.ConcurrentHashMap在每一个分段上都用锁进行保护,从而让锁的粒度更精细一些,并发性能更好,而HashMap没有锁机制,不是线程安全的。

ConcurrentHashMap如何进行扩容的?

当往hashMap中成功插入一个key/value节点时,有可能触发扩容动作:

1、如果新增节点之后,所在链表的元素个数达到了阈值 8,则会调用treeifyBin方法把链表转换成红黑树,不过在结构转换之前,会对数组长度进行判断

如果数组长度n小于阈值MIN_TREEIFY_CAPACITY,默认是64,则会调用tryPresize方法把数组长度扩大到原来的两倍,并触发transfer方法,重新调整节点的位置。

2、新增节点之后,会调用addCount方法记录元素个数,并检查是否需要进行扩容,当数组元素个数达到阈值时,会触发transfer方法,重新调整节点的位置。


三、红黑树的理解?
红黑树是一种自平衡二叉查找树,红黑树是一种很有意思的平衡检索树;每次插入的时候都要进行计算,保证二叉树的平衡;如果有2的N次方数据量级,查询的时候只需要查询N次即可。
我们对任何有效的红黑树加以如下增补要求:
        1.节点是红色或黑色。
        2.根是黑色。
        3.所有叶子(外部节点)都是黑色。
        4.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
        5.从每个叶子到根的所有路径都包含相同数目的黑色节点。
 这些约束强制了红黑树的关键属性: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。

© 著作权归作者所有

上一篇: 多线程并发编程
下一篇: Redis技术
粉丝 7
博文 103
码字总数 174582
作品 0
广州
私信 提问
2018年Android面试题含答案--适合中高级(上)

文章转载自:http://www.pythonheidong.com/blog/article/3339/ 这些面试题是我在今年年初换工作的时候整理,没有重点。包括java基础,数据结构,网络,Android相关等等。适合中高级工程师。由...

雄霸天下-无人能挡
08/15
0
0
HashMap和Hashtable的区别

HashMap和Hashtable的比较是Java面试中的常见问题,用来考验程序员是否能够正确使用集合类以及是否可以随机应变使用多种思路解决问题。HashMap的工作原理、ArrayList与Vector的比较以及这个问...

LCZ777
2014/03/29
96
0
分享一份非常强势的Android面试题

马上步入金九银十了,是时候看一些面试题去鹅厂了,接下来我将分享一些面试题,每天总结一点点,希望对大家有所帮助! ListView和RecyclerView区别 参考链接: blog.csdn.net/shu_lance/a… ...

codeGoogle
2018/08/23
0
0
BATJ等大厂最全经典面试题分享

金九银十,又到了面试求职高峰期,最近有很多网友都在求大厂面试题。正好我之前电脑里面有这方面的整理,于是就发上来分享给大家。 这些题目是网友去百度、蚂蚁金服、小米、乐视、美团、58、...

老道士
2018/09/26
158
0
Java 面试题:百度前200页都在这里了

基本概念 操作系统中 heap 和 stack 的区别 什么是基于注解的切面实现 什么是 对象/关系 映射集成模块 什么是 Java 的反射机制 什么是 ACID BS与CS的联系与区别 Cookie 和 Session的区别 fa...

Java红茶
2017/11/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

开发中常用的正则表达式

为了能够更好地理解如何在C#环境中使用正则表达式,这里整理了一些常用的正则表达式: 罗马数字: string p1 = "^m*(d?c{0,3}|c[dm])" + "(l?x{0,3}|x[lc])(v?i{0,3}|i[vx])$";string t1 ......

木庄
29分钟前
4
0
【.NET程序打包】VS2019使用Installer Projects打包

C#—使用Installer Projects打包桌面应用程序 前言 打包桌面应用程序实在是一个不常使用的东西,偶尔使用起来经常会忘东忘西的耽误时间,因此,这篇文章多以图片记录过程,也是用于备忘。 下...

_Somuns
33分钟前
4
0
自定义注解,使用动态代理解决网站的字符集编码问题

第1章设置环境 安装操作系统,安装备份(镜像): JDK: 设置环境变量Eclipse:解压即可 Eclipse自身解压目录不包括中文 代码工作空间目录不包括中文Tomcat:解压不要包含中文目录M...

蓝来杯往
38分钟前
6
0
Solr中的字段类型field type

Solr含有多种字段类型,可用的字段类型基本都定义在了包org.apache.solr.schema中,列举如下: 类 说明 BinaryField 二进制数据 BoolField 布尔值,其中’t’/’T’/’1’都是true Collatio...

gantaos
52分钟前
4
0
《JAVA核心知识》学习笔记 (21. JAVA 算法)

21. JAVA 算法

Shingfi
59分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部