你不知道的HashMap

面试中经常会问到常用数据结构，比如HashMap。 相信你平时几乎每天都会用到HashMap，但是你知道它是的实现原理是怎样的吗？ 这里先提几个问题：HashMap和Hash算法有什么关系？HashMap中的键值对是以put的次序顺序排列的吗？

HashMap之存储

注意表里有几个信息， · 排列顺序并不是以存储次序来的 · hash 值长度是固定的

面试时要记住这两个关键点，因为说起HashMap的原理基本离不开这个现象。 现在我们来解释其中的原理。

HashMap 存储时会以Hash算法将输入的key值变换为固定长度的输出计算为index， 如果无碰撞则直接放进HashMap， 如果有碰撞则以链表放到对应的index后， 如果碰撞导致链表长度过长，则将链表转换为红黑树， 如果节点已经存在则更新为新值， 如果HashMap满了则resize扩展HashMap。

什么是哈希碰撞呢？

因为Hash算法是将任意长度的输入转换为固定长度的输出，那么就必然会存在Hash值重复的情况。 此时就需要将key作为链表添加到对应的index后了。 当然每个节点包含了Hash，Key，Value信息，当Hash碰撞时还会以Key作为判断依据，所以以链表存储也不会影响数据唯一性。

HashMap的大小怎么确定呢？

HashMap用两个东西来确定大小 · Initial Capacity · Load Factor Capacity是HashMap的buckets数量，也就是节点的数量。Factor则是允许的最大容量比例 当HashMap的存储量超过Factor，则需要对HashMap进行resize，一般是2倍Capacity。