一.实现

JDK7采用数组+链表。 JDK8采用数组+链表、红黑树。

二.知识点

  1. 初始容量为2^4=16。
  2. 负载因子为0.75
  3. JDK1.8开始，一个桶存储的链表长度大于8时会将链表转化成红黑树。
  4. 确定桶的下标：hashcode & (length - 1)，length为当前容量，按位与操作。
  5. JDK7的链表插入以头插法进行的（扩容后顺序会相反，JDK8保持顺序）。

三.扩容

  1. 何时扩容？ 默认键值对的数量大于等于（容量（桶）*负载因子）的个数时即扩容为原来的两倍。

  2. 实现过程 扩容使用resize()实现，扩容操作把oldTable的所有键值对重新插入newTable中。 扩容的时候需要重新计算桶的下标，容量（桶）为2的n次方极大降低桶下标操作的复杂度。对于一个key，16扩容为32只需看第五位，为0不变，为1+16。

五.问题

  1. 用户传入的初始容量不为2的n次方。 HashMap可以自动地将传入的容量转换为2的n次方。

  2. 为什么数组的长度一定为2的n次方？ 只有长度为2的n次方的时候，我们对它减1才能拿到全部为1的二进制，这样才能在按位与操作中非常快速的拿到下标，并且分布也是均匀的。

  3. Java7d HashMap有哪些问题？ 1） 非常容易死锁，多线程扩容导致链表的值互相指向（头插法导致的），然后在查询的时候无此元素循环导致死锁（环形链表导致CPU100%）。 2) 潜在的安全隐患：可以通过精心构造的恶意请求引发Dos。链表的性能退化（产生大量链表，消耗大量cpu）。 3） 为什么大于8才能转换成红黑树？ 根据泊松分布计算，参数为0.5，超过8的时候概率非常的小。

六.ConcurrentHashMap

线程安全的HashMap。

  1. HashTable通过使用Synchronized修饰方法的方式来实现多线程同步，因此，HashTable的同步会锁住整个数组，性能在高并发情况下非常差。
  2. ConcurrentHashMap采用锁分离技术，对应的put、remove等操作也只需要锁住当前线程需要用到的桶，而不需要锁住整个数据。
  3. JDK1.7采用Segment分段锁，1.8采用CAS+Synchronized来保证并发安全性。
  4. ConcurrentHashMap的Hash链中除了变量value外，其他变量都被定义为final类型，保证不加锁读取到一致的数据。（HashEntry链表）

七.参考视频

https://www.bilibili.com/video/BV18E411C7kD https://www.bilibili.com/video/BV1T54y1B7rV?p=37