一、底层结构

1.7 数组加链表
1.8 数组加链表加红黑树（单向链表）

二、源码分析的一些疑问点（1.7）

发生冲突时，链表采用头插法。

头插法一定比尾插好吗？

不见得，因为你总会去遍历一次链表，看是否有这个元素，没有才需要插入。
key是允许为null的。

补充知识：二的幂次方的数，用二进制表达，所有位上，只有1个位是1。如8，就是1000.

为什么容量是2的幂次方？

n是容量，(n - 1) & hash实际上是计算出 key 在数组中索引位置。用这个与运算代替了取模运算。
(n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n

由于取模的预算没有位运算快，因此为了性能这么设计也合理。

因此我们即使设定容量不为幂，底层也会帮助我们改成2的幂次。如我们设定为10，实际容量会是16.

key能为null吗？

key为null，会存在数组中的索引为0的位置。
HashMap对象的key、value值均可为null。但显然只能有一个Key为null。
HahTable对象的key、value值均不可为null。

且两者的的key值均不能重复，若添加key相同的键值对，后面的value会自动覆盖前面的value，但不会报错。

扩容为什么是2倍

可以和容量是2的幂次方的问题相同

1.7扩容线程不安全时会出现循环链表

如果链表中为1->2->3，那么扩容可能形成3->2->1，因为是头插法，所有顺序都颠倒了。中间某个线程不安全就会导致头尾相连。

在多线程环境下，1.7 会产生死循环、数据丢失、数据覆盖的问题，1.8 中会有数据覆盖的问题。（改成尾插也是有问题的）

负载因子0.75

当map中的所有元素个数超过数组容量的0.75倍，就会扩容。
那为什么是0.75呢，反正大了为1容易冲突，小了0.5容易浪费空间，0.75是一个折中的考虑。为什么不是0.6或者0.8，这个可以根据大量的数据插入计算出效率，0.75可能折中是最佳。

fast-fail机制

当多个线程对同一个集合进行操作的时候，某线程访问集合的过程中，该集合的内容被其他线程所改变(即其它线程通过add、remove、clear等方法，改变了modCount的值)；这时，就会抛ConcurrentModificationException异常，产生fail-fast事件。

1.7 扩容

1.7扩容时需要重新计算哈希值和索引位置，1.8并不重新计算哈希值，巧妙地采用和扩容后容量进行&操作来计算新的索引位置。

三、源码分析（1.8）

2.1 HashMap的几个重要默认参数

初始数组容量默认为16,负载因子为0.75。也就是说大小为16的HashMap的数组中，有数据量超过13时，就会扩容成32。

超过8个转化成红黑树？

在理想情况下，使用随机哈希码，节点出现的频率在hash桶（形成的链表）中遵循泊松分布。也就是说链表长度超过8个，概率是百万分之6，但是超过8个影响了性能，因此能不转换成红黑树就不要转化。

变树变链表

链表长度超过8个就会将链表转换为红黑树，长度低于6个就会将红黑树转化成链表。这里可以理解成避免扩容缩容会产生震荡。扩一次缩一次。为什么是8呢，因为太长会降低性能。之前也分析过，超过8的情况很少，但是还是有，如果有那就转用更高效的红黑树。

1.8扩容机制

1.7扩容是重新计算，但是1.8不同，利用新增的一位要么是1要么是0，决定元素要么在原来的位置，要么在原位置在移动2次幂的位置。这样也保证了均匀性。