首先我们来谈谈HashMap，从字面上来看，HashMap的名字中带有hash，我们就可以联想到HashMap的存储方式可能与hash有关。
下面我们来谈谈HashMap的存储机制：
HashMap是以键值对的形式存储数据的，其底层存储是以数组+链表的方式实现的（jdk1.8之后又引入了红黑树）。
首先我们可想象一个数组，这个数组的默认大小是16（因为在创建一个HashMap对象时，如果不指定其长度，那么底层将会默认创建一个有16个大小的数组）。
HashMap在存入一个数据时，会先去调用对象的hashCode方法计算出该对象应该放在之前创建的数组的哪个位置（即数组的索引值），若该位置为空，则直接将该对象存进去，若该位置有值，在去调用对象的equals方法比较两个key的值是否相等，如果相等则覆盖掉value的值，如果不相等，则在数组该索引处将旧值后移并将新值插入，形成一个链表（这是jdk1.7及以前的方式）。
上述方式存在一个问题，即如果多次添加数据的位置相同的话，那么这个链表就会一直增长，而且每次在链表中添加数据时都要移动链表中的数据，这样情况称之为碰撞。我们需要尽量减少这种碰撞的发生，发生碰撞，可能会增长链表，链表增长越长，碰撞的所需的时间就越多，可想是多么影响效率。
所以HashMap就引入了加载因子避免碰撞，默认为0.75，即当元素达到现有hash表的75%时扩容，一旦扩容将会重新排序hash表，减少碰撞的概率。
jdk1.8之后：
上述情况依旧不能避免形成一长串链表的可能，所以在jdk1.8之后引入了红黑树。开始的存储方式与之前相同，通过key确定存放位置，通过value判断是否覆盖或添加链表，超过阈值0.75自动扩容，但是改变的是如果链表的长度大于8，那么就会将链表转化为红黑树，但是在转变成树之前还会有一个判断，只有键值对的数量大于64才会发生转换。这是为了避免在哈希表创建初期，多个键值对恰好被放入了同一个链表中而导致的不必要的转化。