hashMap 底层结构是 数组 + 链表，
key 用Set 存储，因此key不允许重复，value用collection存储

HashMap 在 JDK 1.8新增的红黑树结构

JDK 1.8以后的HashMap 结合了哈希表和红黑树的优点，不仅快速，而且
在极端情况下也能保证性能， 在链表长度大于8的时候，将后面的数据存在红黑树中，以加快检索速度。

面试题：

1.HashMap 中 equals() 和 hashCode() 有什么作用？// hashMap 如何保证元素唯一性？

HashMap 的添加、获取时需要通过 key 的 hashCode() 进行 hash()，
然后计算下标 ( n-1 & hash)，从而获得要找的同的位置。

当发生哈希碰撞时，利用 key.equals() 方法去链表或树中去查找对应的节点。

2.HashMap 的put()、get() 原理

当put元素时，首先根据key的hashCode重新计算哈希值，
得到该元素在数组中的下标，如果在该位置数组已存在元素，
那么在该位置上的元素将以链表的形式存放，先加入的存放在链尾，
后加入的存在链头，如果数组该位置上没有元素，
就直接将该元素放在数组中该位置，
如果当太多元素有相同的哈希值时，所有元素都会存在一个链表中，查找效率会低下，
因此，JDK1.8之后，HashMap 结构采用数组+链表+红黑树实现，
当链表长度超过阈值（8）时，将链表转换为红黑树，
以减少查找时间。
当get元素时，实现计算key的hashCode，
找到数组中对应位置的某一元素，然后通过key的equals() 在对应位置的
链表中找到需要的元素，
如果第一个节点是TreeNode，说明采用的是数组+红黑树结构，遍历红黑树，得到节点值

3.hashMap 扩容

当hashmap 中元素越来越多时，hash冲突几率会越来越高，因为
数组的长度是固定的。
为了提高查询效率，就要对hashMap 的数组扩容，数组扩容这个
操作也会出现在ArrayList中，在HashMap数组扩容时，会申请内
存空间，把原数组中的元素复制到新数组中，数组扩容操作比较耗时。

hashMap 在何时扩容？
当hashMap元素个数超过数组大小的负载因子时，就会扩容，
负载因子默认值是0.75，这是一个折中取值，也就是说，
默认情况下，数组默认大小是16，当元素个数超过16*0.75=12时，
就把数组的大小扩展为2*16=32，即扩大1倍，
然后重新计算每个元素在数组中的位置，这是一个耗时操作，
所以预知hashMap元素个数，那么预设元素个数能够有效提高hashMap性能。

4.为什么hashMap的数组默认大小为16，数组负载因子是0.75？

如果数组默认大小设置太大，会影响内存空间，16是一个折中的大小