常见问题如下：

  1. 谈谈你理解的 HashMap，讲讲其中的 get put 过程。
  2. JDK 1.8 对 HashMap 做了什么优化？
  3. HashMap是线程安全的吗？
  4. 不安全会导致哪些问题？
  5. 如何解决？有没有线程安全的并发容器？
  6. ConcurrentHashMap 是如何实现的？ 1.7、1.8 实现上有什么不同？为什么要这么做？

首先，我们知道 HashMap 的底层是基于数组+链表的方式。
而 JDK 1.7 和 1.8在实现上是不相同的。

HahsMap put过程

  1. 判断当前数组是否初始化。
  2. 如果 key 为空，则 put 一个空值进去。
  3. 根据 key 计算出 hashcode。
  4. 根据 hashcode 定位所在桶。
  5. 如果桶是一个链表则遍历里面的 hashcode，判断key是否和传入 key 相等。如果相等则进行覆盖，并返回原来的值。
  6. 如果桶是空的，说明当前位置没有数据存入，新增一个 entry 对象写入当前位置。

HashMap get过程

  1. 根据 key 计算出 hahscode，然后定位具体的桶。
  2. 判断该位置是否为链表。
  3. 不是链表就根据 key， hashcode 是否相等返回值。
  4. 若为链表则遍历直到key、hashcode相等返回值。
  5. 如果size为0直接返回null。

1.7的缺点是：当 hash 冲突严重时，在桶上形成的链表会变得越来越长，导致查询效率越来越低，时候就复杂的为 O(n) 。

1.8重点优化了这个查询效率。
当链表长度达到指定的阈值时，链表就被转换为红黑树。修改为红黑树之后查询效率提高到了 O(logn) 。

原因是：并发操作在 HashMap 扩容时会调用 resize() 方法，这样容易形成环形链表。

ConcurrentHashMap 专门用于解决并发问题。

ConcurrentHashMap 在1.7和1.8的实现上也有不同。
其底层结构和HashMap一样，都是数组+链表。
和HashMap区别是：
其 value 和链表都是 volatile 修饰的，保证了获取时代可见性。

从原理上讲：ConcurrentHashMap采用了分段锁技术。不像HashTable那样不管是put还是get操作都是同步处理。
ConcurrentHashMap在1.7中的问题：查询遍历链表效率太低。

1.8中抛弃了原有的Segment分段锁，而采用CAS + synchronized 来保证并发安全性。

独占锁是一种悲观锁，synchronized就是一种独占锁，会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。
而另一个更加有效的锁就是乐观锁。所谓乐观锁就是，每次不加锁而是假设没有冲突而去完成某项操作，如果因为冲突失败就重试，直到成功为止。乐观锁用到的机制就是CAS，Compare and Swap（比较与交换）。

参考链接： HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你！

LinkedHashMap 原理

LinkedHashMap 是基于数据+双向链表实现的。

LinkedHashMap虽然增加了时间和空间的开销，但是通过维护一个运行于所有条目的双向链表，LinkedHashMap保证了元素的迭代顺序。

LinkedHashMap key 和value 允许为空，key重复后覆盖， 有序，非现场安全。
Entry有四个属性是从HashMap继承而来，分别如下：

  • K key
  • V value
  • Entry<K, V> next
  • int hash

其另外两个属性如下：

  • Entry<K, V> before
  • Entry<K, V> after

next 是用于维护HashMap指定table位置上连接Entry的顺序的。
before、After 用于维护Entry插入的先后顺序。

LinkedHashMap原理图

注意：循环双向链表头部存储的是最久访问的节点或是最先插入的节点，尾部为最近访问的或最近插入的节点。迭代器遍历方向是从链表头部开始到链表尾部结束。在链表尾部有一个空的header节点，该节点不存放key-value，为LinkedHashMap类的成员属性，循环双向链表的入口。

HashMap实现中有个init()方法，该方法只是提供子类实现相关的初始化调用。

LinekedHashMap 重写了init()方法，供其实现对Entry的初始化操作。

void init() {
    header = new Entry<K,V>(-1, null, null, null);
    header.before = header.after = header;
}