编程洪同学

模式切换

Map 集合 ​

Map 集合是一种用于存储键值对（key-value pairs）的数据结构。Map 接口属于 Java 集合框架（Java Collections Framework）的一部分，提供了一种将对象存储为键值对的方式，其中每个键都是唯一的，并且每个键都映射到一个值。Map 接口的实现类有 HashMap、LinkedHashMap、TreeMap、Hashtable 等。

Map 接口 ​

Map 接口定义了一些核心的方法用于操作键值对：

  • V put(K key, V value)：将指定的键值对存入 Map 中。如果 Map 之前包含了一个该键的映射，则旧值被新值替换。
  • V get(Object key)：返回指定键所映射的值，如果此 Map 不包含该键的映射，则返回 null。
  • V remove(Object key)：从 Map 中移除指定键的键值对，并返回与该键关联的值，如果该键不存在于 Map 中，则返回 null。
  • boolean containsKey(Object key)：检查 Map 是否包含指定的键。
  • boolean containsValue(Object value)：检查 Map 是否将一个或多个键映射到指定值。
  • int size()：返回 Map 中的键值对的数量。
  • boolean isEmpty()：检查 Map 是否为空。
  • Set<K> keySet()：返回 Map 中所有键的视图。
  • Collection<V> values()：返回 Map 中所有值的视图。
  • Set<Map.Entry<K, V>> entrySet()：返回 Map 中所有键值对（键-值映射关系）的视图。

25030509.png

图 Map 接口中提供的方法

Map 接口的常见实现类：

实现类底层数据结构线程安全性适用场景
HashMap哈希表（数组 + 链表 + 红黑树）非线程安全高效存取
TreeMap红黑树非线程安全有序键存储
LinkedHashMap哈希表 + 双向链表非线程安全维护插入顺序
Hashtable哈希表线程安全（已不推荐）需要线程安全

HashMap ​

HashMap 是基于哈希表的数据结构，用于存储键值对。其底层数据结构的设计非常巧妙，兼顾了查询效率和空间利用率。

25030701.png

图 HashMap 类的继承关系

25030703.png

图 HashMap 类中提供的构造方法

数据结构 ​

下方罗列了 HashMap 类中的几个重要的属性：

  • DEFAULT_INITIAL_CAPACITY：默认的初始容量。必须是 2 的幂次方。
    java
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  • MAXIMUM_CAPACITY：最大容量。必须是 2 的幂次方且小于等于 1 << 30。
    java
    static final int MAXIMUM_CAPACITY = 1 << 30;
  • DEFAULT_LOAD_FACTOR：默认的加载因子。用于扩容。
    java
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
  • TREEIFY_THRESHOLD：链表转红黑树的阈值。当链表长度超过 8 时，链表转换为红黑树。
    java
    static final int TREEIFY_THRESHOLD = 8;
  • UNTREEIFY_THRESHOLD：红黑树转链表的阈值。当红黑树节点数减少到 6 时，红黑树转换为链表。
    java
    static final int UNTREEIFY_THRESHOLD = 6;
  • MIN_TREEIFY_CAPACITY：最小树化容量。当哈希表的容量大于等于 64 时，才会进行树化操作。
    java
    static final int MIN_TREEIFY_CAPACITY = 64;

25030702.png

图 HashMap 类中的属性

HashMap 的底层数据结构主要包括三个部分：数组、链表和红黑树。

  • 数组

    作用：HashMap 内部维护了一个 Entry 数组（在 JDK 1.8 及以后版本中称为 Node 数组）。数组是 HashMap 的基础结构，用于存储键值对。每个数组元素被称为一个“桶”（Bucket）。

    java
    transient Node<K,V>[] table;

    Node 是存储数据的基本单元，它包含了键、值以及指向下一个节点的引用。

    java
    static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

    特性：数组的大小总是 2 的幂次方（如 16、32、64 等），这是为了优化哈希计算的性能。

    索引计算：通过键的哈希值计算数组索引，公式为 index = hash & (length - 1)，其中 hash 是键的哈希值，length 是数组的长度。由于数组长度是 2 的幂次方，length - 1 的二进制表示中所有位都是 1，这样可以保证哈希值在数组中的分布更加均匀。

  • 链表

    作用：当多个键的哈希值相同（发生哈希冲突）时，这些键值对会被存储在同一个桶中，形成链表。

    结构：链表中的每个节点（Entry）包含键、值以及指向下一个节点的引用。

    冲突解决：链表用于解决哈希冲突，保证每个键都能被唯一地映射到数组中的一个位置。

  • 红黑树

    引入版本：从 JDK 1.8 开始，HashMap 引入了红黑树结构。

    作用：当同一个桶中的链表长度超过一定阈值（默认为 8），且 HashMap 的容量大于 64 时，链表会被转换为红黑树。

    优化性能：红黑树是一种自平衡的二叉查找树，查找、插入和删除操作的时间复杂度为 O(log n)，相比链表的 O(n) 有显著提升。

    退化机制：当红黑树中的节点数减少到一定程度（默认为 6），红黑树会退化为链表，以节省空间。

    java
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
    boolean red;
}

哈希计算 ​

  • HashMap 使用哈希函数将键转换为哈希值，并通过哈希值与数组长度进行位运算（hash & (length - 1)），得到数组中的索引位置。
  • 哈希函数的设计旨在减少哈希冲突，使键值对在数组中均匀分布。
    java
    /**
 * 返回哈希码 h 的散列值。这个散列值必须与 HashMap 类的 hash 方法一致。
 *
 * @param key 键
 * @return  h 的散列值
 */
static final int hash(Object key) {
    int h;
    // 如果 key 为 null，则哈希值为 0；否则，哈希值为 key 的 hashCode() 方法返回值的异或操作。
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // h >>> 16 是为了增加哈希值的随机性
}

插入操作 ​

  • 当向 HashMap 中插入键值对时，首先计算键的哈希值，并确定在数组中的索引位置。
  • 如果该位置为空，则直接将键值对存储在数组中。
  • 如果该位置已有元素，则判断是否为同一个键：
    • 如果是同一个键，则更新值。
    • 如果不是同一个键，则判断当前桶中的数据结构：
      • 如果是链表，则将新节点添加到链表末尾。
      • 如果是红黑树，则按照红黑树的规则插入新节点。
  • 当链表长度超过阈值时，链表会转换为红黑树。
java
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

查找操作 ​

  • 当从 HashMap 中查找键时，首先计算键的哈希值，并确定在数组中的索引位置。
  • 如果该位置为空，则直接返回 null。
  • 如果该位置有元素，则判断是否为同一个键：
    • 如果是同一个键，则返回对应的值。
    • 如果不是同一个键，则判断当前桶中的数据结构：
      • 如果是链表，则遍历链表查找。
      • 如果是红黑树，则按照红黑树的规则查找。
java
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

扩容机制 ​

  • 当 HashMap 中的元素数量超过数组容量的负载因子（默认为 0.75）时，会触发扩容操作。
  • 扩容时，会创建一个新的数组，其容量是原数组的两倍。
  • 然后，将原数组中的数据重新计算索引，并迁移到新数组中。
java
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

TreeMap ​

TreeMap 基于红黑树（Red-Black Tree）数据结构，提供了一种有序的键值对存储方式。

数据结构 ​

TreeMap 的底层数据结构是红黑树，这是一种自平衡的二叉搜索树。红黑树通过旋转和重新着色操作，能够在插入和删除操作后保持平衡，从而保证 O(log n) 的操作效率。

红黑树具有以下特点：

  • 节点颜色：每个节点都有颜色，红色或黑色。
  • 根节点：根节点始终是黑色的。
  • 叶子节点：叶子节点都是黑色的（在实际实现中，叶子节点通常指向同一个空节点）。
  • 红色节点的子节点：红色节点的两个子节点都是黑色的（从根节点到叶子节点的路径上，不能有两个连续的红色节点）。
  • 路径上黑色节点数量：从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

插入操作 ​

插入操作的逻辑如下：

  • 检查根节点：如果红黑树的根节点为空，将新节点设为根节点，并将其颜色设为黑色。
  • 找到插入位置：根据键的比较结果（使用自然顺序或自定义比较器），在红黑树中找到新节点的插入位置。
  • 插入新节点：将新节点插入到红黑树中，并将其颜色设为红色。
  • 调整红黑树：插入新节点后，可能会破坏红黑树的性质。此时需要进行旋转和重新着色操作，以恢复红黑树的平衡。
java
public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }

    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    } else {
        if (key == null)
            throw new NullPointerException();

        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }

    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;

    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

删除操作 ​

删除操作的逻辑如下：

  • 找到要删除的节点：根据键的比较结果，在红黑树中找到要删除的节点。
  • 删除节点：从红黑树中删除该节点。
  • 调整红黑树：删除节点后，可能会破坏红黑树的性质。此时需要进行旋转和重新着色操作，以恢复红黑树的平衡。
java
public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    if (p.left == null || p.right == null)
        setEntry(p, null);
    else
        replaceEntry(p, successor(p));

    fixAfterDeletion(p);
}

查找操作 ​

查找操作的逻辑如下：

  • 从根节点开始遍历：从红黑树的根节点开始，根据键的比较结果（使用自然顺序或自定义比较器），遍历红黑树。
  • 找到目标节点：如果找到目标节点，则返回该节点的值；否则返回 null。
java
public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p == null ? null : p.value);
}

final Entry<K,V> getEntry(Object key) {
    if (comparator != null)
        return getEntryUsingComparator(key);

    if (key == null)
        throw new NullPointerException();

    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }

    return null;
}

LinkedHashMap ​

LinkedHashMap 继承自 HashMap，并在其基础上维护了一条双向链表。这一设计使得 LinkedHashMap 具备了保持元素顺序的能力，既可以按插入顺序迭代，也可以按访问顺序迭代。

数据结构 ​

LinkedHashMap 的底层数据结构结合了哈希表和双向链表。

  • 哈希表：继承自 HashMap，用于快速存取键值对。HashMap 的底层是一个数组，数组中的每个元素是一个链表或红黑树（在链表长度超过一定阈值时转换为红黑树），用于解决哈希冲突。
  • 双向链表：LinkedHashMap 在 HashMap 的基础上维护了一条双向链表。链表中的每个节点都包含指向前一个节点和后一个节点的引用，用于记录元素的插入顺序或访问顺序。

节点设计 ​

LinkedHashMap 的节点类 Entry 继承自 HashMap 的 Node 类，并额外增加了两个指针 before 和 after，用于维护双向链表。

java
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;

    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

构造方法 ​

LinkedHashMap 提供了多种构造方法，允许用户在创建实例时指定初始容量、加载因子和访问顺序。

java
// 无参构造，使用默认容量和加载因子，按插入顺序迭代
public LinkedHashMap() {
    super();
    accessOrder = false;
}

// 指定初始容量，按插入顺序迭代
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

// 指定初始容量和加载因子，按插入顺序迭代
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

// 指定初始容量、加载因子和访问顺序
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

// 使用另一个 Map 初始化
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

插入操作 ​

当向 LinkedHashMap 插入一个新的键值对时，操作分为两步：

  • 哈希表操作：将键值对插入到哈希表的相应位置，解决哈希冲突。
  • 双向链表操作：将新节点添加到双向链表的末尾。
java
void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

访问操作 ​

当访问 LinkedHashMap 中的元素时，操作也分为两步：

  • 哈希表操作：通过哈希表快速定位到键值对。
  • 双向链表操作：如果启用了访问顺序（accessOrder 为 true），则将访问的节点移动到双向链表的末尾。
java
void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

删除操作 ​

当从 LinkedHashMap 中删除一个键值对时，操作分为两步：

  • 哈希表操作：从哈希表中移除键值对。
  • 双向链表操作：将被删除的节点从双向链表中移除。
java
void afterNodeRemoval(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

迭代操作 ​

LinkedHashMap 的迭代操作通过双向链表实现，保证了元素的顺序。

  • 按插入顺序迭代：从头节点开始，依次访问每个节点，直到尾节点。
  • 按访问顺序迭代：从头节点开始，依次访问每个节点，直到尾节点。由于访问过的节点会被移动到链表尾部，因此按访问顺序迭代实际上会按照元素的最近访问顺序进行。

Hashtable ​

Hashtable 提供了一种线程安全的键值对存储方式。虽然在现代 Java 应用中，通常推荐使用 ConcurrentHashMap 来替代 Hashtable 以获得更好的并发性能，但 Hashtable 的底层数据结构及其逻辑设计仍然具有一定的学习价值。

数据结构 ​

Hashtable 的底层数据结构采用数组加链表的方式实现。具体来说：

  • 数组：Hashtable 内部维护了一个数组 table，用于存储键值对。数组的每个元素称为一个“桶”（Bucket），可以存储一个或多个键值对。
  • 链表：当多个键值对的哈希值相同（即发生了哈希冲突）时，这些键值对会被链接在同一个桶中，形成一条链表。链表的每个节点都包含键、值以及指向下一个节点的引用。

哈希函数 ​

Hashtable 使用哈希函数将键转换为数组的索引。哈希函数的设计目标是使不同键的哈希值尽可能均匀分布在数组的各个桶中，以减少哈希冲突的发生。

哈希冲突解决 ​

当发生哈希冲突时，Hashtable 采用链表法解决。即，将哈希值相同的键值对链接在同一个桶的链表中。这样，即使不同的键具有相同的哈希值，它们也可以通过链表的形式存储在同一个桶中，而不会发生覆盖。

扩容机制 ​

随着元素的增加，Hashtable 的负载因子（即实际存储的元素数量与数组容量的比值）会逐渐增大。当负载因子超过某个阈值（默认为 0.75）时，Hashtable 会进行扩容操作。

扩容的具体步骤如下：

  • 计算新容量：新容量是当前容量的两倍加一（即 2n+1）。这种扩容策略可以保持哈希表的性能，同时减少哈希冲突的发生。
  • 重新散列：扩容后，Hashtable 会将所有元素重新散列到新的数组中。具体做法是，使用新的容量重新计算每个键的哈希值，并将其插入到新的数组中相应的桶中。
  • 更新阈值：扩容后，Hashtable 会更新扩容阈值，以确保在负载因子再次达到阈值时能够进行下一次扩容。

线程安全 ​

Hashtable 是线程安全的，这是通过在其方法上使用 synchronized 关键字实现的。每个公共方法在执行时都会获取 Hashtable 的对象锁，从而确保同一时刻只有一个线程能够访问 Hashtable。

然而，这种全局锁的机制在高并发环境下可能会导致性能瓶颈。因此，在现代 Java 应用中，通常推荐使用 ConcurrentHashMap 来替代 Hashtable 以获得更好的并发性能。

java
// Hashtable 的内部类 Entry，用于表示链表节点
private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K,V> next;

    Entry(int h, K k, V v, Entry<K,V> n) {
        hash = h;
        key = k;
        value = v;
        next = n;
    }
}

// Hashtable 的构造函数，初始化容量和加载因子
public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: " + loadFactor);
    if (initialCapacity == 0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new Entry<?,?>[initialCapacity];
    threshold = (int) Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

// put 方法，用于插入键值对
public synchronized V put(K key, V value) {
    // 如果键或值为 null，则抛出 NullPointerException
    if (value == null) {
        throw new NullPointerException();
    }

    // 计算键的哈希值
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % table.length;

    // 遍历桶中的链表，查找是否存在相同的键
    for (Entry<?,?> e = table[index]; e != null; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

    // 如果桶为空或未找到相同的键，则添加新的键值对
    addEntry(hash, key, value, index);
    return null;
}

// addEntry 方法，用于在桶中添加新的键值对
private void addEntry(int hash, K key, V value, int index) {
    // 创建新的链表节点
    Entry<?,?> e = table[index];
    table[index] = new Entry<>(hash, key, value, e);
    count++;

    // 检查是否需要扩容
    if (count >= threshold) {
        rehash();
    }
}

// rehash 方法，用于扩容和重新散列
private void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // 计算新容量
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            return; // 不再扩容
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    // 重新散列
    modCount++;
    threshold = (int) Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    for (int i = oldCapacity; i-- > 0;) {
        for (Entry<K,V> old = (Entry<K,V>) oldMap[i]; old != null;) {
            Entry<K,V> e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>) newMap[index];
            newMap[index] = e;
        }
    }
    table = newMap;
}

ConcurrentHashMap ​

ConcurrentHashMap 是 Java 中一个线程安全的哈希表实现，底层采用数组（Node 数组）加链表（或红黑树）的数据结构。在 JDK 1.8 及以后的版本中，ConcurrentHashMap 取消了 JDK 1.7 中的 Segment 分段锁机制，转而使用更加细粒度的锁机制，以及 CAS（Compare-And-Swap）操作来提升并发性能。

25030704.png

图 ConcurrentHashMap 类的继承关系

数据结构 ​

  • Node 数组：
    • ConcurrentHashMap 使用一个 Node 数组来存储哈希表的数据。Node 数组中的每个元素都是一个 Node 对象，用于存储键值对。
    • Node 对象的结构如下：
      java
      static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;

    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }
}
    • hash：存储键的哈希值。
    • key：存储键。
    • val：使用 volatile 修饰，存储值，保证可见性。
    • next：使用 volatile 修饰，指向下一个 Node，形成链表。
  • 链表（或红黑树）：
    • 当哈希冲突发生时（即多个键的哈希值相同），这些键会被存储在同一哈希槽（Node 数组中的元素）对应的链表中。
    • 在 JDK 1.8 中，当链表长度超过一定阈值（默认为 8）时，链表会被转换为红黑树，以提高查找效率。红黑树的查找时间复杂度为 O(log n)，而链表的查找时间复杂度为 O(n)。

哈希函数 ​

ConcurrentHashMap 使用哈希函数将键映射到 Node 数组的索引位置。哈希函数通过对键的哈希值进行位移和异或操作，减少哈希冲突。

spread 方法通过对哈希值进行位移和异或操作，增加哈希值的随机性，减少哈希冲突。

java
static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}
static final int HASH_BITS = 0x7fffffff; // 31 bits

put 操作 ​

  • 当向 ConcurrentHashMap 中添加键值对时，首先计算键的哈希值，然后通过哈希函数找到对应的 Node 数组索引位置。
  • 如果该位置为空，则使用 CAS 操作直接将新的 Node 对象放入该位置。
  • 如果该位置不为空，则进入同步代码块，检查该位置的 Node 对象：
    • 如果该 Node 是链表头结点，则遍历链表查找是否存在相同的键。如果存在，则更新值；如果不存在，则将新的键值对添加到链表尾部。
    • 如果该 Node 是红黑树的根节点，则调用红黑树的插入方法。
  • 如果链表长度超过阈值，且数组长度大于 64，则将链表转换为红黑树。

以下是 putVal 方法的简化版源码示例：

java
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, newNode(hash, key, value, null)))
                break;
        } 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 = newNode(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;
}

get 操作 ​

  • 当从 ConcurrentHashMap 中获取值时，首先计算键的哈希值，然后通过哈希函数找到对应的 Node 数组索引位置。
  • 如果该位置的 Node 对象即为要查找的键，则直接返回其值。
  • 如果该位置的 Node 对象是一个链表头结点，则遍历链表查找是否存在相同的键。
  • 如果该位置的 Node 对象是一个红黑树的根节点，则在红黑树中查找。

get 方法的源码相对简单，主要逻辑如下：

java
public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        } else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

扩容机制 ​

  • 当 Node 数组的使用率达到一定阈值（默认为 75%）时，ConcurrentHashMap 会启动扩容操作。
  • 扩容时，会创建一个新的 Node 数组，其容量是原数组的两倍。
  • 然后，将原数组中的元素逐个迁移到新数组中。迁移过程中，使用 CAS 操作和同步代码块来保证线程安全。
  • 如果在扩容过程中有其他线程进行 put 操作，会帮助进行扩容，直到扩容完成。

扩容过程中涉及的一些关键属性和方法：

  • sizeCtl：用于控制扩容的变量。当 sizeCtl 为负数时，表示正在进行扩容。
  • transfer 方法：负责将原数组中的元素迁移到新数组中。
  • helpTransfer 方法：当其他线程发现正在扩容时，会调用此方法帮助进行扩容。
编程洪同学服务平台是一个广泛收集编程相关内容和资源，旨在满足编程爱好者和专业开发人员的需求的网站。无论您是初学者还是经验丰富的开发者，都可以在这里找到有用的信息和资料，我们将助您提升编程技能和知识。
CopyRight © 2018-2025 doc.bchtx.cn All Rights Reserved.
专业开发
高端定制
售后无忧
站内资源均为本站制作或收集于互联网等平台，如有侵权，请第一时间联系本站，敬请谅解！本站资源仅限于学习与参考，严禁用于各种非法活动，否则后果自行负责，本站概不承担！