【昕宝爸爸小模块】ConcurrentHashMap为什么不允许null值

一、?典型解析

我们知道，ConcurrentHashMap在使用时，和HashMap有一个比较大的区别，那就是HashMap中，null 可以作为键或者值都可以。而在ConcurrentHashMap中，key和value都不允许为null。

那么，为什么呢? 为啥ConcurrentHashMap要设计成这样的呢?

关于这个问题，其实最有发言权的就是ConcurrentHashMap的作者——Doug Lea

他自己曾经出面解释过这个问题，内容如下 http://cs.oswego.edu/pipermail/concurrencyinterest/2006-May/002485.html ，原文地址已经打不开了，大家将就着看一下截图吧)

我简单解释一下这张图的意思：

ConcurrentMap(如ConcurrentHashMap、ConcurrentSkipListMap) 不允许使用null值的主要原因是，在非并发的Map中(如HashMap)，是可以容忍模糊性 (二义性)的，而在并发Map中是无法容忍的。

假如说，所有的Map都支持null的话，那么map.get(key) 就可以返回 null，但是，这时候就会存在一个不确定性，当你拿到 null 的时候，你是不知道他是因为本来就存了一个 null 进去还是说就是因为没找到而返回了 null 。

在HashMap中，因为它的设计就是给单线程用的，所以当我们map.get(key)返 null 的时候，我们是可以通过 map.contains(key)检查来进行检测的，如果它返回true，则认为是存了一个null，否则就是因为没找到而返回了null。

但是，像 ConcurrentHashMap ，它是为并发而生的，它是要用在并发场景中的，当我们 map.get(key) 返回 null 的时候，是没办法通过 map.contains(key) 检查来准确的检测，因为在检测过程中可能会被其他线程所修改，而导致检测结果并不可靠。

So，为了让 ConcurrentHashMap 的语义更加准确，不存在二义性的问题，他就不支持 null 。

二、?要实现一个HashMap怎么做

2.1 ?需要考虑以下几个方面

1. 数据结构选择：HashMap基于键值对（key-value pair）的数据结构，因此你需要选择一种合适的数据结构来存储键值对。常用的数据结构有数组、链表、红黑树等。
   
   
2. 哈希函数设计：HashMap通过哈希函数将键映射到桶（bucket）中，因此你需要设计一个高效的哈希函数，以保证键的分布均匀和查询性能。
   
   
3. 桶的设计：为了提高查询性能，你需要为每个桶设计合适的数据结构，如链表、红黑树等。桶的数量需要根据实际需求和内存大小进行权衡。
   
   
4. 同步机制：如果你想让你的HashMap线程安全，你需要考虑使用同步机制，如使用synchronized关键字或ReentrantLock等。
   
   
5. 扩容机制：当HashMap中的元素数量超过一定阈值时，需要考虑进行扩容操作。扩容时需要重新计算哈希函数，并调整桶的数量和数据结构。

实现一个HashMap需要综合考虑数据结构、哈希函数、桶的设计、同步机制和扩容机制等多个方面。如果你不熟悉这些概念和技术，建议使用Java标准库提供的HashMap实现，或者使用其他成熟的第三方库。

2.2 ?基于数组和链表的HashMap实现Demo

内有逐行注释，就不做解释了！

/**
*  @author xinbaobaba
*/
static class Entry<K,V> implements Map.Entry<K,V> {  
    final K key;  
    V value;  
    Entry<K,V> next;  
    // ... 构造方法和其他方法  
}  
  
// 如果要实现红黑树，还需要定义TreeNode，它是Entry的子类，并且包含红黑树所需的额外字段和方法。  
// 这里为了简化，我们省略TreeNode的定义。  
  
// HashMap的主类定义  
public class HashMap<K,V> {  
    // 初始容量  
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    // 最大容量  
    static final int MAXIMUM_CAPACITY = 1 << 30;  
    // 默认加载因子  
    static final float DEFAULT_LOAD_FACTOR = 0.75f;  
    // 桶数组  
    transient Entry<K,V>[] table;  
    // 存放具体元素的数量  
    transient int size;  
    // 扩容阈值，当size大于threshold就一定会扩容  
    int threshold;  
    // 加载因子  
    final float loadFactor;  
  
    // 构造函数  
    public HashMap(int initialCapacity, float loadFactor) {  
        // 参数校验  
        // 初始化桶数组  
        // 初始化阈值  
        // 初始化加载因子  
    }  
  
    // 哈希函数，可以自定义实现，也可以使用JDK中的实现  
    static final int hash(Object key) {  
        int h;  
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  
    }  
  
    // 根据key的哈希值计算数组索引  
    static int indexFor(int h, int length) {  
        return h & (length - 1);  
    }  
  
    // 实现put方法  
    public V put(K key, V value) {  
        // 如果table为空或者长度为0，就初始化  
        if (table == null || size == 0) {  
            inflateTable(threshold);  
        }  
        // 如果key为null，就放到table[0]的位置  
        if (key == null)  
            return putForNullKey(value);  
        int hash = hash(key);  
        int i = indexFor(hash, table.length);  
        // 遍历链表，如果key已存在，就覆盖掉value  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;  
            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
        // 如果key不存在，就添加到链表的头部  
        modCount++;  
        addEntry(hash, key, value, i);  
        return null;  
    }  
  
    // 添加新的键值对到链表中  
    void addEntry(int hash, K key, V value, int bucketIndex) {  
        // 如果size大于阈值，就扩容  
        if ((size >= threshold) && (null != table[bucketIndex])) {  
            resize(2 * table.length);  
            hash = (null != key) ? hash(key) : 0;  
            bucketIndex = indexFor(hash, table.length);  
        }  
  
        createEntry(hash, key, value, bucketIndex);  
    }  
  
    // 创建新的Entry并添加到桶中  
    void createEntry(int hash, K key, V value, int bucketIndex) {  
        Entry<K,V> e = table[bucketIndex];  
        // 将新创建的 Entry 放入桶中，并指向原来的 Entry  
        table[bucketIndex] = new Entry<>(hash, key, value, e);  
        size++;  
    }  
  
    // 扩容方法  
    void resize(int newCapacity) {  
        // ... 省略扩容逻辑  
    }  
  
    // 其他方法，如get、remove等  
    // ...  
}

2.3 ?扩容后如何解决链表长度过长的问题

扩容后解决链表长度过长的问题主要有以下两种方法：

1. 树化：当链表长度大于8并且数组长度大于等于64时，可以将链表转为红黑树。红黑树查找元素的时间复杂度为O(logN)，而链表查找元素的时间复杂度为O(N)。这样可以避免在链表超长时性能下降，树化应当是偶然情况。

2. 重新计算哈希值：如果所有元素的哈希值一样，扩容则不能缩短链表长度提高查询效率。这时需要重新计算哈希值，以减少哈希冲突，从而缩短链表长度。

当然，除了上面的树化 和 重新计算哈希值的方法，还有一些其他方法可以解决扩容后链表长度过长的问题：

1. 调整数组长度：如果数组长度过短，可能导致哈希冲突过多，链表长度过长。可以适当增加数组长度，减少哈希冲突，从而缩短链表长度。
   
   

2. 使用开放地址法：当发生哈希冲突时，可以使用开放地址法（例如线性探测）来处理。这种方法可以在发生冲突时重新计算哈希值，减少链表长度。

3. 使用再哈希：在某些情况下，可以使用再哈希技术，即在计算哈希值时使用多个哈希函数，以获得更好的分布。这有助于减少链表长度。
   
   

4. 链表合并：在扩容时，可以将相邻的链表合并，以减少链表数量。这种方法适用于链表长度差异较大的情况。

以上可以结合使用，以更好地解决扩容后链表长度过长的问题。具体选择哪种方法取决于具体的应用场景和数据特点。

注意：这些技术通常在需要处理大量数据和复杂数据结构的场景下比较常见，例如数据库索引、搜索引擎、缓存系统等。在这些场景下，需要快速地查找、插入和删除数据，而链表和哈希表等数据结构可以提供高效的性能。通过使用这些技术，可以有效地解决数据量大、哈希冲突多等问题，提高系统的性能和响应速度。

看一个案例，一段代码使用哈希表和链表来存储用户信息，并提供添加、删除和查找用户的方法：

import java.util.HashMap;  
import java.util.List;  
import java.util.Map;  
/**
*   @author xinbaobaba
*/  
public class UserService {  
	// 用户映射表，以用户ID为键，用户对象为值  
    private Map<String, User> userMap;  
    // 链表的头节点，用于存储用户ID的链表结构
    private ListNode head;  
  
    public UserService() {
    	// 初始化用户映射表   
        userMap = new HashMap<>(); 
         // 初始化链表头节点为空
        head = null;  
    }  
  
    public void addUser(User user) {
    	// 获取用户ID  
        String userId = user.getId();
        // 如果用户映射表中不存在该用户ID  
        if (!userMap.containsKey(userId)) {
        	// 将用户添加到映射表中  
            userMap.put(userId, user);
            // 如果链表为空  
            if (head == null) {
            	// 创建新的链表节点，并设置其为头节点    
                head = new ListNode(userId);  
            } 
			// 如果链表不为空
			else {
				// 从链表头节点开始遍历  
                ListNode curr = head;
                 // 遍历到最后一个节点前   
                while (curr.next != null) {
                	// 移动到下一个节点  
                    curr = curr.next;  
                }
                // 在最后一个节点后面添加新的节点  
                curr.next = new ListNode(userId);  
            }  
        }
		// 如果用户映射表中已存在该用户ID
		 else {
		 	//输出提示的信息  User already exists（用户已存在）
            System.out.println("User already exists.");  
        }  
    }  
  	// 删除用户的方法 （一样的道理，不逐行注释了）
    public void removeUser(String userId) {  
        if (userMap.containsKey(userId)) {  
            User removedUser = userMap.remove(userId);  
            ListNode removedNode = null;  
            if (head != null && head.val.equals(userId)) {  
                removedNode = head;  
                head = head.next;  
            } else {  
                ListNode curr = head;  
                while (curr != null && curr.next != null && curr.next.val.equals(userId)) {  
                    removedNode = curr.next;  
                    curr.next = curr.next.next;  
                }  
            }  
            if (removedNode != null) {  
                // do something with removedUser and removedNode, e.g., free memory or update related data structures  
            } else {  
                System.out.println("User not found.");  
            }  
        } else {  
            System.out.println("User not found.");  
        }  
    }  
    
  	 // 根据用户ID查找用户的方法  
    public User findUserById(String userId) {  
        if (userMap.containsKey(userId)) {  
            return userMap.get(userId);  
        } else {  
            return null; // or throw an exception if the user is required to exist  
        }  
    }  
    
    // 批量添加用户的方法（用于一次性添加多个用户） 
    public void addUsers(List<User> users) {  
        for (User user : users) {  
            addUser(user);  
        }  
    }  
     //remove 
    public void removeUsers(List<String> userIds) {  
        for (String userId : userIds) {  
            removeUser(userId);  
        }  
    }  
      
    public List<User> getAllUsers() {  
        List<User> users = new ArrayList<>();  
        ListNode curr = head;  
        while (curr != null) {  
            users.add(userMap.get(curr.val));  
            curr = curr.next;  
        }  
        return users;  
    }  
      
    public int getUserCount() {  
        return userMap.size();  
    }  
      
    // Other methods and attributes can be added here...  
}

三、?拓展知识仓

3.1 ?在多线程环境下如何保证数据的正确性和性能

在多线程环境下，要保证数据的正确性和性能，可以考虑以下几个方面：

1. 线程安全：选择线程安全的数据结构或使用同步机制，如synchronized关键字或ReentrantLock等，保证多个线程对数据的操作不会产生冲突或不一致。
   
   
2. 原子操作：对于关键的更新操作，使用原子操作，如AtomicInteger、AtomicBoolean等，保证操作的原子性，避免数据竞争和线程安全问题。
   
   
3. 乐观锁：使用乐观锁机制，如CAS（Compare-and-Swap）操作，在更新数据时比较版本号，只有当版本号一致时才进行更新，否则重试直到成功。
   
   
4. 数据同步：对于共享数据，使用同步机制进行数据同步，保证多个线程对数据的操作顺序一致，避免数据不一致问题。
5. 避免死锁：在实现多线程程序时，需要避免死锁情况的发生。可以采用一些策略来预防和解决死锁问题，如避免循环等待、按顺序获取锁、设置锁的超时时间等。
   
   
6. 合理使用锁粒度：根据实际情况选择合适的锁粒度，避免过度同步导致性能下降。可以考虑使用细粒度锁或分段锁等策略。
   
   
7. 性能优化：对于关键路径上的操作，需要进行性能优化，如使用缓存、减少锁的持有时间、使用低延迟的数据结构等。
   
   
8. 监控和调优：在多线程程序运行过程中，需要监控程序的性能指标和资源使用情况，及时发现和解决性能瓶颈和问题。

要保证数据的正确性和性能，需要综合考虑线程安全、原子操作、乐观锁、数据同步、避免死锁、合理使用锁粒度、性能优化和监控调优等方面。同时需要结合实际业务场景和需求进行权衡和优化。

3.2 ?那如何在多线程环境下进行乐观锁

在多线程环境下进行乐观锁，可以使用CAS（Compare-and-Swap）操作。CAS操作是一种原子性操作，用于在多线程环境中实现乐观锁。

CAS操作包含三个参数：内存位置V、预期的原值A和新值B。在执行CAS操作时，如果内存位置V的值等于预期原值A，则将内存位置V的值更新为新值B。如果内存位置V的值不等于预期原值A，则说明该内存位置V的值已经被其他线程修改过，此时不会进行更新操作，并且会返回一个失败的结果。

在Java中，可以使用 AtomicStampedReference类或 AtomicMarkableReference 类来实现乐观锁。这些类提供了compareAndSet()方法，该方法接受两个参数：预期的原值和新值。如果当前值与预期原值相匹配，则将当前值更新为新值，并返回true；否则，不做任何操作并返回false。

下面是一个简单的示例代码，演示如何在Java中使用AtomicStampedReference 类实现乐观锁：

import java.util.concurrent.atomic.AtomicStampedReference;

public class OptimisticLocker {
    private AtomicStampedReference<Integer> stampRef = new AtomicStampedReference<>(0, 0);

    public void increment() {
        int stamp = stampRef.getStamp(); // 获取当前时间戳
        int value = stampRef.getValue(); // 获取当前值
        int newValue = value + 1; // 计算新值
        int nextStamp = stamp + 1; // 计算下一个时间戳
        if (stampRef.compareAndSet(value, newValue, stamp, nextStamp)) {
            // 如果更新成功，则打印新值和时间戳
            System.out.println("New value: " + newValue + ", Stamp: " + nextStamp);
        } else {
            // 如果更新失败，则打印当前值和时间戳
            System.out.println("Current value: " + value + ", Stamp: " + stamp);
        }
    }
}

在上面的示例中，我们使用AtomicStampedReference类来存储一个整数值和一个时间戳。在increment()方法中，我们首先获取当前的时间戳和值，然后计算新值和下一个时间戳。接下来，我们使用compareAndSet()方法尝试更新值和时间戳。如果更新成功，则打印新值和时间戳；否则，打印当前值和时间戳。这样就可以实现乐观锁的效果。