1.JDK1.7的HashMap
底层是以数组 单链表的形式进行存储的! 1.1.实例化：在底层直接创建Entry[]一维空数组，在第一次put元素时进行初始化和计算容量，数组长度为大于等于给定Size的最小2的次幂。 1.2.插入键值对： 当调用put(key,value)时，经历以下步骤： ①计算key的哈希值（详见我的之前一篇写HashMap底层哈希值计算的文章），然后将哈希值与数组长度-1进行按位与运算，得到应该存储的数组下标索引。 ②如果该数组位置没有Entry,则直接添加即可。 ③若该数组位置已经有Entry了，则计算key与该位置上的其他key的hash值，如果hash值都不相同，则采用头插法添加(key，value)到该数组位置。若与某个Entry中的key的hash值相同，则进一步通过equals方法进行比较，若equals相同则覆盖，若不同则采用头插法添加(key，value)到该数组位置。 1.3.扩容方式 先进行条件判断，key是否为空等等。然后准备进行Entry添加。 当数组的长度大于等于threshold且要插入的地方不为null空值时，进行扩容为原来的2倍。 扩容后需要重新计算要插入元素的hash值，并且计算在新数组长度下的索引。 1.4.Hash算法: 1.7版本会进行判断，当要插入的键值为字符串时，选用其他的hash值计算方法。并且hash值计算完之后采用复杂的避免hash碰撞的运算。hash值没有用final修饰，在进行扩容后可以重新计算。
2.JDK1.8的HashMap
底层是以数组 链表 红黑树的形式进行存储的! 2.1.实例化：在底层直接创建Node（Node TreeNode）[]一维空数组，但是并没有赋值，属于懒汉模式。在第一次put元素时进行初始化和计算容量，数组长度为大于等于给定Size的最小2的次幂。 2.2.插入键值对： 与JDK1.7相同,区别是存在链表转化为红黑树的树化，以及节点插入为尾插法。 2.3.扩容方式: 在进行初始化时、添加节点结束之后以及判断是否树化的时候，都会去判断扩容。添加节点结束之后只要size大于阈值，就一定会扩容，是一个条件。扩容为原来长度的2倍。 1.4.Hash算法: 1.8版本直接用对应OBject类的hash值计算方法。避免hash碰撞的运算即为简单的：向右移位，并进行异或。hash值用final修饰，一旦确定不再更改。
3.JDK1.8中一些其他细节
3.1.加载因子：在进行扩容时，会进行阈值的判断，这个阈值大小是通过当前的数组的容量和一个加载因子进行确定的。加载因子默认为0.75，即在初始默认大小为16的数组情况下，当数组的元素个数达到了12，即进行扩容，扩容为原来的2倍。 3.2.链表和红黑树的转化： 链表和红黑树的转化条件是，当数组上某一索引上元素以链表的形式存在个数>8时，且数组的长度>64，则会将此位置上的所有数据改为用红黑树存储，红黑树类似于二叉排序树，可以提高key值搜索的效率。 java源码中关于为什么树化的解释： 由于TreeNodes的大小大约是常规节点的两倍，因此我们仅在容器包含足够的节点以保证使用时才使用它们（参见 TREEIFY_THRESHOLD 值）。当它们变得太小（由于移除或调整大小）时，它们会被转换回普通的bin。理想情况下，在随机哈希代码下，bin中的节点频率遵循泊松分布，下面就是list size k 的频率表。
- 0：0.60653066
- 1：0.30326533
- 2：0.07581633
- 3：0.01263606
- 4：0.00157952
- 5：0.00015795
- 6：0.00001316
- 7：0.00000094
- 8：0.00000006
- 其他：少于一百万分之十
因此通过随机哈希值，每个索引下的节点频率遵循泊松分布，进行计算，在同一个数组位置出现8个节点的概率为百万分之六！！！。所以基本不可能出现。这就保证了前面用链表存储的空间利用率。当节点大于8个时，我们就需要进行树化，从而牺牲部分空间来提高HashMap的检索效率。 3.3.为什么不选择6进行树化？ 因为虽然6的频率也很低，但仍然比8打了1000倍左右，而且，遇到组合Hash攻击时，会使性能下降。其实是综合了性能和检索效率，提高了被hash攻击的抗性。 3.4.为什么在减至6后，需要进行反树化? 6个元素通过红黑树查询是3次，而通过链表是6次。这里时间减半，但是内存空间加倍了（因为TreeNode与Node是两倍关系），再减少，空间的损失以及无法弥补时间的检索效率的提升。而且维护红黑树更加复杂。 3.5.为什么把链表转化为红黑树的阈值是8,而不是6、7或者不是20呢？ 这个问题其实和3.3.差不多，但3.3只回答了一部分。 即为什么不是6，是综合了性能和时间效率。 那为什么不是7？因为在<=6的时候还会进行反树化，如果选择7进行树化，则会导致频繁红黑树的转化与反树化，导效率降低。而>=8进行树化，可以使得中间有一个差值7进行过渡。 而大于8以上，很明显，使得链表的时间效率降低很多，而且出现的概率很低，基本无法实现红黑树的优化效果。
