HashMap底层实现原理(站在巨人的肩膀上)

1.前言

一言以蔽之，底层是数组加单向链表，链表的数组，在了解hashMap以前，先了解常用的数组和链表底层原理

1.1 ArrayList :

底层是数组，数组属于顺序存储，内存空间连续根据下标随机访问数组元素的效率高，向数组尾部添加元素的效率高；但是，删除数组中的数据以及向数组中间添加数据效率低，因为需要移动数组元素。顺序存储可以想象成吃饭排队，每个人领的号都是按顺序来的，服务员只要喊号就里立即可以找到对应的人，新来的人都自动加到队尾，如果有人想插队，那么从他插队的位置后面所有的人都要挪动位置；查询速度快。

1.2 LinkedList：

底层是双向链表，内存空间不连续， 每个元素都有一个前指针和后指针，linledList在获取任何一个数据的时候，都要把前面的数据或后面的数据都遍历一遍；插入和删除某个元素的时候，直接移动指针就行；插入、删除速度快。

2.HashMap:

HashMap底层使用数组加（链表或红黑树）的结构完美的解决了数组和链表的问题，使得查询和插入，删除的效率都很高。

2.1  HashMap的put方法

HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，HashMap的基础就是一个线性数组。hashmap在存数据的时候是基于hashing的原理，当我们调用put(key,value)方法的时候，其实我们会先对键key调用key.hashcode()方法，根据方法返回的hashcode来找到bucket的位置来存Entry对象，如果hashcode不存在，则直接存储；如果hashcode已存在，那么它们对应的bucket显然也是相同的，这个时候就会产生所谓的碰撞（hashmap的底层存储结构是 数组+链表）。每个bucket索引对应一个链表，这个时候系统就会找到对应的链表,最新的元素放到链表头。根据hashcode找到对应的bucket之后，还会在对应的链表逐一检查这个链表里有没存在相同的key对象，这个时候是通过equals这个方法来对比的。如果有，者用新的value取代旧的value。如果没有，则向楼上说的，在链表的尾部加上这个新的Entry对象

2.2  HashMap的get方法

这个操作的原理就比较简单,只需要根据key的hashcode算出元素在数组中的下标,之后遍历Entry对象链表,直到找到元素为止。

2.3 HashMap的扩容

HashMap中的两个重要的参数：HashMap中有两个重要的参数：初始容量大小和加载因子，初始容量大小是创建时给数组分配的容量大小，默认值为16，用数组容量大小乘以加载因子得到一个值，一旦数组中存储的元素个数超过该值就会调用rehash方法将数组容量增加到原来的两倍，专业术语叫做扩容。由于数组是定长的，当数组储存过多的结点时，发生碰撞的概率大大增加，此时hash表退化成链表。

在做扩容的时候会生成一个新的数组，原来的所有数据需要重新计算哈希码值重新分配到新的数组，所以扩容的操作非常消耗性能.

创建HashMap时我们可以通过合理的设置初始容量大小来达到尽量少的扩容的目的。加载因子也可以设置，但是除非特殊情况不建议设置.

站在巨人的肩膀上，参考资料：

https://baijiahao.baidu.com/s?id=1611209814188127596&wfr=spider&for=pc