<返回更多

当我们创建HashMap时,底层到底做了什么?

2020-06-28    
加入收藏

jdk1.7中的底层实现过程(底层基于数组+链表)

在我们new HashMap()时,底层创建了默认长度为16的一维数组Entry[ ] table。当我们调用map.put(key1,value1)方法向HashMap里添加数据的时候:

首先,调用key1所在类的hashCode()计算key1的哈希值,通过key1的hash值与数组的最大索引进行位运算以后,得到了在 Entry数组中的存放位置:

如果此位置上的数据为空,此时的key1-value1添加成功。

如果此位置上的数据不为空(意味着此位置已经存在一个或多个数据),比较key1和已经存在的一个或多个数据的哈希值:

如果key1的哈希值与已经存在的数据的哈希值都不相同,此时key1-value1添加成功。

如果key1的哈希值与已经存在的数据的某一个数据的哈希值相同,继续比较:调用key1所在类的equals()方法:

如果equals()返回false,此时key1-value1添加成功;

如果equals()返回true,使用value1替换value2。

需要注意的是,若原来位置已有数据,则此时key1-value1和原来的数据以链表的方式存储。

在不断的添加过程中,会涉及到扩容问题,当数组容量大于数组现有长度乘以加载因子(如16*0.75,默认的加载因子为0.75)的时候,就会进行数组扩容,以减少哈希冲突(哈希冲突是指哈希函数算出来的地址被别的元素占用了),提高查询效率。默认的扩容方式,扩容为原来容量的2倍,并将原有的数据复制过来。

当我们创建HashMap时,底层到底做了什么?

 

jdk1.8的底层实现过程(底层基于数组+链表+红黑树)

jdk1.8与jdk1.7中底层的创建过程相似,但有不同,首先,new HashMap()底层没有创建出一个长度为16的数组,在调用put()方法时,判断数组是否存在,如果不存在创建长度为16的Node[ ]数组。接下来的过程与jdk1.7相似。最后,当某一个索引位置上的元素以链表形式存在的数据个数>8且当前数组的长度>64时,此时此索引位置上的所有数据改为使用红黑树存储。

在jdk1.7中,即使在“数组容量大于数组现有长度乘以加载因子”时扩容,也不可避免地会有哈希冲突存在,因此,在jdk1.8中引入红黑树是为了进一步减少哈希冲突,提高查询效率。

红黑树是一种自平衡的二叉查找树,是一种数据结构,典型的用途是实现关联数组。根节点必须是黑色,其他每个节点要么是红色,要么是黑色。

结论:HashMap键是不能重复的,去除重复的条件是依赖键的hashCode方法和equals方法,如果键是自己的对象类型,必须要重写hashCode方法和equals方法,否则,不能去除重复的键。

声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多资讯 >>>