java 7 HashMap

1. 经典的哈希表实现：数组+链表

数组优点：随机寻址是常数时间，无论数组长度多大，都可以通过硬件电路的线性地址变换查找。复杂度都是O(1)的。

哈希桶：本质是将一个元素映射到一个哈希值，致命问题是哈希碰撞
多个元素的哈希值相同称为哈希碰撞，解决办法是使用链表

成员变量中的 Entry<K, V>[] table就是哈希桶，Entry类是链表结构

put(key, value)做了什么？
HashMap 刚完成初始化的时候并没有初始化默认的16个哈希桶，只包含一个空的哈希桶数组。第一次执行put方法时会inflateTable,将哈希桶的容量扩充为初始容量向上取整为2的幂，如果你设定初始化容量为17，在这一步会把17变成32。

Map中有transient关键字。 实现Serilizable接口的类，将不需要序列化的属性前添加关键字transient，这个属性就不会序列化。

2. HashMap 初始容量

初始容量为 1 << 4 (16), 且设定初始容量必须是2的幂，这个容量就是HashMap中哈希桶的个数。

为什么初始容量必须是2的幂？
任意一个对象的hashCode的范围是 -2 ^ 31 ~ 2 ^ 31 - 1, 大约是42亿个数。如何将这些数分散放到 n 个哈希桶中？如果使用 i % n 这种算法，有两个缺点：1. 负数求余是负数 ( -1 % 2 = -1) 2. 效率较慢 (硬件中求余的本质是不停的做除法，慢于位运算)

根据哈希值求索引的方法是 hash & (length - 1)，如果length是2的幂，
length - 1 的二进制就会是一个全 1 的数，它和哈希值按位与，可以快速的得到一个0 ~ length - 1的数组下标， 且分布是均匀的。

3. 哈希算法

HashMap中的hash(Object o)会对Object的hashCode做再一次的哈希稀疏，减少碰撞，但是java8将java7中的hash(Object o)丢弃了，换成了高16位按位与低16位。

5. 扩容：低效、线程不安全

负载因子默认是0.75
java7的扩容是所有问题的根源。当填入的元素数量大于等于capacity * load factor(容量乘负载因子)时，发生扩容，新的容量是旧的2倍，依然是2的幂。

1. 非常容易碰到死锁问题，在多线程的环境下哈希桶中的链表形成了环，导致cpu100%
   https://coolshell.cn/articles/9606.html
2. 潜在的安全隐患
   在旧版本tomcat服务器中，get请求的参数使用HashMap保存。精心设计的一系列参数，他们的哈希值都是相同的，会使HashMap退化成链表，引发DoS

6.Java8中的改进

1.由数组+链表变成了数组+链表+红黑树
哈希桶中的元素超过8的时候，哈希桶中的链表会变成红黑树。
2.扩容时插入顺序的改进