大家先看下这张图片:
1、HashMap是基于哈希表实现的,而哈希表的底层是数组加上链表的形式。
2、数组内存连续查询效率高,链表内存分散增删改效率高,哈希表采用此种存储数据的形式极大的提高操作数据的效率。
3、哈希表的默认长度是16,编号从0开始。图中编号0-4的长方形代表了一个数组,箭头指向的代表了一个一个的链表。
HashMap存储数据原理
1、用HashMap存储数据( put(key,value) )时,会先操作key调用.hashcode()方法得出hash值,然后再通过哈希算法转换成数组的一个下标,对应的就是在数组上的的存储位置。
2、如果该位置没有数据,则直接存储。如果该位置有数据,则会发生数据碰撞。
3、数据碰撞的时候遍历该位置上链表中的所有数据,并且通过equals()方法来比对每个数据的key。如果key相同的话,会将链表上该位置的数据进行覆盖。如果key不相同的话,在JDK1.8之前是实行的头插法,数据存储在链表头部,1.8之后实行的是尾插法数据存储在链表尾部。
4、JDK1.8之后,当链表上的节点个数(数据个数)大于等于8时并且数组长度不小于64的时候,链表数据结构自动进行树化转化成红黑树,当链表上的数据小于8个时,又会自动退化成链表
5、如果数组的长度小于64的话链表数据个数达到了8的话也不会转化成红黑树,而是先进行扩容,直到数组长度达到64
6、HashMap默认的数组长度是16,扩容的话有两种情况:
1)一种是数组上的元素达到了阈值,16*默认负载因子0.75,也就是12个元素的时候,数组长度扩容为两倍32,阈值变为24
2)还有一种是在没有红黑树的情况下,添加元素后数组中某个链表的长度超过了8,数组会扩容为两倍(比如创建HashMap集合后刚开始添加元素全都在一个链表中,当链表长度是9的时候数组扩容成32,链表长度是10的时候数组扩容成64,此时再添加元素,满足了数组长度为64链表长度到达8的两个条件,链表转换成红黑树)
如果觉得《HashMap底层原理(图文并茂 简单易懂)》对你有帮助,请点赞、收藏,并留下你的观点哦!