深入剖析HashMap与ConcurrentHashMap内部原理及实现

一、HashMap关键属性与方法 在Java中，HashMap是一个基于哈希表的Map接口实现，它存储的内容是键值对，并且允许使用null作为键和值。HashMap的内部通过一个数组和链表（Java 8中引入红黑树优化链表过长的情况）来处理键的冲突。 关键属性包括： 1. int threshold; // 下一次扩容的阈值 2. final float loadFactor; // 负载因子，默认值是0.75 put()方法实现： 1. 初始化或扩容检查：如果哈希表的数组为空或长度为0，则调用resize()方法初始化数组。resize()方法在首次插入时创建一个默认容量（16）的数组。 2. 计算桶位置并插入新节点：通过(n - 1) & hash计算键的桶索引（等价于取模运算，但更高效）。如果该位置为空，则直接插入新节点。 3. 处理哈希冲突： - 首节点匹配：检查桶的第一个节点是否与待插入的key相同（哈希值和equals均匹配）。 - 红黑树插入：如果节点是TreeNode类型，则调用红黑树的插入方法putTreeVal。 - 链表遍历：遍历链表查找是否存在相同的key。如果未找到，在链表尾部插入新节点，并检查是否需要树化。 4. 树化条件：当链表长度达到TREEIFY_THRESHOLD（默认8）并且数组长度≥MIN_TREEIFY_CAPACITY（64）时，链表转换为红黑树；否则，优先扩容。 5. 更新已存在的键值对：如果找到相同key的节点，根据onlyIfAbsent参数决定是否更新值，并返回旧值。 6. 扩容与回调：新增节点后，检查总节点数是否超过扩容阈值threshold，若超过则调用resize()方法扩容。afterNodeInsertion和afterNodeRemoval方法用于插入和删除节点后的回调。 get()方法实现：通过key的哈希值计算出数组中的桶位置，然后在这个位置的链表中进行遍历，查找是否存在与key相等的节点。 扩容机制（resize）：当元素数量超过阈值threshold时，会进行数组的扩容操作，这个操作会创建一个新的数组，并将旧数组中的元素重新计算索引后放入新数组中。 二、ConcurrentHashMap并发实现 ConcurrentHashMap是线程安全的HashMap实现，它通过分段锁（Segmentation Locking）来实现高并发访问。在Java 8及以后版本中，ConcurrentHashMap基于数组+链表+红黑树的实现方式，已经不再使用分段锁，而是采用了一种新的并发策略。 关键属性包括： - volatile Node<K,V>[] table; // 存储数据的数组 - volatile int sizeControl; // 控制大小和扩容的变量 put()方法实现： 1. 计算桶位置并尝试插入新节点。 2. 如果该位置为空，则直接使用CAS（Compare-And-Swap）操作设置节点。 3. 如果该位置已存在节点，则遍历链表或红黑树，找到key相同的节点并更新值，或者在链表尾部插入新节点。 4. 使用casTabAt()方法增加元素数量addCount()。 5. 如果需要扩容，则调用transfer()方法进行扩容操作。 为什么ConcurrentHashMap不允许null键值？ ConcurrentHashMap不允许null键值是因为它要区别对待键为null的情况和键不存在的情况。在多线程环境下，无法判断null值是由哪个线程插入的，这可能导致并发问题。因此，ConcurrentHashMap将null键值的引入视为API设计上的一个错误。 HashMap和ConcurrentHashMap的哈希扰动的区别： HashMap在进行哈希计算时使用的是hash方法，而ConcurrentHashMap使用的是spread方法。spread方法加入了更多的位运算，可以更好地减少哈希冲突，同时在高位进行异或运算，有助于提高散列分布的均匀性。 获取某个桶tabAt()方法： ConcurrentHashMap中的tabAt方法用于获取数组中某个索引位置的元素，这一过程是原子的，确保了线程安全。 典型问题示例： 1. 线程安全问题：在多线程环境下，多个线程同时进行put操作时可能会引起数据不一致的问题，ConcurrentHashMap通过分段锁或CAS操作解决这些问题。 2. 链表转红黑树的阈值：在Java 8中，当链表长度大于8且数组长度大于64时，链表会转化为红黑树以优化性能，这是一个平衡链表长度和红黑树性能的选择。 3. 高并发下的扩容问题：扩容是一个复杂且耗时的操作，ConcurrentHashMap设计了一种平滑扩容的机制，尽量减少扩容对性能的影响。