HashMap底层实现原理

数据结构：

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

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

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

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

工作流程:

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

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

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

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

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

源码解析(java 8)

// HashMap 的核心方法 putpublic 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<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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;}

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

synchronizedMap

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

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {    return new SynchronizedMap<>(m);}private static class SynchronizedMap<K,V>        implements Map<K,V>, Serializable {    private final Map<K,V> m;  // Backing Map    private final Object mutex = new Object();    SynchronizedMap(Map<K,V> m) {        if (m == null)            throw new NullPointerException();        this.m = m;    }    ... // 所有方法都被 synchronized 修饰}

总结：

性能问题: 所有方法都加锁，会导致性能瓶颈，尤其是高并发情况下。粒度粗: 整个 HashMap 对象都被锁住，任何操作都会阻塞其他线程。低并发场景 简单场景，不需要太高的性能要求。ConcurrentHashMap核心原理: 使用分段锁机制，将 HashMap 分成多个段，每个段都有独立的锁。

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>        implements ConcurrentMap<K,V>, Serializable {    // Segment 数组，每个 Segment 都是一个 HashMap    final Segment<K,V>[] segments;    // put 方法示例    public V put(K key, V value) {        Segment<K,V> 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<K,V> extends ReentrantLock implements Serializable {        final HashMap<K,V> table;        ... // 其他方法，例如 put、get 等    }}

总结：

性能提升: 允许多个线程同时访问不同的段，提高并发性能。细粒度锁: 每个段独立加锁，避免了对整个 HashMap 加锁，减少了锁竞争

ConcurrentHashMap 并不完全保证数据一致性，它允许在不同线程中同时修改同一个键值对，但最终结果可能是不可预测的。如果需要完全保证数据一致性，可以使用其他线程安全的数据结构，例如 Hashtable 或 TreeMap。资料参考

Java8的HashMap详解

官方文档:

HashMap实现原理分析(源码分析，ReHash，扩容机制)