问九：如何设计一个线程安全的HashMap？

1. 将所有public方法都加上synchronized： 相当于设置了一把全局锁，所有操作都需要先获取锁（比如直接使用Collections.synchronizedMap()方法对其进行加锁操作），java.util.HashTable就是这么做的，性能很低

2.由于每个桶在逻辑上是相互独立的，将每个桶都加一把锁，如果两个线程各自访问不同的桶，就不需要争抢同一把锁了。这个方案的并发性比单个全局锁的性能要好，不过锁的个数太多，也有很大的开销。

3.锁分离(Lock Stripping)技术：第2个方法把锁的压力分散到了多个桶，理论上是可行的的，但是假设有1万个桶，就要新建1万个ReentrantLock实例，开销很大。可以将所有的桶均匀的划分为16个部分，每一部分成为一个段(Segment)，每个段上有一把锁，这样锁的数量就降低到了16个，JDK 7里的java.util.concurrent.ConcurrentHashMap就是这个思路。

4. 在JDK8里，ConcurrentHashMap的实现又有了很大变化，它在锁分离的基础上，大量利用了了CAS指令。并且底层存储有一个小优化，当链表长度太长（默认超过8）时，链表就转换为红黑树。链表太长时，增删查改的效率比较低，改为红黑树可以提高性能。实现的难度有点高，JDK8里的ConcurrentHashMap有6000多行代码，JDK7才1500多行。