如何设计线程安全的 HashMap?
如何设计线程安全的 HashMap?
HashMap 线程不安全的体现：
- 多线程下扩容死循环：JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
- 多线程的put可能导致元素的丢失：多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。
- put和get并发时，可能导致get为null：线程1执行 put 时，因为元素个数超出 threshold 而导致 rehash，线程2此时执行get，有可能导致这个问题。此问题在JDK 1.7和 JDK 1.8 中都存在。
针对问题1，JDK1.8 使用尾插法已经解决了，因此我们需要重点解决问题2和问题3。
思路一：使用 Synchronized 来实现线程安全的，给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞等待需要的锁被释放。
优点：实现简单。
缺点：竞争激烈的多线程场景中性能会变的很差。
思路二：使用 ConcurrentHashMap JDK1.7 的实现思路， 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
优点：并发访问率比Synchronized更高，效率也更高。
思路三：使用 ConcurrentHashMap JDK1.8 的实现思路，采用CAS + synchronized实现更加低粒度的锁。
优点：将锁的级别控制在了更细粒度的哈希桶元素级别，也就是说只需要锁住这个链表头结点（红黑树的根节点），就不会影响其他的哈希桶元素的读写，大大提高了并发度。
CAS 机制在 ConcurrentHashMap 的具体体现： - 在初始化数组时,它会以 CAS 的方式修改初始化状态，避免多个线程同时进行初始化；
- 在执行 put 方法初始化头节点时，它会以 CAS 的方式将初始化好的头节点设置到指定槽的首位，避免多个线程同时设置头节点；
- 在数组扩容时,每个线程会以 CAS 方式修改任务序列号来争抢扩容任务，避免和其他线程产生冲突；
- 在执行 get 方法时，它会以 CAS 的方式获取头指定槽的头节点,避免其他线程同时对头节点做出修改。