⭐️前面的话⭐️
本篇文章将介绍Java中HashMap的底层实现原理,有关HashMap为数组开辟内存的时期,默认的容量,默认负载因子,树化的条件,HashMap的扩容机制,put方法的过程以及HashMap中的哈希函数。
小贴士:博主推荐->学习面试刷题必用工具
📒博客主页:未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创,CSDN首发!
📆首发时间:🌴2022年8月14日🌴
✉️坚持和努力一定能换来诗与远方!
💭推荐书籍:📚《数据结构》,📚《算法导论》
💬参考在线编程网站:🌐牛客网🌐力扣
博主的码云gitee,平常博主写的程序代码都在里面。
博主的github,平常博主写的程序代码都在里面。
🍭作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!
📌导航小助手📌
- 1.HashMap以及HashMap的基本原理
-
- 1.1什么是HashMap?
- 1.2HashMap的属性
- 1.3HashMap的构造方法
- 1.4HashMap开辟数组的时机
- 1.5HashMap中的put
- 1.6HashMap中的哈希函数
- 1.7HashMap的扩容机制
- 2.HashSet的基本实现原理
- 3.有关HashMap其他的面试题
-
- 3.1HashMap是否是线程安全的?有没有线程安全的"HashMap"?
- 3.2HashMap有什么特点?
注意事项:博主安利一款刷题面试的神器,如果有小伙伴还没有注册牛客,可以点击下方链接进行注册,注册完就能立即刷题了。不仅是刷题,上面还有很多有关就业的面经,面试题库,以及名企的模拟面试,我非常推荐它,博主自己用的也很多,也刷了不少题了!下图可以作证:
注册地址:牛客网
有关任何问题都可以与博主交流,你可以在评论区留言,也可以私信我,更可以加上博主的vx与博主一对一交流(文章最下方有)。
1.HashMap以及HashMap的基本原理
1.1什么是HashMap?
HashMap是Java集合框架中Map容器的一个实现类,它的底层是使用哈希表实现的,更加具体地说在jdk7中采用数组+链表实现,在jdk8中采用数组+链表+红黑树实现。
Map代表具有映射关系(key-value)的集合,其所有的key是一个Set集合(key值不能重复),即key无序且不能重复,而HashMap就是Map接口下的一个实现类,HashMap是一个储存键值对(EntrySet)的集合,并且支持储存key/value为null
的元素。
下面我们基于jdk8来说一说HashMap的基本原理。
1.2HashMap的属性
HashMap对象被构造时,初始的默认容量为1<<4
,也就是16
,并且必须是2的幂(这与哈希函数有关)。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
HashMap最大的容量为1<<30
,也就是
2
30
2^{30}
230。
static final int MAXIMUM_CAPACITY = 1 << 30;
HashMap默认的负载因子为0.75
。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
链表树化的最小链表大小阈值8
,当HashMap中数组大于64
,数组所挂链表的大小超过8
才会将数组所挂的链表转换为红黑树。
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
红黑树链表化的的阈值是6
,当红黑树结点个数小于6
时,就会转换为链表。
static final int UNTREEIFY_THRESHOLD = 6;
HashMap底层的数组,是一个链表数组:
transient Node<K,V>[] table;
元素个数阈值,当HashMap的size大于threshold时会执行resize操作,threshold=capacity*loadFactor
,其中capacity表示数组的容量。
int threshold;
1.3HashMap的构造方法
HashMap最常用的构造方法,一个是无参的构造方法,使用无参构造方法构造HashMap时,默认的构造容量是16
,但是此时不会真的去申请一个大小为16
的数组,还有一个指定容量的构造方法也是如此,并且所取容量为大于或等于指定容量的一个最接近的2次幂数,日指定容量为19
,那实际数组容量为32
。
源码:
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
除此之外,还有指定容量和负载因子的构造方法,其中tableSizeFor(initialCapacity)
方法会生成比initialCapacity
大并最接近initialCapacity
的一个2
次幂。
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
从源码可以看出其实在使用以上三种构造方法进行对象构造的时候,并没有为数组分配空间,只是确定负载因子,容量等属性。
最后还有一个根据其他的Map对象构造HashMap的构造方法,使用这种方式构造,只要传入的参数有元素,那么数组空间肯定已经申请好了,否则也是没有去申请的。
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
所以我们可以得到一个结论:当HashMap对象创建时,内部的数组并没有分配内存。
1.4HashMap开辟数组的时机
真正为数组分配内存是在第一次put
操作的时候,其中源码如下:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
意思就是通过哈希函数hash
生成对应数组的下标值,找到对应的位置进制插入。
如果是第一次插入,就会对链表数组进行扩容,也是正式地为数组初始化:
我们就不继续深入看了,在resize方法中,会为数组分配内存,并且大小为2的幂,至于为什么是这个值,这与HashMap中的哈希函数有关。
1.5HashMap中的put
如果是首次扩容,先判断数组是否为空,若数组为空则进行第一次扩容(resize),会为HashMap对象申请一个默认容量大小16
的数组。
第一步,通过hash()方法计算索引,通过hash算法,计算键值对在数组中的索引,并通过索引找到在数组中的位置。
第二步,插入数据,分以下几种情况:
- 如果当前位置元素为空,则直接插入数据;
- 如果当前位置元素非空,遍历链表或红黑树,如果key已存在,则直接覆盖其value;
- 如果当前位置元素非空,遍历链表或红黑树,如果key不存在,则将数据链尾插(jdk7是头插)到链表;
- 若链表长度达到8,并且HashMap中的
table
数组大小达到64
,则将链表转换成红黑树,并将数据插入树中,如果链表长度达到8
但是table
数组大小没有64
则将数组扩容;
第三步,检查存储的元素个数,如果超过阈值threshold
,则扩容。这一步其实也就是检查负载因子是否超过默认值,超过就扩容。
1.6HashMap中的哈希函数
前面我们说到了hash方法,HashMap中的hash方法是与我们直接根据key
生成hashCode值再取模的方式不同,在HashMap中的hash算法中,首先会key
计算出hashCode值,然后再将hashCode值与右移16
为的hashCode值进行按位异或操作,得到一个新的哈希值,这样做的目的其实就是为了增强哈希值的随机性,这个方法也叫做“扰动方法”。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
在进行put等需要找到某个key
所对应的数组索引的时候,HashMap不是通过直接取数组长度的模来得到对应的下标,取而代之的是使用按位与&
运算来进行下标的计算,毕竟位运算的效率是大于取模%
操作的。假设HashMap底层数组table
的长度为length
,不妨记n=length-1
,key
对应的哈希值为h
。
在jdk8源码中,使用h&(n-1)
来获取对应table
数组的索引(下标),这也解释了为什么HashMap当中的数组长度一定是2
的幂。
因为使用2
的幂再减去一个1
,得到的数n
它的所有有效二进制位均为1
,如64
的二进制数为1000000
,减去1
得到n
,它的值为0111111
,数组的长度的二进制有效位是7
位,因为数组长度是二的幂,数组下标最大下标有效位一定是6
位,并且全为1
,我们知道0
与任何数按位与得到的均为0
,而1
与任何数运算得到的结果可能是1
也可能是0
,这就保证了在使用&
操作时,每一位有效位的值都有可能是0
或1
,进一步就保证了数组table
的所有下标均有可能被映射到,反之如果存在含有0
的二进制有效位,则那一位按位与的操作结果一定是0
,这样的话,一定存在数组table
中某些下标无法被映射,增大了哈希冲突的可能性。
做个小总结,HashMap中计算的哈希值是通过hashCode值与右移16位hashCode值按位异或的结果,这个目的就是为了增强哈希值的随机性。HashMap确定索引的方法是将n&h
,毕竟按位与的效率大于取模,为了数组每个下标都可能被映射到,则n
的每一位二进制有效位均得为1
,所以数组的长度必须为2
的幂,因为只有2
的幂减1
得到的有效二进制位均为1
。
其中n
表示数组长度减去一个1
,h
表示通过hash方法得到的哈希值。
1.7HashMap的扩容机制
HashMap中table
数组初始默认大小为16
,根据上述对hash方法的分析,数组table
长度一定得是2
的幂,从这里就不难猜出,HashMap极有可能是2
倍扩容,毕竟2
倍扩容比较合理,并且它能够保证扩容后的数组大小也是2
的幂。
在jdk8中,HashMap的扩容,确实是采用了2
倍扩容。
当HashMap对象中元素个数size
大于threshold
或者数组为null
时会触发扩容resize
。
为了解决哈希冲突,jdk8采用了数组+链表+红黑树的方式实现,当数组中某链表的长度大于8
,并且数组table
的长度达到64
,就会将链表转换为红黑树来提高效率,当数组中某链表长度大于8
但是数组table
长度没有达到64
,此时就会进行扩容。
当红黑树结点个数小于6
时,就会将红黑树转换回链表。
在扩容的时候,会将所有的元素遍历,全部重新计算哈希值并全部重新确定在数组中的位置。
2.HashSet的基本实现原理
HashSet是基于HashMap实现的,默认构造函数是构建一个初始容量为16,负载因子为0.75 的HashMap。它封装了一个 HashMap 对象来存储所有的集合元素,所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存,而 HashMap 的 value 则存储了一个 PRESENT,它是一个静态的 Object 对象。
3.有关HashMap其他的面试题
3.1HashMap是否是线程安全的?有没有线程安全的"HashMap"?
HashMap不能保证线程安全,因为在并发的情况下进行put
操作,可能会导致数组中链表死循环。
线程安全的“HashMap”有HashTable,它相比于HashMap,给关键的方法加上了锁,那么给方法加锁本质上就是给对象加锁,那么每种操作都需要拿对象锁,这样会造成激烈的锁竞争。
相比于HashTable,更推荐使用CurrentHashMap,在jdk7中,它是给每一个数组中的元素都加上了锁,或者说创建了一个新的数组Segment
,这个数组用于实现加锁操作,每个 Segment 里包含一个 HashEntry 数组,Segment 中元素的结构和 HashMap 类似,是一个数组和链表结构。
在jdk8中,已经摒弃了 Segment 的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 Synchronized 和 CAS 来操作,整个看起来就像是优化过且线程安全的 HashMap,简单说,在HashMap的基础上,就是给每个数组中的元素加锁,来保证线程安全,并且由于每个数组元素都有锁,所以相比于HashTable锁竞争的激烈程度小得多。
3.2HashMap有什么特点?
- HashMap是线程不安全的,支持序列化。
- HashMap可以使用null作为key或value。
- HashMap查找的效率可达到O(1)。
- HashMap遍历方式比较单一,主要使用EntrySet 和 KeySet进行遍历,遍历方式有增强for循环和迭代器。
- HashMap是Map容器的一种实现,是无序的键值对集合。
下期预告:反射枚举lambda表达式
到文章最后,再来安利一下吧,博主也是经常使用,并且也经常在牛客上刷题,题库也非常丰富:学习,刷题,面试,内推都有。也欢迎与博主交流有关刷题,技术方面,以及与博主聊聊天,交个朋友也好啊,毕竟有朋自远方来!
觉得文章写得不错的老铁们,点赞评论关注走一波!谢谢啦!