CCNAIVE

ConcurrentHashMap

2023/10/27

# ConcurrentHashMap

ConcurrentHashMap是Java中的一种线程安全的哈希表实现，它允许多个线程同时读取其中的数据，而不需要进行显式的锁定。它是HashMap的线程安全版本，提供了高并发性能和可靠的操作。ConcurrentHashMap的主要特点包括：

  1. 线程安全：ConcurrentHashMap是线程安全的，多个线程可以同时对其进行读取操作，而不会发生冲突。
  2. 分段锁：它将数据分成多个段（默认为16个），每个段内部都有自己的锁。这意味着不同的线程可以并行地访问不同的段，从而提高了并发性能。
  3. 支持高并发：由于分段锁的使用，ConcurrentHashMap在高并发环境下表现出色，允许多个线程同时执行读取和写入操作。
  4. 扩展性：ConcurrentHashMap支持动态扩展，当需要增加段的数量时，它可以自动扩展以提供更多的并发性能。
  5. 不允许null键或值：ConcurrentHashMap不允许存储null键或值，因为这可能会引起不确定的行为。

# 特点举例体现

# 线程不安全问题

使用 ConcurrentHashMap 可以避免多个线程同时写入或读取数据导致的线程不安全问题。

# HashMap不安全、ConCurrentHashMap安全的情况

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class HashMapVsConcurrentHashMapExample {

    public static void main(String[] args) {
        // 使用HashMap
        Map<String, Integer> hashMap = new HashMap<>();

        Runnable hashMapTask = () -> {
            for (int i = 0; i < 10000; i++) {
                String key = "key";
                if (hashMap.containsKey(key)) {
                    hashMap.put(key, hashMap.get(key) + 1);
                } else {
                    hashMap.put(key, 1);
                }
            }
        };

        // 使用ConcurrentHashMap
        Map<String, Integer> concurrentHashMap = new ConcurrentHashMap<>();

        Runnable concurrentHashMapTask = () -> {
            for (int i = 0; i < 10000; i++) {
                String key = "key";
                concurrentHashMap.merge(key, 1, Integer::sum);
            }
        };

        Thread thread1 = new Thread(hashMapTask);
        Thread thread2 = new Thread(hashMapTask);
        Thread thread3 = new Thread(concurrentHashMapTask);
        Thread thread4 = new Thread(concurrentHashMapTask);

        thread1.start();
        thread2.start();
        thread3.start();
        thread4.start();

        try {
            thread1.join();
            thread2.join();
            thread3.join();
            thread4.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("HashMap result: " + hashMap.get("key"));
        System.out.println("ConcurrentHashMap result: " + concurrentHashMap.get("key"));
    }
}

# ConcurrentHashMap 不保证原子性

  1. 线程安全的操作：ConcurrentHashMap 提供了线程安全的操作，意味着多个线程可以同时对其进行读取和写入操作，而不会导致数据损坏或不一致。这是因为 ConcurrentHashMap 内部采用了锁机制，分段锁，CAS 操作等，以确保多线程安全访问。
  2. 不保证原子性：虽然 ConcurrentHashMap 是线程安全的，但它并不保证多个线程同时操作相同键时的原子性。具体来说，ConcurrentHashMap 的某些操作可能不是原子的。在多线程环境下，如果多个线程同时操作相同的键，例如递增一个键的值，由于该操作不是原子的，就有可能导致竞争条件，即多个线程之间相互竞争修改相同键的值，这可能导致结果不确定或不符合预期。
  3. 要保证多个线程同时操作相同键的原子性，需要使用额外的同步机制，例如 synchronized 块或原子类（如 AtomicInteger）。这些机制可以确保对键的操作是原子的，不会发生竞争条件，从而获得正确的结果。
public static void main(String[] args) {
    final Map<String, Integer> map = new ConcurrentHashMap<>();

    Runnable task = () -> {
        for (int i = 0; i < 10000; i++) {
            // 多个线程同时向ConcurrentHashMap添加元素
            String key = "key";
            //这里引入synchronized来解决竞争条件
            //因为进行+1的操作是需要先取值、加一、赋值，ConcurrentHashMap提供了线程安全的操作，但是不能保证多个线程同时操作相同键时的原子性
            map.put(key, map.getOrDefault(key, 0) + 1);
        }
    };

    Thread thread1 = new Thread(task);
    Thread thread2 = new Thread(task);

    thread1.start();
    thread2.start();

    try {
        thread1.join();
        thread2.join();
    } catch (InterruptedException e) {
        e.printStackTrace();
    }

    // 打印最终结果
    System.out.println("Final value for 'key': " + map.get("key"));
}

# 如何解决ConcurrentHashMap不保证原子性

# 使用synchronized
String key = "key";
synchronized(key){
	map.put(key, map.getOrDefault(key, 0) + 1);
}
# 使用AtomicInteger
import java.util.concurrent.atomic.AtomicInteger;

public class SafeHashMapExample {

    public static void main(String[] args) {
        final AtomicInteger atomicValue = new AtomicInteger(0);

        Runnable task = () -> {
            for (int i = 0; i < 10000; i++) {
                atomicValue.incrementAndGet();
            }
        };

        Thread thread1 = new Thread(task);
        Thread thread2 = new Thread(task);

        thread1.start();
        thread2.start();

        try {
            thread1.join();
            thread2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        // 打印最终结果
        System.out.println("Final value: " + atomicValue.get());
    }
}
# 使用concurrentHashMap.merge(key, 1, Integer::sum); 安全的原子操作

# 并发修改异常问题

ConcurrentHashMap允许在遍历时修改映射，而不会引发ConcurrentModificationException` 异常。

# 数据不一致性问题

ConcurrentHashMap 提供了同步机制，确保多线程同时修改时数据一致性。

# 性能问题

ConcurrentHashMap 采用分段锁机制，可以在高并发情况下提供较好的性能。

# 死锁可能性问题

ConcurrentHashMap 的分段锁机制可以减少死锁的可能性，因为每个段独立加锁，减小了锁的竞争范围。

此问题不容易直接演示，因为 ConcurrentHashMap 的设计旨在降低死锁风险，但不保证绝对不会发生。在复杂应用中，需要注意死锁的可能性并谨慎设计。

# ConCurrentHashMap-put源码

 final V putVal(K key, V value, boolean onlyIfAbsent) {
        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 = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    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;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

CAS