hashMap的实现原理

时间:2020-9-16 作者:admin

HashMap的实现原理

HashMap的数据结构

在看Hashmap的数据结构之前先来看看数组和链表的特点
数组:寻址容易插入和删除的时候比较困难(数组有下表寻址,但是插入删除的时候下表要移动,扩容的时候也很麻烦)
链表:寻址困难,插入和删除容易,元素的指针指向下一个元素,在插入删除的时候只需要对指针进行操作就好

然而HashMap就是二者的结合,我们可以发现哈希表是由数组+链表组成的如下图
hashMap的实现原理
​ JDK1.8之前,哈希表底层采用数组+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。
​ JDK1.8中,哈希表存储采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。如下图(画的不好看,只是表达一个意思。):
hashMap的实现原理
​ 1,进行键值对存储时,先通过hashCode()计算出键key的哈希值,然后再数组中查询,如果没有则保存。
​ 2,但是如果找到相同的哈希值,那么接着调用equals方法判断它们的值是否相同。仅当满足以上两种条件才能认定为相同的数据,因此对于Java中的包装类里面都重写了hashCode()和equals()方法。
​ JDK1.8引入红黑树大程度优化了HashMap的性能,根据对象的hashCode和equals方法来决定的。如果我们往集合中存放自定义的对象,那么保证其唯一,就必须复写hashCode和equals方法建立属于当前对象的比较方式。(可以自定义排序方法)
HashMap<K,V>:存储数据采用的哈希表结构,元素的存取顺序不能保证一致。由于要保证键的唯一、不重复,需要重写键的hashCode()方法、equals()方法。另外Map接口中的集合都有两个泛型变量<K,V>,在使用时,要为两个泛型变量赋予数据类型。两个泛型变量<K,V>的数据类型可以相同,也可以不同

主要方法

hashMap的实现原理

HashMap源码查看

hashMap的实现原理
进入put方法
hashMap的实现原理
人后在进入putVal方法
hashMap的实现原理
然后进入resize()方法
hashMap的实现原理
hashMap的实现原理
这个值是16
所以当存入一组键值对的时候,先对key进行hash,然后映射到一个初始化长度为16的数组上。
进入HashMap<>();
hashMap的实现原理
会发现创建一个初始化数组长度为16,负载因子0.75
hashMap的实现原理
负载因子0.75
hashMap的实现原理
负载因子:在HashMap的底层存在着一个名字为table的Entry数组,在实例化HashMap的时候,会输入两个参数,一个是 int initCapacity(初始化数组大小,默认值是16),一个是float loadFactor(负载因子,默认值是0.75),首先会根据initCapacity计算出一个大于或者等于initCapacity且为2的幂的值capacity,例如initCapacity为15,那么capacity就会为16,还会算出一个临界值threshold,也就是capacity * loadFactor,贴出源代hashMap的实现原理

第一次读源码,有错误请指出!感觉应该不是很对!哈哈哈哈

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。