HashMap底层原理探析

在java1.8之前，HashMap底层实现中未使用到hash表去进行存储，这样存在着很多效率方便的问题。

原本没有使用hash表的时候，存储的元素是无序的，当我们添加一个元素，不能重复的话，如下图，当每一次有数据新增的时候，不用hash表或者hash算法的时候，都会调用equals方法去进行对比，但是随这hashmap中的底层元素的新增，那么调用equals方法的频次就高了很多，此时效率大大降低了，如果里面有1万个元素，需要进行一万次的equals比较。因此为了大大提高效率，后续采用了一种hash表的方式进行存储。

hash表：

hash表的底层其实就是一个数组的方式，数组中存储的都是entry,数组拥有对应的索引值，如下图

hash表默认的大小是16，采用hash表的方式，当往集合中新增数据的时候，首先会调用对象的hashcode方法，然后运用hash算法对这个hashcode进行运算得到一个数组的索引值。然后就会根据这个索引值找到这个对应的数组中的位置，如果数组中改元素位置为空，那么可以直接新增，插入到数组中的指定位置，再次新增元素的时候，依旧会调用hash算法得到一个索引值，当我们新增的索引值在数组中已经存在了，再调用equals去进行比较，

如果一样的话，那么如果key相同那么，新增元素的VALUE就会将数组中的对应位置的VALUE替换掉即可。

如果不一样的话，那么就形成了链表，后加入的元素作为表头，先加入的元素形成链表加入到表头的后面，这种情况，专业形容词叫做碰撞.但是这种情况是我们尽可能去避免的，如果我们使用链表的方式，后续增加的链表长度变长，那么新增元素的时候，还是需要要链表中的元素进行equals进行比较，那么依旧会有效率低的问题的存在。

为了避免这种hash碰撞，我们在重写hashcode和equals方法的时候，尽量写的比较严谨一点。尽量让hashcode方法和equals方法保持一致。这样可以减缓hash碰撞的问题，但是这还是无法有效的避免hash碰撞。由于我们在新增元素的时候，运用哈希算法将得到对应数组的索引值，但是数组中的元素是固定的，得到的索引值一定是在数组的范围内的。为了在新增元素的时候，避免hash碰撞导致的链表长度过长，hashmap中又引入了一个加载因子的概念.

加载因子默认是0.75S，当hash表中的内容达到75%的时候，就去进行扩容操作。不能太大也不能太小，不然很容易浪费空间。当扩容之后，就会将链表中的内容，进行重排序。运用hash算法，得到索引值，放入到新的扩容之后的位置。在某种程序上，碰撞的概率就大大降低了。

但是，即便是进行了hash表的扩容，但是这种碰撞的机制还是避免不了，就意味着效率还是很低的。在进行查询的时候，会对链表进行一个一个的遍历，有可能我们需要的数据在链尾，但是我们进行遍历的时候，会对整个链接都进行遍历一遍，因此效率还是很低的。

于是在jdk1.8之后就进行了一些改变，在数组加上链表的基础上引入了红黑树的概念。红黑树是二叉树的一种。当碰撞的元素的个数大于8时，并且数组的总容量大于64的时候，会默认的将链表转为红黑树去进行存储