一张思维导图带你梳理HashMap相关知识-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

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

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

         HashMap可以说是java中最常见也是最重要的key-value存储结构类,很多程序员可能经常用,但是不一定清楚这个类背后的数据结构和相关操作原理,为了复习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方法 

5、和其他集合类的区别

       HashTable:

              1、HashTable线程安全,因为put和remove方法里加了synchronized关键字

2、HashTable中的key和value都不能为null,hashMap可以

3、性能上,由于HashMap非线程安全,因此速度更高

4、HashMap继承自AbstractMap,HashTable继承自Dictionary

5、其他各方面区别不大,包括数据结构,存取方法等

       TreeMap:1、HashMap无序,TreeMap基于红黑树实现,是有序的

        总的来说,hashMap是一个设计非常巧妙的类,光看源码有一定的复杂度,尤其是不同版本的jdk对应的方法可能有较大差异,如果有什么地方讲的不正确,欢迎指出。有需要思维导图原图的可以给我留言,我发给你。

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章
最新文章
相关文章