HashMap底层实现原理

数据结构：

HashMap 的底层实现原理主要依赖于 数组 + 链表 + 红黑树 的结构。

1、数组: HashMap 最底层是一个数组，称为 table，它存放着键值对。

2、链表: 当多个键映射到数组的同一个位置时，会形成一个链表。

3、红黑树: 当链表长度超过阈值（默认 8）时，链表会转换为红黑树，以提高查找效率。

工作流程:

1、当插入一个键值对时，会根据键的 hashCode 计算出该键在数组中的位置 index = (n - 1) & hash (n 是数组长度)。

2、如果该位置为空，直接插入该键值对。

3、如果该位置已有元素，则根据 key 的 equals 方法判断是否已有相同 key 的键值对。

• 如果已存在，则替换该键值对。
• 如果不存在，则将新键值对添加到链表的末尾。

4、当链表长度超过阈值时，会将链表转换为红黑树，以提高查找效率。

源码解析(java 8)

// HashMap 的核心方法 put
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// putVal 方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node p; int n, i;
    // 如果 table 数组为空，则初始化一个默认大小的数组
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算 key 在数组中的位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 如果该位置已有元素，则根据 key 的 equals 方法判断是否已有相同 key 的键值对
    else {
        Node e; K k;
        // 如果 key 已存在，则替换该键值对
        if ((k = p.key) == key || (key != null && key.equals(k)))
            e = p;
        // 如果 key 不存在，则根据 key 的 hashCode 判断是否需要使用红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(hash, key, value);
        else {
            // 如果链表长度超过阈值，则将链表转换为红黑树
            for (e = p; e.next != null; e = e.next) {
                if ((k = e.next.key) == key || (key != null && key.equals(k)))
                    break;
            }
            // 如果 key 不存在，则将新键值对添加到链表的末尾
            if (e.next == null)
                e.next = newNode(hash, key, value, null);
            else
                e.next = new Node<>(hash, key, value, e.next);
            // 如果链表长度超过阈值，则将链表转换为红黑树
            if (++size > threshold)
                resize();
        }
        if (e != null) {
            V oldValue = e.value;
            e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 如果 table 数组没有被初始化，则初始化一个默认大小的数组
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

使用注意事项

1. 避免使用 null 作为 key: 由于 HashMap 使用 equals 方法比较 key，如果 key 为 null，则可能会导致不可预料的结果。
2. 注意 key 的 hashCode 方法: hashCode 方法对于 HashMap 的效率至关重要，如果 hashCode 方法实现不当，会导致性能下降。
3. 理解容量和加载因子: 容量指的是 HashMap 数组的大小，加载因子指的是 HashMap 允许的填充率。容量和加载因子会影响 HashMap 的性能，需要根据实际情况进行调整。
4. 了解底层实现机制: 了解 HashMap 的底层实现机制有助于更好地理解其行为和使用方式。
5. 选择合适的线程安全方案: 对于多线程环境，需要选择合适的线程安全方案来保证数据一致性。HashMap 本身不是线程安全的，在多线程环境下可能会出现数据一致性问题,多线程场景可以考虑ConcurrentHashMap、synchronizedMap

synchronizedMap

核心原理: 通过对 HashMap 进行包装，在所有方法上添加 synchronized 锁，来实现线程安全性。

public static  Map synchronizedMap(Map m) {
    return new SynchronizedMap<>(m);
}

private static class SynchronizedMap
        implements Map, Serializable {

    private final Map m;  // Backing Map
    private final Object mutex = new Object();

    SynchronizedMap(Map m) {
        if (m == null)
            throw new NullPointerException();
        this.m = m;
    }
    ... // 所有方法都被 synchronized 修饰
}

总结：

• 性能问题: 所有方法都加锁，会导致性能瓶颈，尤其是高并发情况下。
• 粒度粗: 整个 HashMap 对象都被锁住，任何操作都会阻塞其他线程。
• 低并发场景 简单场景，不需要太高的性能要求。

ConcurrentHashMap

• 核心原理: 使用分段锁机制，将 HashMap 分成多个段，每个段都有独立的锁。

public class ConcurrentHashMap extends AbstractMap
        implements ConcurrentMap, Serializable {
    // Segment 数组，每个 Segment 都是一个 HashMap
    final Segment[] segments;

    // put 方法示例
    public V put(K key, V value) {
        Segment s;
        // 获取 key 对应的 Segment
        if ((s = segmentFor(hash(key))) == null)
            // Segment 为 null 时，需要初始化 Segment
            s = ensureSegment(hash(key));
        // 在 Segment 上加锁，进行 put 操作
        return s.put(key, value, false);
    }

    // Segment 类，继承自 ReentrantLock
    static final class Segment extends ReentrantLock implements Serializable {
        final HashMap table;
        ... // 其他方法，例如 put、get 等
    }
}

总结：

• 性能提升: 允许多个线程同时访问不同的段，提高并发性能。
• 细粒度锁: 每个段独立加锁，避免了对整个 HashMap 加锁，减少了锁竞争
• 
  
• ConcurrentHashMap 并不完全保证数据一致性，它允许在不同线程中同时修改同一个键值对，但最终结果可能是不可预测的。
• 如果需要完全保证数据一致性，可以使用其他线程安全的数据结构，例如 Hashtable 或 TreeMap。

资料参考

Java8的HashMap详解
https://blog.csdn.net/login_sonata/article/details/76598675

官方文档:
https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

HashMap实现原理分析(源码分析，ReHash，扩容机制)
https://blog.csdn.net/qq_35995514/article/details/103630107