Java面试题：HashMap为什么线程不安全、ConcurrentHashMap原理、ConcurrentHashMap与HashMap区别、Map总结

文章目录

1.HashMap 为什么线程不安全

• 1.1 概述——HashMap线程不安全的体现、原因、改善
• 1.2 jdk1.7中的线程不安全——死循环、数据丢失
• 1.3 jdk1.8中的线程不安全——数据覆盖
• 1.4 如何在多线程环境下使用安全的HashMap

2.ConcurrentHashMap原理、分段锁、局部锁、线程安全

• 2.1 ConcurrentHashMap概述
• 2.2 ConcurrentHashMap源码 jdk1.8
• 2.3 ConcurrentHashMap结构 jdk1.7-->jdk1.8
  • jdk1.7下的ConcurrentHashMap
    • get方法
    • put方法
  • jdk1.8下的COncurrentHashMap
    • 1）结构改变
    • 2）HashEntry 改为 Node
    • 3）Put操作的变化
    • 4）Get操作的变化
• 2.4 ConcurrentHashMap总结

3.HashMap与ConcurrentHashMap工作原理、区别、总结

• 3.1 HashMap与ConcurrentHashMap区别
• 3.2 工作原理
  • 3.2.1 HashMap
  • 3.2.2 ConcurrentHashMap

4.HashMap与Hashtable的区别

5.HashMap、Hashtable、ConcurrentHashMap区别

6.为什么 HashMap 采用拉链法而不是开放地址法？

7.Map总结

还记得 HashMap的实现原理、jdk1.7与jdk1.8的HashMap有什么区别吗？如果忘记可以到这里重新温习：Java面试题：ArrayList底层实现原理、HashMap的实现原理、HashMap的jdk1.7和jdk1.8有什么区别

1.HashMap 为什么线程不安全

1.1 概述——HashMap线程不安全的体现、原因、改善

HashMap是线程不安全的，它是非同步的数据结构。主要体现在：

• jdk1.7中，在多线程环境下，扩容时会出现 死循环、数据丢失 问题
• jdk1.8中，在多线程环境下，会发生 数据覆盖 的情况

HashMap线程不安全原因（具体原因见1.2、1.3）：

• JDK1.7 中，HashMap扩容时使用头插法插入元素。具体原因：在 HashMap 触发扩容时，正好两个线程同时在操作同一个链表，当线程A被挂起，线程B已完成数据迁移，等CPU资源释放后被挂起的线程A重新执行之前的逻辑，数据已经被改变，形成环形链表，造成死循环、数据丢失问题 —— 在JDK1.8中采用了尾插法插入元素，再扩容时会保持链表原本的顺序，避免了死循环的问题
• JDK1.8 中，由于多线程对HashMap进行put操作，调用了HashMap#putVal()，如果两个线程并发执行 put 操作，并且两个数据的 hash 值冲突，就可能出现数据覆盖。具体原因：线程 A 判断 hash 值位置为 null，还未写入数据、由于时间片耗尽导致被挂起，此时线程 B 正常插入数据。接着线程 A 获得时间片，由于线程 A 之前已进行hash碰撞的判断，所以此时不会再进行判断、而是直接进行插入，就会把刚才线程 B 写入的数据覆盖掉

为了在多线程环境下使用安全的HashMap，可以采取以下措施：

1. 使用线程安全的替代品：使用线程安全的集合类，如ConcurrentHashMap，它是专门设计用于多线程环境的哈希表，提供了高效的并发性能。
2. 显式同步：如果必须使用普通的HashMap，确保在访问和修改HashMap时进行适当的同步，使用synchronized关键字或其他同步机制来保护共享资源。如Collections.synchronizedMap(map)，包装成同步Map，原理就是在HashMap的所有方法上synchronized
3. 使用线程局部变量：为每个线程维护一个独立的HashMap实例，以避免线程间竞争。ThreadLocal<Map<String, Integer>> threadLocalMap = ThreadLocal.withInitial(HashMap::new);

1.2 jdk1.7中的线程不安全——死循环、数据丢失

jdk1.7 HashMap的transfer函数如下：

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

在对table进行扩容到newTable后，需要将原来数据转移到newTable中，注意10-12行代码，这里可以看出在转移元素的过程中，使用的是头插法，也就是链表的顺序会翻转，这里也是形成死循环的关键点。下面进行详细分析。

前提条件：此处假设

• hash算法为简单的用key mod链表的大小。
• 最开始hash表size=2，key=3,7,5，则都在table1中
• 然后进行resize，使size变成4。

未resize前的数据结构如下：

如果在单线程中，最后的结果如下：

在多线程环境下，假设有两个线程A和B都在进行put操作。线程A在执行到transfer函数中第11行代码 newTable[i] = e 处挂起，此时线程A中运行结果如下，e=3、next=7、e.next=null：

线程A挂起后，此时线程B正常执行，并完成resize操作，结果如下：

重点来了，根据Java内存模式可知，线程B执行完数据迁移后，此时主内存中newTable和table都是最新的，也就是说：7.next=3、3.next=null。

此时切换到线程A上，在线程A挂起时内存中值如下：e=3，next=7，newTable3=null，代码执行过程如下：

newTable[3]=e ----> newTable[3]=3
e=next ----> e=7

此时结果如下：

继续循环：

e=7
next=e.next ----> next=3【从主存中取值】
e.next=newTable[3] ----> e.next=3【从主存中取值】
newTable[3]=e ----> newTable[3]=7
e=next ----> e=3

结果如下：

再次进行循环：

e=3
next=e.next ----> next=null
e.next=newTable[3] ----> e.next=7 即：3.next=7
newTable[3]=e ----> newTable[3]=3
e=next ----> e=null

注意此次循环：e.next=7，而在上次循环中7.next=3，出现环形链表，并且此时e=null循环结束。结果如下

上面说了此时e.next=null即next=null，当执行完e=null后，将不会进行下一轮循环。到此线程A、B的扩容操作完成，很明显当线程A执行完后，HashMap中出现了环形结构，当在以后对该HashMap进行操作时会出现死循环。

并且从上图可以发现，元素5在扩容期间被莫名的丢失了，这就发生了数据丢失的问题。

参考回答：

在jdk1.7的hashmap中在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环。

比如说，现在有两个线程

线程一：读取到当前的hashmap数据，数据中一个链表，在准备扩容时，线程二介入

线程二：也读取hashmap，直接进行扩容。因为是头插法，链表的顺序会进行颠倒过来。比如原来的顺序是AB，扩容后的顺序是BA，线程二执行结束。

线程一：继续执行的时候就会出现死循环的问题。

线程一先将A移入新的链表，再将B插入到链头，由于另外一个线程的原因，B的next指向了A，所以B->A->B,形成循环。当然，JDK 8 将扩容算法做了调整，不再将元素加入链表头（而是保持与扩容前一样的顺序），尾插法，就避免了jdk7中死循环的问题。

1.3 jdk1.8中的线程不安全——数据覆盖

在jdk1.8中对HashMap进行了优化，在发生hash碰撞，不再采用头插法方式，而是直接插入链表尾部 即尾插法，保持了链表元素的顺序，解决了扩容造成的死循环、数据丢失问题。如果你去阅读1.8的源码会发现找不到HashMap#transfer()，因为JDK1.8直接在HashMap#resize()中完成了数据迁移。

但在多线程的情况下仍然不安全，会发生数据覆盖问题。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)  //如果没有hash碰撞则直接插入元素
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

根据putVal源码，注意第6行代码，如果没有hash碰撞则会直接插入元素。假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完第6行代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入；然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。

除此之前，还有代码的第38行处++size，假设线程A、B同时进行put操作，当前HashMap的zise大小为10，当线程A执行到第38行代码时，从主内存中获得size的值为10后准备进行+1操作，但是由于时间片耗尽只好让出CPU；线程B拿到CPU还是从主内存中拿到size的值10进行+1操作，完成了put操作并将size=11写回主内存，然后线程A再次拿到CPU并继续执行(此时size的值仍为10)，当执行完put操作后，还是将size=11写回内存，此时，线程A、B都执行了一次put操作，但是size的值只增加了1，所有说还是由于数据覆盖又导致了线程不安全。

1.4 如何在多线程环境下使用安全的HashMap

为了在多线程环境下使用安全的HashMap，可以采取以下措施：

1. 使用线程安全的替代品：使用线程安全的集合类，如ConcurrentHashMap，它是专门设计用于多线程环境的哈希表，提供了高效的并发性能。
2. 显式同步：如果必须使用普通的HashMap，确保在访问和修改HashMap时进行适当的同步，使用synchronized关键字或其他同步机制来保护共享资源。如Collections.synchronizedMap(map)，包装成同步Map，原理就是在HashMap的所有方法上synchronized
3. 使用线程局部变量：为每个线程维护一个独立的HashMap实例，以避免线程间竞争。ThreadLocal<Map<String, Integer>> threadLocalMap = ThreadLocal.withInitial(HashMap::new);

2.ConcurrentHashMap原理、分段锁、局部锁、线程安全

HashMap 在多线程环境下操作不安全，ConcurrentHashMap是HashMap的线程安全版本。

JDK1.8中 ConcurrentHashMap内部是使用 数组 + 链表 + 红黑树 的结构来存储元素。相比于同样线程安全的HashTable来说，效率等各方面都有极大地提高。

ConcurrentHashMap 的优势在于兼顾性能和线程安全，一个线程进行写操作时，它会锁住一小部分，其他部分的读写不受影响，其他线程访问没上锁的地方不会被阻塞。

ConcurrentHashMap底层数据结构：

• JDK1.7底层采用分段的数组+链表实现
• JDK1.8采用的数据结构跟HashMap1.8的结构一样，数组+链表+红黑树。

加锁的方式：

• JDK1.7采用Segment分段锁，底层使用的是ReentrantLock
• JDK1.8采用CAS添加新节点，采用synchronized锁定链表或红黑二叉树的首节点，相对Segment分段锁粒度更细，性能更好

JDK1.8中的ConcurrentHashMap比JDK1.7中的ConcurrentHashMap好在哪里？

• JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）。
• JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也降低了。
• JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表。

JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock，有以下几点：

• 因为锁粒度降低了，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）。在相对而言的低粒度加锁方式，synchronized并不比ReentrantLock差，在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界，更加的灵活，而在低粒度中，Condition的优势就没有了。
• JVM的开发团队从来都没有放弃synchronized，而且基于JVM的synchronized优化空间更大，使用内嵌的关键字比使用API更加自然。
• 在大量的数据操作下，对于JVM的内存压力，基于API的ReentrantLock会开销更多的内存，虽然不是瓶颈，但是也是一个选择依据。

2.1 ConcurrentHashMap概述

java.util.concurrent.ConcurrentHashMap属于JUC包下的一个集合类，可以实现线程安全。

ConcurrentHashMap和HashMap一样，是一个存放键值对的容器。使用hash算法来获取值的地址，因此时间复杂度是O(1)。查询非常快。同时，ConcurrentHashMap是线程安全的HashMap。专门用于多线程环境。

JDK1.7

ConcurrentHashMap 采用分段锁策略，由多个 Segment 组合而成，其中 Segment 可以看成一个 HashMap， 不同点是 Segment 继承自 ReentrantLock，在操作的时候给 Segment 赋予了一个对象锁（Put 操作时，锁的是某个 Segment，其他线程对其他 Segment 的读写操作均不影响），从而保证多线程环境下并发操作安全。

不同Segment的并发写入（可以并发执行）；同一Segment的一写一读（可以并发执行，table有volatile关键字修饰，保证每次获取值都是最新的）；同一Segment的并发写入，会阻塞

ConcurrentHashMap 中每个Segment各自持有一把锁。在保证线程安全的同时降低了锁的粒度，让并发操作效率更高。

JDK1.8

相比于 JDK1.7 中的 ConcurrentHashMap，JDK1.8 中 ConcurrentHashMap 类取消了 Segment 分段锁，采用 CAS + synchronized 来保证并发安全；数据结构跟jdk1.8中HashMap一样，数组+链表改为 数组+链表+红黑树，当冲突链表长度大于8时，会将链表转变成红黑树结构。

ConcurrentHashMap 中 synchronized 只锁定当前链表或红黑二叉树的首节点，只要节点 hash 不冲突，就不会产生并发，相比 JDK1.7 的 ConcurrentHashMap 效率又提升了 N 倍！

2.2 ConcurrentHashMap源码 jdk1.8

组成

//ConcurrentHashMap使用volatile修饰节点数组，保证其可见性，禁止指令重排。
//而HashMap没有使用volatile，  transient Node<K,V>[] table; 
transient volatile Node<K,V>[] table;

put方法 put()方法没有用synchronized修饰

public V put(K key, V value) {
    return putVal(key, value, false);
}


final V putVal(K key, V value, boolean onlyIfAbsent) {
    // key和value都不能为null
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {  //死循环，可视为乐观锁
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            // 如果tab未初始化或者个数为0，则初始化node数组
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                // 如果使用CAS插入元素时，发现已经有元素了，则进入下一次循环，重新操作
                // 如果使用CAS插入元素成功，则break跳出循环，流程结束
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            // 如果要插入的元素所在的tab的第一个元素的hash是MOVED，则当前线程帮忙一起迁移元素
            tab = helpTransfer(tab, f);
        else {   //发生hash冲突
            // 如果这个tab不为空且不在迁移元素，则锁住这个tab（分段锁）
            // 并查找要插入的元素是否在这个tab中
            // 存在，则替换值（onlyIfAbsent=false）
            // 不存在，则插入到链表结尾或插入树中
            V oldVal = null;
            synchronized (f) {
                // 再次检测第一个元素是否有变化，如果有变化则进入下一次循环，从头来过
                if (tabAt(tab, i) == f) {
                    // 如果第一个元素的hash值大于等于0（说明不是在迁移，也不是树）
                    // 那就是tab中的元素使用的是链表方式存储
                    if (fh >= 0) {
                        // tab中元素个数赋值为1
                        binCount = 1;
                        // 遍历整个tab，每次结束binCount加1
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                // 如果找到了这个元素，则赋值了新值（onlyIfAbsent=false），并退出循环
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                // 如果到链表尾部还没有找到元素，就把它插入到链表结尾并退出循环
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        // 如果第一个元素是树节点
                        Node<K,V> p;
                        // tab中元素个数赋值为2
                        binCount = 2;
                        // 调用红黑树的插入方法插入元素，如果成功插入则返回null，否则返回寻找到的节点
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            // 如果找到了这个元素，则赋值了新值（onlyIfAbsent=false），并退出循环
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            // 如果binCount不为0，说明成功插入了元素或者寻找到了元素
            if (binCount != 0) {
                // 如果链表元素个数达到了8，则尝试树化
                // 因为上面把元素插入到树中时，binCount只赋值了2，并没有计算整个树中元素的个数，所以不会重复树化
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                // 如果要插入的元素已经存在，则返回旧值
                if (oldVal != null)
                    return oldVal;
                // 退出外层大循环，流程结束
                break;
            }
        }
    }
    // 成功插入元素，元素个数加1（是否要扩容在这个里面）
    addCount(1L, binCount);
    // 成功插入元素返回null
    return null;
}

put操作总结：

做插入操作时，首先进入乐观锁，在乐观锁中判断容器是否初始化， 如果没初始化则初始化容器；如果已经初始化，则判断该hash位置的节点是否为空， 如果为空，则通过CAS操作进行插入。 如果该节点不为空，再判断容器是否在扩容中，如果在扩容，则帮助其扩容。如果没有扩容，则进行最后一步，先加锁，然后找到hash值相同的那个节点(hash冲突)， 循环判断这个节点上的链表，决定做覆盖操作还是插入操作。 循环结束，插入完毕。

• 首先会判断 key、value是否为空，如果为空就抛异常；
• 接着会判断容器数组是否为空，如果为空就初始化数组；
• 进一步判断，要插入的元素f，在当前数组下标是否第一次插入、即该hash位置的节点是否为空，如果是就通过 CAS 方式插入；
• 如果不为空，再接着判断f.hash == -1是否成立，如果成立，说明当前f是ForwardingNode节点，表示有其它线程正在扩容，则一起进行扩容操作；
• 其他的情况，就是把新的Node节点按链表或红黑树的方式插入到合适的位置；
• 节点插入完成之后，接着判断链表长度是否超过8，如果超过8个，就将链表转化为红黑树结构；
• 最后，插入完成之后，进行扩容判断。

get方法

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    // 计算hash
    int h = spread(key.hashCode());
    // 判断数组是否为空，通过key定位到数组下标是否为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        // 如果第一个元素就是要找的元素，直接返回
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)
            // hash小于0，说明是树或者正在扩容
            // 使用find寻找元素，find的寻找方式依据Node的不同子类有不同的实现方式
            return (p = e.find(h, key)) != null ? p.val : null;
        // 遍历整个链表寻找元素
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

步骤如下：

• 判断数组是否为空，通过key定位到数组下标是否为空；
• 判断node节点第一个元素是不是要找到，如果是直接返回；
• 如果是红黑树结构，就从红黑树里面查询；
• 如果是链表结构，循环遍历判断。

ConcurrentHashMap的get()方法没有加synchronized锁，为什么可以不加锁？因为table有volatile关键字修饰，保证每次获取值都是最新的。

【Hashtable的get(Object key)方法加了synchronized锁，性能较差】

remove方法

public V remove(Object key) {
    // 调用替换节点方法
    return replaceNode(key, null, null);
}

final V replaceNode(Object key, V value, Object cv) {
    // 计算hash
    int hash = spread(key.hashCode());
    // 循环遍历数组
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        //校验参数
        if (tab == null || (n = tab.length) == 0 ||
                (f = tabAt(tab, i = (n - 1) & hash)) == null)
            break;
        else if ((fh = f.hash) == MOVED)
            // 如果正在扩容中，协助扩容
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 标记是否处理过
            boolean validated = false;
            //用 synchronized 同步锁，保证并发时元素移除安全
            synchronized (f) {
                // 再次验证当前tab元素是否被修改过
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        // fh>=0表示是链表节点
                        validated = true;
                        // 遍历链表寻找目标节点
                        for (Node<K,V> e = f, pred = null;;) {
                            K ek;
                            if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                            (ek != null && key.equals(ek)))) {
                                V ev = e.val;
                                if (cv == null || cv == ev ||
                                        (ev != null && cv.equals(ev))) {
                                    oldVal = ev;
                                    if (value != null)
                                        e.val = value;
                                    else if (pred != null)
                                        pred.next = e.next;
                                    else
                                        setTabAt(tab, i, e.next);
                                }
                                break;
                            }
                            pred = e;
                            // 遍历到链表尾部还没找到元素，跳出循环
                            if ((e = e.next) == null)
                                break;
                        }
                    }
                    else if (f instanceof TreeBin) {
                        // 如果是树节点
                        validated = true;
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> r, p;
                        // 遍历树找到了目标节点
                        if ((r = t.root) != null &&
                                (p = r.findTreeNode(hash, key, null)) != null) {
                            V pv = p.val;
                            if (cv == null || cv == pv ||
                                    (pv != null && cv.equals(pv))) {
                                oldVal = pv;
                                if (value != null)
                                    p.val = value;
                                else if (t.removeTreeNode(p))
                                    setTabAt(tab, i, untreeify(t.first));
                            }
                        }
                    }
                }
            }
            // 如果处理过，不管有没有找到元素都返回
            if (validated) {
                // 如果找到了元素，返回其旧值
                if (oldVal != null) {
                    // 如果要替换的值为空，元素个数减1
                    if (value == null)
                        addCount(-1L, -1);
                    return oldVal;
                }
                break;
            }
        }
    }
    // 没找到元素返回空
    return null;
}

步骤如下：

• 循环遍历数组，接着校验参数；
• 判断是否有别的线程正在扩容，如果是一起扩容；
• 用 synchronized 同步锁，保证并发时元素移除安全；
• 因为 check= -1，所以不会进行扩容操作，利用CAS操作修改baseCount值。

2.3 ConcurrentHashMap结构 jdk1.7-->jdk1.8

jdk1.7下的ConcurrentHashMap

它由多个 Segment 组合而成。Segment 本身就相当于一个 HashMap 对象。

同 HashMap 一样，Segment 包含一个 HashEntry 数组，数组中的每一个 HashEntry 既是一个键值对，也是一个链表的头节点。

单一的 Segment 结构如下：

像这样的 Segment 对象，在 ConcurrentHashMap 集合中有多少个呢？有 2 的 N 次方个，共同保存在一个名为 segments 的数组当中。

因此整个ConcurrentHashMap的结构如下：

可以说，ConcurrentHashMap 是一个二级哈希表。在一个总的哈希表下面，有若干个子哈希表。

它的核心属性

final Segment<K,V>[] segments;
transient Set<K> keySet;
transient Set<Map.Entry<K,V>> entrySet;

其中，Segment是它的一个内部类，主要组成如下：

static final class Segment<K,V> extends ReentrantLock implements Serializable {

	private static final long serialVersionUID = 2249069246763182397L;
	
	// 和 HashMap 中的 HashEntry 作用一样，真正存放数据的桶
	transient volatile HashEntry<K,V>[] table;
	
	transient int count;
	transient int modCount;
	transient int threshold;
	final float loadFactor;

	// ...
}

HashEntry也是一个内部类，主要组成如下：

static class HashEntry<K,V> {
    final int hash;
    final K key;
    volatile V value;
    volatile HashEntry<K,V> next;

    HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    //...
}

和 HashMap 的 Entry 基本一样，唯一的区别就是其中的核心数据如 value ，以及链表都是 volatile 修饰的，保证了获取时的可见性。

get方法

1. 为输入的Key做Hash运算，得到hash值。
2. 通过hash值，定位到对应的Segment对象
3. 再次通过hash值，定位到Segment当中数组的具体位置。

put方法

1. 为输入的Key做Hash运算，得到hash值。
2. 通过hash值，定位到对应的Segment对象
3. 获取可重入锁
4. 再次通过hash值，定位到Segment当中数组的具体位置。
5. 插入或覆盖HashEntry对象。
6. 释放锁。

高并发线程安全：Put 操作时，锁的是某个 Segment，其他线程对其他 Segment 的读写操作均不影响。因此解决了线程安全问题。

jdk1.8下的COncurrentHashMap

虽然 JDK1.7 中的 ConcurrentHashMap 解决了 HashMap 并发的安全性，但是当冲突的链表过长时，在查询遍历的时候依然很慢。因此JDK8有所改进：

（在 JDK1.8 中，HashMap 引入了红黑二叉树设计，当冲突的链表长度大于8时，会将链表转化成红黑二叉树结构，红黑二叉树又被称为平衡二叉树，在查询效率方面，又大大的提高了不少。）

1）结构改变

首先是结构上的变化，相比于 JDK1.7 中的 ConcurrentHashMap，JDK1.8 中 ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS + synchronized 来保证并发安全；数据结构跟jdk1.8中HashMap一样，数组+链表改为 数组+链表+红黑树，当冲突链表长度大于8时，会将链表转变成红黑树结构。

ConcurrentHashMap 中 synchronized 只锁定当前链表或红黑二叉树的首节点，只要节点 hash 不冲突，就不会产生并发，相比 JDK1.7 的 ConcurrentHashMap 效率又提升了 N 倍！

2）HashEntry 改为 Node

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
}

和 JDK7 的 HasEntry 作用相同，对 val 和 next 都用了 volatile 关键字，保证了可见性。

3）Put操作的变化

1. 根据 key 计算出 hashcode，然后开始遍历 table；
2. 判断是否需要初始化；
3. f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
4. 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
5. 如果都不满足，则利用 synchronized 锁写入数据。
6. 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

4）Get操作的变化

1. 根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
2. 如果是红黑树那就按照树的方式获取值。
3. 都不满足那就按照链表的方式遍历获取值。

为什么取消分段锁，分段锁有什么问题

• 分段锁内存开销大
• 锁粒度太小，经常涉及跨多个锁操作，性能太低（有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁）
• 扩容会牵扯到多个分段锁，并发操作复杂性太高

2.4 ConcurrentHashMap总结

底层数据结构：

• JDK1.7底层采用分段的数组+链表实现
• JDK1.8采用的数据结构跟HashMap1.8的结构一样，数组+链表+红黑树。

加锁的方式：

• JDK1.7采用Segment分段锁，底层使用的是ReentrantLock
• JDK1.8采用CAS添加新节点，采用synchronized锁定链表或红黑二叉树的首节点，相对Segment分段锁粒度更细，性能更好

JDK1.7

ConcurrentHashMap 采用分段锁策略，由多个 Segment 组合而成，其中 Segment 可以看成一个 HashMap， 不同点是 Segment 继承自 ReentrantLock，在操作的时候给 Segment 赋予了一个对象锁（Put 操作时，锁的是某个 Segment，其他线程对其他 Segment 的读写操作均不影响），从而保证多线程环境下并发操作安全。

ConcurrentHashMap 中每个Segment各自持有一把锁。在保证线程安全的同时降低了锁的粒度，让并发操作效率更高。

JDK1.8

相比于 JDK1.7 中的 ConcurrentHashMap，JDK1.8 中 ConcurrentHashMap 类取消了 Segment 分段锁，采用 CAS + synchronized 来保证并发安全；数据结构跟jdk1.8中HashMap一样，数组+链表改为 数组+链表+红黑树，当冲突链表长度大于8时，会将链表转变成红黑树结构。

ConcurrentHashMap 中 synchronized 只锁定当前链表或红黑二叉树的首节点，只要节点 hash 不冲突，就不会产生并发，相比 JDK1.7 的 ConcurrentHashMap 效率又提升了 N 倍。

3.HashMap与ConcurrentHashMap工作原理、区别、总结

3.1 HashMap与ConcurrentHashMap区别

• 是否线程安全：
  • HashMap不是线程安全的；
  • ConcurrentHashMap是线程安全的，通过 Segment分段锁--继承 ReentrantLock（JDK1.7重入锁）、CAS和synchronized(JDK1.8内置锁) 来进行加锁 ，保证线程安全
• 底层数据结构
  • HashMap：JDK1.8之前HashMap的结构为数组+链表，JDK1.8之后为数组+链表+红黑树；
  • ConcurrentHashMap：JDK1.8之前ConcurrentHashMap的结构为 Segment数组+数组+链表，JDK1.8之后为 数组+链表+红黑树（类似于JDK1.8版本的HashMap）。

3.2 工作原理

3.2.1 HashMap

HashMap的工作原理、底层数据结构 可以查看 Java面试题：ArrayList底层实现原理、HashMap的实现原理、HashMap的jdk1.7和jdk1.8有什么区别

HashMap的数据结构： 底层使用hash表数据结构，即数组和链表或红黑树。jdk1.7使用的是 数组+链表，jdk1.8 当链表长度大于阈值（默认为8）并且数组长度达到64时 会转换为红黑树

初始容量：HashMap 的初始容量是 0，这是一种懒加载机制，直到第一次 put 操作才会初始化数组大小，默认大小是 16。

扩容逻辑：

HashMap 使用的是拉链法来解决散列冲突，扩容并不是必须的，但是不扩容的话会造成拉链的长度越来越长，导致散列表的时间复杂度会倾向于 O(n) 而不是 O(1)。

HashMap 扩容的触发时机出现在元素个数超过阈值（容量 * loadFactor）的时候时，会将集合的一维数组扩大一倍，然后重新计算每个元素的位置。

• 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
• 存储时，如果出现hash值相同的key，此时有两种情况。
  • 如果key相同，则覆盖原始值；
  • 如果key不同（出现冲突），则将当前的key-value放入链表或红黑树中
• 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。

注意：链表的长度大于8 且 数组长度大于64转换为红黑树

3.2.2 ConcurrentHashMap

JDK1.7

ConcurrentHashMap 采用分段锁策略，由多个 Segment 组合而成，其中 Segment 可以看成一个 HashMap， 不同点是 Segment 继承自 ReentrantLock，在操作的时候给 Segment 赋予了一个对象锁（Put 操作时，锁的是某个 Segment，其他线程对其他 Segment 的读写操作均不影响），从而保证多线程环境下并发操作安全。

ConcurrentHashMap 中每个Segment各自持有一把锁。在保证线程安全的同时降低了锁的粒度，让并发操作效率更高。

JDK1.8

相比于 JDK1.7 中的 ConcurrentHashMap，JDK1.8 中 ConcurrentHashMap 类取消了 Segment 分段锁，采用 CAS + synchronized 来保证并发安全；数据结构跟jdk1.8中HashMap一样，数组+链表改为 数组+链表+红黑树，当冲突链表长度大于8时，会将链表转变成红黑树结构。

ConcurrentHashMap 中 synchronized 只锁定当前链表或红黑二叉树的首节点，只要节点 hash 不冲突，就不会产生并发，相比 JDK1.7 的 ConcurrentHashMap 效率又提升了 N 倍。

细节如下：

底层数据结构：

• JDK1.7底层采用分段的数组+链表实现
• JDK1.8采用的数据结构跟HashMap1.8的结构一样，数组+链表+红黑树。

加锁的方式：

• JDK1.7采用Segment分段锁，底层使用的是ReentrantLock
• JDK1.8采用CAS添加新节点，采用synchronized锁定链表或红黑二叉树的首节点，相对Segment分段锁粒度更细，性能更好

4.HashMap与Hashtable的区别

Hashtable和HashMap都是 基于hash表实现的K-V结构的集合，Hashtable是jdk1.0引入的一个线程安全的集合类，内部使用数组+链表的形式来实现

从功能特性的角度来说

1、Hashtable是线程安全的（HashTable 对每个方法都增加了 synchronized），而HashMap不是

2、HashMap的性能要比Hashtable更好，因为Hashtable采用了全局同步锁来保证安全性，对性能影响较大

从内部实现的角度来说

1）Hashtable使用数组加链表，HashMap JDK1.7数组+链表、JDK1.8 数组+链表+红黑树

2）HashMap初始容量是16，Hashtable初始容量是11

3）HashMap可以使用null作为key；而Hashtable不允许 null 作为 Key，会抛出NullPointerException异常

他们两个的key的散列算法不同：Hashtable直接是使用key的hashcode对数组长度取模；而HashMap对key的hashcode做了二次散列，从而避免key的分布不均匀影响到查询性能

5.HashMap、Hashtable、ConcurrentHashMap区别

HashMap、Hashtable、ConcurrentHashMap都是 基于hash表实现的K-V结构的集合，在线程安全、底层数据结构方面有所区别

• HashMap：；线程不安全，因为HashMap中操作都没有加锁，因此在多线程环境下会导致数据覆盖之类的问题，所以，在多线程中使用HashMap是会抛出异常的
• Hashtable：线程安全，但是Hashtable只是单纯的在添加put、删除remove、查询get方法上加synchronized，保证插入时阻塞其他线程的插入操作。虽然安全，但因为设计简单，所以性能低下（HashMap的性能要比Hashtable更好，因为Hashtable采用了全局同步锁来保证安全性，对性能影响较大）
• ConcurrentHashMap：线程安全，ConcurrentHashMap并非锁住整个方法，而是通过原子操作和局部加锁的方法保证了多线程的线程安全，且尽可能减少了性能损耗。Segment分段锁--继承 ReentrantLock（JDK1.7重入锁）、CAS和synchronized(JDK1.8内置锁)

6.为什么 HashMap 采用拉链法而不是开放地址法？

Java 给予 HashMap 的定位是一个相对通用的散列表容器，它应该在面对各种输入的时候都表现稳定。而开发地址法相对来说容易出现数据堆积，在数据量较大时可能出现连续冲突的情况，性能不够稳定。

我们可以举个反例，在 Java 原生的数据结构中，也存在使用开放地址法的散列表 —— 就是 ThreadlLocal。因为项目中不会大量使用 ThreadLocal 线程局部存储，所以它是一个小规模数据场景，这里使用开发地址法是没问题的。

7.Map总结

参考 黑马程序员相关视频与笔记、HashMap源码分析 —— 一篇文章搞定HashMap面试、HashMap为什么线程不安全、一文彻底弄懂ConcurrentHashMap，轻松应对面试官！、深入浅出ConcurrentHashMap详解、HashMap与ConcurrentHashMap工作原理、区别和总结