HashMap的底层实现

HashMap

众所周知,HashMap是一种以Key-value形式表现的容器,在java日常开发中非常常见,使用频率很高,但是究其底部原理,本人其实并不太了解,因此写此文章探讨一下。

实现原理

当我们对HashMap进行put的时候,首先会通过hashCode()方法计算出key的hash值,然后再用这个hash值去找在HashMap中对应的位置,如果对应位置为空,那么就直接存储进去了,如果不为空,则会调用equals()方法判断此位置上存储的key和想要存的key是否重复(equals()方法的工作原理是判断对象的值是否相等,即所存内存空间上的值是否相等),如果相等则直接结束,如果不相等,则会以链表的形式存储,当链表长度大于8且HashMap长度大于64时,会将链表改为红黑树的形式存储。

存储形式

HashMap的存储形式是一个位桶数组数组Node<K,V>[],Node可以理解为我们平时使用的Entry,它实现了Entry接口,Node中存储了对象的hash、key和value,当对HashMap进行getValue()操作时,首先会用key计算出hash值,然后在HashMap中找到对应的位置,判断此位置上的对象的key和手上的key是否相等,如果不相等,则遍历链表,直到找到相等的key或者全部遍历结束为止。

负载因子

HashMap默认的负载因子是0.75,即当容器填满了75%容量的时候,就会创建一个容量是原来两倍的新容器,并将原来容器中的对象放入新容器中。

HashMap的key有什么必要条件

  1. 遵守equals()方法和hashCode()方法。
  2. 是不可变的,即在put()以后就不会再改变了。

HashMap不适用于多线程

HashMap不建议在多线程下使用,多线程建议使用ConcurrentHashmap。

因为HashMap存在扩容机制,在多线程条件下,可能会产生循环链的情况,即线程A和B都发现HashMap需要扩容了,同时进行扩容,但是由于扩容的进度不一致,可能会导致循环链的情况,从而导致get()死锁。

  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!

请我喝杯咖啡吧~

支付宝
微信