HashMap的数据结构及存储过程

1、HashMap基于哈希表的Map接口实现，是以key-value存储形式存在，即主要用来存放键值对。HashMap的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。
JDK1.8之前HashMap由数组+链表组成的,数组是HashMap的主体，链表则是为了解决哈希冲突(两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同)而存在的(“拉链法”)解决冲突。
JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值(或者红黑树的边界值,默认为8)并且当前数组的长度大于64时，此时索引位置上的所有数据改为使用红黑树存储。

补充：将链表转换成红黑树前会判断，即使阈值大于8，但是数组长度小于64，此时并不会将链表变为红黑树，而是选择进行数组扩容。
这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率，因为红黑树要进行左旋，优选，变色这些操作来保持平衡。同时数组长度小于64时，搜索时间相对要快些。所以综上所述为了提高性能和减少搜索时间，底层在阈值大于8并且数组长度大于64时，链表才转换为红黑树。
当然虽然增了红黑树作为底层数据结构，结构变得复杂了，但是阈值大于8并且数组长度大于64时，链表转换为红黑树时，效率也变得更高效。
2、特点：
a.存取无序的。
b.键和值位置都可以是null，但是键位置只能是一个null
c.键位置是唯一的，底层的数据结构控制键的。
d.jdk1.8之前数据结构：链表+数组 jdk1.8之后:链表+数组+红黑树。
e.阈值(边界值)>8并且数组长度大于64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。
3、存储过程

4、几道面试题
a.当两个对象的hashCode相等时会怎样？
会发生哈希碰撞,若key值内容相同则替换旧的value,不然连接到链表后面,链表长度超过阈值8就转换为红黑树存储。

b.何时发生哈希碰撞？什么是哈希碰撞？如何解决哈希碰撞？
只要两个元素的key计算的哈希码值相同就会发生哈希碰撞。jdk8前使用链表解决哈希碰撞。jdk8之后使用链表+红黑树解决哈希碰撞。

c.如果两个键的hashcode相同，如何存储键值对？
hashcode相同，通过equals比较内容是否相同。
相同:则新的value覆盖之前的value。
不同:则将新的键值对添加到哈希表中。

d.在不断的添加数据的过程中，会设计到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

e.HashMap已经继承了AbstractMap而AbstractMap类实现了Map接口，那为什么HashMap还要在实现Map接口呢？同样的ArrayList中LinkedList中都有这种结构。据java集合框架的创始人描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，jdk的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。
5、内容不同hash值可能相等