目录

1. HashMap

2. HashTable 

3. ConcurrentHashMap 

1. HashMap

    HashMap 是 Java 中非常常用的一个数据结构，它主要用于存储 键值对（K，V）。

    在JDK 1.7中，HashMap的实现是基于 Table数组 和 Entry链表 的组合。

      

    从JDK 1.8开始，为了解决链表过长导致的性能问题，当链表长度超过一定阈值时，链表会转换为红黑树。

    特点：

  （1）HashMap 允许使用 null 作为 键（K）或值（V），但是最多只能有一个键为null。

  （2）在单线程下，HashMap 是不需要关心线程安全问题的； 但是在多线程下，HashMap就不是线程安全的，因为 它没有任何加锁的操作来 保证线程安全 。

    所以，HashMap 只能在单线程线程安全下执行，但如果我们想在多线程下进行呢？

    此时我们就需要了解一下 HashTable 。

2. HashTable 

     HashTable不允许键为null，但允许值为null。

     HashTable 为保证多线程情况下 是线程安全的，就给整个链表 加入 一把大锁（如下图）。

    如果加一把大锁，那多个线程 现在同时操作 这个 HashTable 的时候，当某个线程在操作的时候，其他线程就只能干等着， 这大大影响了整体的效率。

    那有没有 更好的加锁方式来解决这个问题的呢？

    接下来来看 ConcurrentHashMap 。

3. ConcurrentHashMap 

    ConcurrentHashMap 是基于 HashTable 的基础上 将一把大锁 分解到 对数组中每个链表 进行加锁，这样，当我们同时操作 HashMap 中的不同链表中的数据时候，就可以在不影响 线程安全的情况下，将效率进一步 提高了。

   

    ConcurrentHashMap 特点：

    （1） ConcurrentHashMap 最核心的改进就是，将一个全局的大锁，改进成 每个链表独立的小锁，这样就大大降低了 锁冲突 的概率 。

    （2）  ConcurrentHashMap 它还 充分利用到了 CAS 的特性， 将 一些不必要的加锁环节给省略加锁了。

    例如， 需要用变量记录 hash 中的元素个数。

    （3） ConcurrentHashMap 还有一个激进的操作，对读操作没有加锁。

    读和读，读和写之间，都不会有锁竞争，

    那有没有可能出现 “ 读到一个修改了一半的值呢”：

    答案是不会，这是因为 ConcurrentHashMap 在底层编码中，谨慎的处理了一些细节，修改的时候，会避免使用一些 非原子的操作，所以 读的时候，要么 读的是修改之前的值，要么是读的修改之后 的值。

    （4） ConcurrentHashMap 针对扩容操作，做了单独的优化。

    HashTable 以及 HashMap 在进行扩容的时候，都是将 所有元素进行拷贝一份，这样一来，就会在扩容的 时候 出现卡顿。

    而 ConcurrentHashMap 不会，它在扩容 过程中，并不是一次将所有的元素进行拷贝，而是分成多份进行 分批 搬运，每次只搬运 部分 数据，这样就避免了卡顿。