一张思维导图带你梳理HashMap相关知识

HashMap可以说是java中最常见也是最重要的key-value存储结构类,很多程序员可能经常用,但是不一定清楚这个类背后的数据结构和相关操作原理,为了复习HashMap相关的知识,今天花了一天的时间整理了下有关该类的相关知识,个人认为基本上涵盖了HashMap相关的知识点,希望对大家有所帮助。

一张思维导图带你梳理HashMap相关知识

一张思维导图带你梳理HashMap相关知识

为了让大家看得更清楚,把图片的内容也放在这里。

1、基本概念

size:key-value键值对的数量

capacity:Entry数组的大小,默认16

loadfactor:负载因子,默认0.75,基于性能和空间的tradeoff,当太大时,会导致冲突变多,影响查询性能,太小时,会占用较多空间,导致浪费

threshold:极限容量,数组扩容时的临界值,capacity*loadFactor>threshold时,会自动扩容

Entry:map中数组存储的对象,遍历Map时就是基于Entry进行遍历的

Bucket:桶,map中一个Entry位置下对应的一个链表,类似于一个坑,相同hashcode的键值对以链表的形式存在一个bucket里

modcount:修改计数,当HashMap中的元素个数发生改变时,该值就会+1,如果该值和expectedModCount不一致,会触发fast-fail机制,抛出ConcurrentModifycationException异常

2、数据结构

jdk7之前(含jdk7):数组+链表

jdk8开始:数组+链表|红黑树(当链表中元素超过8个时,会由链表自动转为红黑树)

3、重要特性

1、非线程安全,对应HashTable是线程安全的,因为加了synchronized关键字

2、无序,因为hash函数会打乱顺序,并且resize后不保证在新数组中的位置和原数组中位置一致,但是会在原来位置+2^n位置

3、允许key和value均为null,当key为null时,存在entry[0]所在的链表里

4、重要方法

equals方法: Object类定义的方法,具体介绍参考面hash方法。如果两个对象根据equals()方法相等,则hashcode一定相等,反过来如果hashcode相同,则equals不一定相等。重写equals方法需要满足5个特性

1、自反性:x.equals(x)永远返回true

2、对称性:如果x.equals(y)为true,则y.equals(x)也为true

3、传递性:如果x.equals(y)为true,y.equals(z)为true,则x.equals(z)也为true

4、幂等性:如果对象没被改变,那么不管调用多少次,x.equal(y)的结果永远相同

5、非空性:如果x非空,则x.equals(null) 永远为false

hash方法:Object类定义的方法,用于计算key的hashCode,默认是一个对象在JVM内存地址的哈希值。当需要比较对象的值而不是对象本身时,通常需要重写hash方法和equals方法,因为默认的equals方法比较的是对象在jvm内存地址的值,如果只重写hash        方法,那么equals方法比较的其实是2个对象的堆地址;反过来,如果只重写equals方法,那么相同对象的hashcode可能不一致,也会导致比较结果不正确

indexFor方法:计算hashCode在entry数组中的位置,用了个很巧妙的算法h = h&(table.length -1 ),后面会解释为什么每次resize的时候,都是原来的2倍

put方法:put方法先判断key是否为null,如果为null,则调用putForNullKey方法(jdk8之前),否则按下面思路执行put操作:

1、先根据hashCode方法计算该对象的key的hashCode

2、通过indexFor方法计算key的hashCode在entry数组中的下标位置

3、如果该下标处为null,则把该对象存入该节点

4、如果该下标处不为null,则遍历该链表,根据equals方法寻找是否有对应的key,如果有,则替换旧的值,否则将该对象添加到链表的头部

addEntry方法:添加Entry对象的方法,添加之前会先判断是否需要resize扩容,扩容的条件有2个:键值对数量>=极限容量,并且存放该对象的buckey的值非空(也就是有冲突了),假如有极限容量是12,map中有13个键值对,但是这13个键值对都存在table          数组的13个bucket里,那么也不会扩容的

resize方法:当达到扩容条件时调用的方法

1、当极限容量已经达到最大值2^32-1时,不再扩容

2、如果未达到,则首先创建一个新的数组(容量为原来数组的2倍)

如果初始化Map容量的时候不是2的n此方,会生效吗?

不会的,因为hash会找一个比该值大的最小2的n此次方的值,比如指定了初始容量为12,则默认的数组大小为16

为什么是2倍?2个原因:

1、位移运算速度快。

2、每次将对象转移到新的数组时(即调用indexFor函数时),由于采用的是hash&(length-1),既能减少冲突,又能保证速度,所以每次扩容都是原来的2倍。

3、遍历map,计算原来的数组中每个键值对在新数组中的index,再将其存到新数组中相应位置

remove方法:与put操作基本相反,将对象从Map中移除,需注意fast-fail问题,对应的解决办法是:采用迭代器本身的remove方法,而不要采用hashMap的remove方法

总的来说,hashMap是一个设计非常巧妙的类,光看源码有一定的复杂度,尤其是不同版本的jdk对应的方法可能有较大差异,如果有什么地方讲的不正确,欢迎指出。

Linux公社的RSS地址: https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址: https://www.linuxidc.com/Linux/2018-07/153060.htm

原文 

https://www.linuxidc.com/Linux/2018-07/153060.htm

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

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

转载请注明原文出处:Harries Blog™ » 一张思维导图带你梳理HashMap相关知识

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

评论 0

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