基本结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 默认容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 默认最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子0.75 16*0.75 = 12 即容量为13时扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 树转化临界点8 链表容量为9时扩容
static final int TREEIFY_THRESHOLD = 8;
// 树退化临界点6 扩容时如果链表容量<=6,退化为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 树容量 转换为红黑树时，如果table长度小于64，扩容
static final int MIN_TREEIFY_CAPACITY = 64;

// 链表节点
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    ...
}

// 红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    ...

通用方法

hash(Object key) - 计算 hashcode

将 key 计算出来的 hashcode 和他的高位进行异或运算，这一步是一个散列运算，目的是为了减少哈希冲突，具体参考–>为什么 HashMap 的 hash 值要右移 16 位？

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

comparableClassFor(Object x) - 判断 x 是否实现 Compareble 接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Returns x's Class if it is of the form "class C implements
* Comparable<C>", else null.
*/
static Class<?> comparableClassFor(Object x) {
    // 判断x是否实现Compareble接口
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        // x是否为String类型
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        if ((ts = c.getGenericInterfaces()) != null) {
            // 遍历x实现的所有接口
            for (int i = 0; i < ts.length; ++i) {
                // 如果x实现了Comparable接口，则返回x的Class
                if (((t = ts[i]) instanceof ParameterizedType) &&
                    ((p = (ParameterizedType)t).getRawType() ==
                    Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) // type arg is c
                    return c;
            }
        }
    }
    return null;
}

compareComparables(Class<?> kc, Object k, Object x) - 获取 compareTo()比较结果

1
2
3
4
static int compareComparables(Class<?> kc, Object k, Object x) {
    return (x == null || x.getClass() != kc ? 0 :
            ((Comparable)k).compareTo(x));
}

tableSizeFor(int cap) - 将传入容量扩展为大于该数的 2 的幂（已经是 2 的幂返回原值）

1
2
3
4
5
6
7
8
9
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

中间的异或其实是对一个二进制数依次向右移位，然后与原值取或。其目的对于一个数字的二进制，从第一个不为 0 的位开始，把后面的所有位都设置成 1。

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

总结一下这三个构造方法就是：传入容量就将 threshold 设为传入容量处理后的结果否则不设置。传入负载因子就将负载因子设置为传入值否则使用默认负载因子。留一个问题？这三个构造方法都没有设置容量，到底在哪里设置的呢？

get(Object key) - get 方法

1
2
3
4
5
6
public V get(Object key) {
    Node<K,V> e;
    // 其实就是调用getNode()方法，找到就返回，不然就返回null
    // 通过这也能推测getOrDefault()方法就是将null替换为传入值。
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode(int hash, Object key) - 获取节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Implements Map.get and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 如果数组不为空且根据hash计算出的下标对应节点不为null，则开始查询
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // hash相同且key相等直接返回
        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;
}

getTreeNode(int h, Object k) - 获取树节点

1
2
3
4
5
final TreeNode<K,V> getTreeNode(int h, Object k) {
// root()方法其实就是递归获取树的根节点
// 根节点调用find()方法
    return ((parent != null) ? root() : this).find(h, k, null);
}

find(int h, Object k, Class<?> kc) - 红黑树中查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Finds the node starting at root p with the given hash and key.
* The kc argument caches comparableClassFor(key) upon first use
* comparing keys.
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    // 遍历红黑树
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        // 根据hashcode比较结果确定查找方向
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        // hashcode相等时判定key是否相同，相同就直接返回
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        // hashcode相同且key不等时，左子树为null则访问右子树，右子树为null则访问左子树
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        // 左右子树都不为null，则根据compareComparables()方法获取compareTo()比较结果确定返回方向
        else if ((kc != null ||
                (kc = comparableClassFor(k)) != null) &&
                (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        // 不能通过hashcode或者compareTo()方法时，先遍历右子树，找到结果就返回，否则才遍历左子树
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}

put(K key, V value) - 插入节点

HashMap的putVal方法

1
2
3
4
public V put(K key, V value) {
    // 调用putVal()方法
    return putVal(hash(key), key, value, false, true);
}

putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) - 插入节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    // 定义数组tab，当前节点p，容量n，下标i
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 数组未初始化或数组长度为0，调用resize();
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算出key的位置 i:（(n-1) & hash) ，如果tab[i]为null，生成node对象插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // tab[i]存在节点，定义节点e保存已存在节点，当前节点key - k
        Node<K,V> e; K k;
        // tab[i].hash和传入hash相同，key也相同
        // key有两种判断方法，1：key为null或基本数据类型，直接取出比较 2：k不为null，使用equals()方法进行比较
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // hash冲突且为红黑树结构时，加入红黑树
        else if (p instanceof TreeNode)
            // 节点存在时返回节点，不存在返回null
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 遍历链表，无终止条件，只会在添加节点或找到相同key后退出
            for (int binCount = 0; ; ++binCount) {
                // tab[i].next为null时，即节点不存在时插入节点，break
                if ((e = p.next) == null) {
                    // 生成node对象添加到链尾
                    p.next = newNode(hash, key, value, null);
                    // 如果（已访问节点数>=TREEIFY_THRESHOLD-1），即添加节点后（链表节点数量>=TREEIFY_THRESHOLD-1）转为红黑树，退出循环
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果tab[i].next与插入节点key相同，break
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // p指向p.next准备下一次循环
                p = e;
            }
        }
        // key已存在时，替换value并返回原值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 允许替换或者原值为null时，替换原值的value为传入value
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // LinkedHashMap方法，HashMap中无作用
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 结构修改次数
    ++modCount;
    // size > threshold时会扩容
    if (++size > threshold)
        resize();
    // LinkedHashMap方法，HashMap中无作用
    afterNodeInsertion(evict);
    // key不存在时即无原值返回null
    return null;
}

putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) - 红黑树插入节点

putTreeVal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                    int h, K k, V v) {
    // 定义k的Class对象kc
    Class<?> kc = null;
    // 搜索标志，只会进行一次搜索
    boolean searched = false;
    // 得到树的根节点
    // root()会返回根节点
    TreeNode<K,V> root = (parent != null) ? root() : this;
    // 遍历树，只能内部退出
    for (TreeNode<K,V> p = root;;) {
        // 定义插入方向dir，当前节点ph，当前节点key pk
        int dir, ph; K pk;
        // p.hash>h dir = -1;p.hash<h dir = 1;hash相同，且key相同时返回节点
        // -1即左子树插入，1即右子树插入
        if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        // 在hashCode相同但是无法比较或equals()不同但compareTo()结果相同，既无法确认新节点应在当前节点的左子树还是右子树插入时执行
        // comparableClassFor(k) 如果k implements Comparable 返回k.Class否则返回null
        // compareComparables(kc,k,pk) 如果pk为null或者pk和kc类型不匹配时返回0，即k和pk无法比较时返回0否则返回k.compareTo(pk)
        // 这一部分代码块执行条件为：key未实现Comparable接口或者(k.compareTo(pk) == 0)
        else if ((kc == null &&
                    (kc = comparableClassFor(k)) == null) ||
                    (dir = compareComparables(kc, k, pk)) == 0) {
            // searched 标识是否已经对比过当前节点的左右子节点
            // 如果没有遍历，则比较是否能得到equals()相同的节点
            // 如果得到相等节点返回
            // 如果没有得到则表示需要插入节点
            if (!searched) {
                // 定义返回节点q，遍历节点ch
                TreeNode<K,V> q, ch;
                // 更改标识，不进行第二次查询
                searched = true;
                if (((ch = p.left) != null &&
                        (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                        (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            // 未找到相等计算，计算插入位置
            // tieBreakOrder()方法中无论是否覆盖hashCode()方法都会返回系统默认hashCode()方法生成的值
            // a默认值<=b默认值，左子树插入;a默认值>b默认值，右子树插入
            dir = tieBreakOrder(k, pk);
        }

        // 定义xp作为父节点
        TreeNode<K,V> xp = p;
        // 根据上一步比较的结果访问下一节点
        // key能根据compareTo()方法比较时，根据比较结果访问左右子树
        // key不能比较时根据默认HashCode比较结果访问左右子树
        // 如果p为null，即p为最左子节点或最右子节点时插入节点
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            // 定义xp.next为xpn,维护双向链表
            Node<K,V> xpn = xp.next;
            // 生成节点x
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            // 插入节点
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            // 父节点指向x
            xp.next = x;
            // x的parent和prev指向父节点
            x.parent = x.prev = xp;
            // 父节点的next的prev指向新节点x
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            // 二叉树自平衡后返回根节点root
            // root节点替换原数组中节点
            moveRootToFront(tab, balanceInsertion(root, x));
            // 插入新节点即原值为null
            return null;
        }
    }
}

balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) - 红黑树插入平衡

balanceInsertion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
// 插入红色节点
    x.red = true;
    // 定义父节点xp，祖父节点xpp，祖父节点的左子树xppl，祖父节点的右子树xppr
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        // 父节点为null，即x为根节点时，x变为黑色，return
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        // 父节点为黑色或者【父节点为红色但是爷爷节点为null？】
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
        // 父节点为红色
        // 父节点为祖父节点的左子节点
        if (xp == (xppl = xpp.left)) {
            // 叔叔节点不为空且叔叔节点为红色节点
            if ((xppr = xpp.right) != null && xppr.red) {
                // 父节点和叔叔节点变为黑色，祖父节点变为红色，祖父节点作为失衡节点进入下一循环
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            // 叔叔节点为Nil或者叔叔节点为黑色
            else {
                // 当前节点为父节点的右孩子，左旋
                if (x == xp.right) {
                    // 父节点左旋,左旋后父节点就是新的失衡节点x
                    root = rotateLeft(root, x = xp);
                    // 获取新的父节点xp和新的祖父节点xpp
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                // 当前节点为父节点的左孩子
                if (xp != null) {
                    // 父节点不为null，父节点变为黑色
                    xp.red = false;
                    if (xpp != null) {
                        // 祖父节点不为null，祖父节点变为红色
                        xpp.red = true;
                        //祖父节点右旋
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        // 父节点为祖父节点的右子节点
        else {
            // 叔叔节点不为空且叔叔节点为红色节点
            if (xppl != null && xppl.red) {
                // 父节点和叔叔节点变为黑色，祖父节点变为红色，祖父节点作为失衡节点进入下一循环
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            // 叔叔节点为Nil或者叔叔节点为黑色
            else {
                // 当前节点为父节点的左孩子，右旋
                if (x == xp.left) {
                    // 父节点右旋,右旋后父节点就是新的失衡节点x
                    root = rotateRight(root, x = xp);
                    // 获取新的父节点xp和新的祖父节点xpp
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                // 当前节点为父节点的右孩子
                if (xp != null) {
                    // 父节点不为null，父节点变为黑色
                    xp.red = false;
                    if (xpp != null) {
                        // 祖父节点不为null，祖父节点变为红色
                        xpp.red = true;
                        //祖父节点左旋
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

rotateLLeft(TreeNode<K,V> root,TreeNode<K,V> p) - 左旋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                            TreeNode<K,V> p) {
    // 定义右孩子r，父节点pp，右孩子的左孩子rl
    TreeNode<K,V> r, pp, rl;
    // 左旋节点和左旋节点的右孩子不为null
    if (p != null && (r = p.right) != null) {
        // 左旋节点的right指向左旋节点的右孩子的左孩子
        if ((rl = p.right = r.left) != null)
        // rl不为null时，rl的parent指向左旋节点
            rl.parent = p;
        // 右孩子的parent指向左旋节点的patent
        if ((pp = r.parent = p.parent) == null)
        // 左旋节点为根节点时，右孩子节点变为黑色
            (root = r).red = false;
        // 父节点指向右孩子
        else if (pp.left == p)
            pp.left = r;
        else
            pp.right = r;
        // 右孩子的left指向p，p的parent指向r
        r.left = p;
        p.parent = r;
    }
    return root;
}

rotateRight(TreeNode<K,V> root,TreeNode<K,V> p) - 右旋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                            TreeNode<K,V> p) {
    // 定义左孩子l，父节点pp，左孩子的右孩子lr
    TreeNode<K,V> l, pp, lr;
    // 右旋节点和右旋节点的左孩子不为null
    if (p != null && (l = p.left) != null) {
        // 右旋节点的left指向右旋节点的左孩子的左孩子
        if ((lr = p.left = l.right) != null)
        // lr不为null时，lr的parent指向右旋节点
            lr.parent = p;
        // 左孩子的parent指向右旋节点的patent
        if ((pp = l.parent = p.parent) == null)
        // 右旋节点为根节点时，左孩子节点变为黑色
            (root = l).red = false;
        // 父节点指向左孩子
        else if (pp.right == p)
            pp.right = l;
        else
            pp.left = l;
        // 左孩子的right指向p，p的parent指向l
        l.right = p;
        p.parent = l;
    }
    return root;
}

treeifyBin(Node<K,V>[] tab, int hash) - 转换为双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
    // 定义容量n，下标index，tab[index]处节点e
    int n, index; Node<K,V> e;
    // 表容量太小时扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // 产生hash冲突
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 定义首节点head，尾节点tl
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 将当前节点转化为树节点
            TreeNode<K,V> p = replacementTreeNode(e, null);
            // 尾节点尾空即还未插入节点
            if (tl == null)
            // 首节点指向当前节点
                hd = p;
            // 尾节点不为空，维护双向链表
            else {
                // 当前节点的prev指向上一步的尾节点
                p.prev = tl;
                // 上一步的尾节点的next指向当前节点
                tl.next = p;
            }
            // 当前节点成为新的尾节点
            tl = p;
        } while ((e = e.next) != null);
        // 替换tab[index]处的节点为首节点，并转化为红黑树
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

treeify(Node<K,V>[] tab) - 转为红黑树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
* Forms tree of the nodes linked from this node.
*/
final void treeify(Node<K,V>[] tab) {
    // 定义根节点root
    TreeNode<K,V> root = null;
    // 遍历链表
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        // root为null时，即当前节点为根节点，当前节点的parent指向null，当前节点为黑色
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        // 根节点已存在
        else {
            // 定义当前节点key k
            K k = x.key;
            // 定义当前节点hash h
            int h = x.hash;
            // 定义key的Class类型 kc
            Class<?> kc = null;
            // 从根节点开始遍历，插入节点后自平衡，这部分代码和putTreeVal()中相同，详见putTreeVal()方法
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                            (kc = comparableClassFor(k)) == null) ||
                            (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    // 维护tab的双向链表
    moveRootToFront(tab, root);
}

remove(Object key) - 删除

1
2
3
4
5
6
public V remove(Object key) {
    Node<K,V> e;
    // 调用removeNode()方法删除
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) - 删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * Implements Map.remove and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to match if matchValue, else ignored
 * @param matchValue if true only remove if value is equal
 * @param movable if false do not move other nodes while removing
 * @return the node, or null if none
 */
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // table容量不为0且对应位置不为null才删除
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // hash相同且key相同表明找到对应节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 在对应节点所属链表继续寻找
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                // getTreeNode()方法，前面已经介绍了
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 遍历链表查找
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 找到节点值进行删除
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
            // 删除树节点
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 节点为首节点，直接存放next
            else if (node == p)
                tab[index] = node.next;
            // 否则维护链表管理
            else
                p.next = node.next;
            // 结构修改次数+1
            ++modCount;
            // size-1
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,boolean movable) - 删除树节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/**
* Removes the given node, that must be present before this call.
* This is messier than typical red-black deletion code because we
* cannot swap the contents of an interior node with a leaf
* successor that is pinned by "next" pointers that are accessible
* independently during traversal. So instead we swap the tree
* linkages. If the current tree appears to have too few nodes,
* the bin is converted back to a plain bin. (The test triggers
* somewhere between 2 and 6 nodes, depending on tree structure).
*/
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                            boolean movable) {

    // ---链表处理开始---
    // 定义数组长度n
    int n;
    // map未初始化，直接返回
    if (tab == null || (n = tab.length) == 0)
        return;
    // 计算删除节点下标index
    int index = (n - 1) & hash;
    // 定义链表首节点first，根节点root，根节点的左孩子rl
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    // 定义当前节点的next指针succ，prev节点pred
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    // prev为空即当前节点头节点，不需要维护prev，链表首节点直接指向succ
    if (pred == null)
        tab[index] = first = succ;
    // prev不为空，表示当前节点不为头节点，删除节点需要维护prev和next的关系
    else
        pred.next = succ;
    // 维护双向链表
    if (succ != null)
        succ.prev = pred;
    // 链表不存在节点，直接返回
    if (first == null)
        return;
    // --链表处理结束---
    // --树处理开始--
    // 如果当前节点的父节点不为null，则找到树的根节点。否则当前节点就是根节点。
    if (root.parent != null)
        root = root.root();
    // 通过根节点判断树大小，如果太小退化为链表返回
    if (root == null
        || (movable
            && (root.right == null
                || (rl = root.left) == null
                || rl.left == null))) {
        tab[index] = first.untreeify(map);  // too small
        return;
    }h
    // 定义待删除节点p，左孩子pl，右孩子pr，替换节点replacement
    TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    // 当前节点左右孩子都不为null，找到后继节点替换（二叉平衡树删除节点第三种情况）
    if (pl != null && pr != null) {
        TreeNode<K,V> s = pr, sl;
        // 找到后继节点（右子树的最左节点）
        while ((sl = s.left) != null) // find successor
            s = sl;
        // 待删除节点和后继节点交换颜色
        boolean c = s.red; s.red = p.red; p.red = c; // swap colors
        // 定义待删除节点的父节点pp，后继节点的右孩子sr
        TreeNode<K,V> sr = s.right;
        TreeNode<K,V> pp = p.parent;
        // 如果后继节点就是待删除节点的右孩子，p的parent指向s，s的right指针指向p
        if (s == pr) { // p was s's direct parent
            p.parent = s;
            s.right = p;
        }
        // 否则交换待删除节点和后继节点
        else {
            // 定义后驱节点的父节点sp
            TreeNode<K,V> sp = s.parent;
            // sp不为null，sp指向s的对应指针指向p，且p的parent指针指向s
            if ((p.parent = sp) != null) {
                if (s == sp.left)
                    sp.left = p;
                else
                    sp.right = p;
            }
            // 如果待删除节点的右孩子不为null，将这个右孩子指向s
            if ((s.right = pr) != null)
                pr.parent = s;
        }
        // 交换后p的左孩子应该为null（p就是原来的s）
        p.left = null;
        // 后继节点的右孩子指向p
        if ((p.right = sr) != null)
            sr.parent = p;
        // 待删除节点的左孩子指向s
        if ((s.left = pl) != null)
            pl.parent = s;
        // s指向待删除节点的父节点，如果父节点为null，s就是新的根节点
        if ((s.parent = pp) == null)
            root = s;
        // 否则将待删除节点的父节点的对应指针指向s
        else if (p == pp.left)
            pp.left = s;
        else
            pp.right = s;
        // 替换完成，p被交换到s的原位置，确认替换节点
        // 右孩子不为null，则用后孩子替换，否则p就是叶子节点，不需要替换
        if (sr != null)
            replacement = sr;
        else
            replacement = p;
    }
    // 在上一步判断后，这里是有一个子节点为null或者都为null
    // 所以哪个节点不为null，哪个节点就是替换节点，或者都为null，不需要替换
    else if (pl != null)
        replacement = pl;
    else if (pr != null)
        replacement = pr;
    else
        replacement = p;
    // 需要替换的情况
    if (replacement != p) {
        // 替换节点指向待删除节点的parent
        TreeNode<K,V> pp = replacement.parent = p.parent;
        // 如果待删除节点的parent为null，替换节点就是新的根节点
        if (pp == null)
            root = replacement;
        // 否则将父节点的对应指针指向替换节点
        else if (p == pp.left)
            pp.left = replacement;
        else
            pp.right = replacement;
        // 清空待删除节点的引用，便于垃圾回收
        p.left = p.right = p.parent = null;
    }

    // 如果待删除节点为红色则不要平衡，为黑色则需要进行自平衡
    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
    // 不需要替换的情况，待删除节点的父节点对应指针指向null
    if (replacement == p) {  // detach
        TreeNode<K,V> pp = p.parent;
        // 清除引用
        p.parent = null;
        if (pp != null) {
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null;
        }
    }
    // 移动根节点到数组中
    if (movable)
        moveRootToFront(tab, r);
}

balanceDeletion(TreeNode<K,V> root,TreeNode<K,V> x) - 删除平衡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                TreeNode<K,V> x) {
    // 定义待平衡节点的父节点xp，父节点的左孩子xpl，父节点的右孩子xpr
    for (TreeNode<K,V> xp, xpl, xpr;;) {
        // 如果待平衡节点为null或者待平衡节点为根节点（或后续处理完毕），则不需要平衡
        if (x == null || x == root)
            return root;
        // 这也是根节点，变为黑色
        else if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        // 待平衡节点为红色，变为黑色即可（因为原来删除了一个黑色，红变黑则将缺少的补了回来）
        else if (x.red) {
            x.red = false;
            return root;
        }
        // 当前节点为父节点的左孩子
        else if ((xpl = xp.left) == x) {
            // 兄弟节点（父节点的右孩子）不为null且为红色
            if ((xpr = xp.right) != null && xpr.red) {
                // 兄弟节点变为黑色
                xpr.red = false;
                // 父节点变为红色
                xp.red = true;
                // 父节点左旋
                root = rotateLeft(root, xp);
                // 左旋后父节点的右子树变为兄弟节点，进入下一循环按其他情况处理
                xpr = (xp = x.parent) == null ? null : xp.right;
            }
            // 兄弟节点为null，父节点作为新的待平衡节点进入下一循环
            if (xpr == null)
                x = xp;
            // 待平衡节点为黑色的情况
            else {
                // 定义兄弟节点的左孩子sl，右孩子sr
                TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                // 兄弟节点的左孩子和右孩子都为黑色，直接将兄弟节点也变为黑色，所以父节点成为了新的待平衡节点
                if ((sr == null || !sr.red) &&
                    (sl == null || !sl.red)) {
                    xpr.red = true;
                    x = xp;
                }
                // 兄弟节点有一个子节点为红色
                else {
                    // 兄弟节点的右孩子不为红色则左孩子一定为红色
                    if (sr == null || !sr.red) {
                        // 兄弟节点的左孩子不为null则变为黑色
                        if (sl != null)
                            sl.red = false;
                        // 兄弟节点变为红色
                        xpr.red = true;
                        // 兄弟节点右旋
                        root = rotateRight(root, xpr);
                        // 获得新的兄弟节点，方便后续处理
                        xpr = (xp = x.parent) == null ?
                            null : xp.right;
                    }
                    if (xpr != null) {
                        // 兄弟节点变为父节点的颜色
                        xpr.red = (xp == null) ? false : xp.red;
                        // 兄弟节点的右孩子变为黑色
                        if ((sr = xpr.right) != null)
                            sr.red = false;
                    }
                    // 父节点变为黑色，即父节点和兄弟节点交换了颜色
                    if (xp != null) {
                        xp.red = false;
                        // 父节点左旋
                        root = rotateLeft(root, xp);
                    }
                    // 处理完毕，退出循环
                    x = root;
                }
            }
        }
        // 当前节点为父节点的右孩子
        else { // symmetric
            // 参考左子树，兄弟节点（父节点的左孩子）不为null且为红色
            // 兄弟节点变为黑色，父节点变为红色，父节点右旋，获得新的兄弟节点进入下一循环
            if (xpl != null && xpl.red) {
                xpl.red = false;
                xp.red = true;
                root = rotateRight(root, xp);
                xpl = (xp = x.parent) == null ? null : xp.left;
            }
            if (xpl == null)
                x = xp;
            else {
                TreeNode<K,V> sl = xpl.left, sr = xpl.right;
                // 兄弟节点的左孩子都为黑色，兄弟节点变为红色，父节点作为新的待处理节点
                if ((sl == null || !sl.red) &&
                    (sr == null || !sr.red)) {
                    xpl.red = true;
                    x = xp;
                }
                else {
                    // 兄弟节点的右孩子为红色
                    if (sl == null || !sl.red) {
                        if (sr != null)
                            // 兄弟节点的右孩子变为黑色
                            sr.red = false;
                        // 兄弟节点变为红色
                        xpl.red = true;
                        // 兄弟节点左旋
                        root = rotateLeft(root, xpl);
                        // 获得新的兄弟节点进入后续处理
                        xpl = (xp = x.parent) == null ?
                            null : xp.left;
                    }
                    if (xpl != null) {
                        // 兄弟节点变为父节点的颜色
                        xpl.red = (xp == null) ? false : xp.red;
                        // 兄弟节点的左孩子变为黑色
                        if ((sl = xpl.left) != null)
                            sl.red = false;
                    }
                    // 父节点变为黑色，父节点右旋
                    if (xp != null) {
                        xp.red = false;
                        root = rotateRight(root, xp);
                    }
                    // 处理完成退出循环
                    x = root;
                }
            }
        }
    }
}

resize() - 扩容

HashMap扩容resize()方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    // 获取当前数组oldTab,当前容量oldCap,当前临界点oldThr
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 当前容量大于0，扩容
    if (oldCap > 0) {
        // 当前容量大于等于设定的最大容量无法扩容，直接返回
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 如果扩容后的容量小于最大值且原容量大于等于默认值，才会将临界点扩容
        // 原容量*2，原临界点*2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 当前容量等于0但是临界点>0，这是构造方法会执行的扩容方法，
    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);
                // 定义lo，hi两个链表对应原位置和(原位置+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) {
                            // 确定lo链表头节点
                            if (loTail == null)
                                loHead = e;
                            // 加入lo链表
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            // 确定hi链表头节点
                            if (hiTail == null)
                                hiHead = e;
                            // 加入hi链表
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // lo链表放入原位置
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // hi链表放入(j+oldCap)位置
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

关于 (e.hash & oldCap) == 0 j 以及 j+oldCap

本部分来自深入理解 HashMap(四): 关键源码逐行分析之 resize 扩容

明确三个前提条件：

  1. oldCap 为 2 的幂，假设为2^n
  2. newCal 为oldCap*2,即2^(n+1)
  3. HashMap 确定下标位置是对 hashcode 按容量取余，即(n-1) & hash;

例如：

假设 oldCap 为 16，即 2^4，（16-1）的二进制结果为0000 0000 0000 1111，所以(16-1)&hash就是对 hash 取后四位。
而扩容后 newCap 为 32,即 2^4,（16-1）的二进制结果为0000 0000 0001 1111，而(32-1)&hash就是对 hash 取后五位。

根据上面的计算结果，假设 hash 后四位为 abcd，扩容后的下标不是0abcd就是1abcd。其中0abcd就是原位置。而1abcd如下：

1
1abcd = 0abcd + 10000 = oabcd + oldCap。

故虽然数组大小扩大了一倍，但是同一个 key 在新旧 table 中对应的 index 却存在一定联系：要么一致，要么相差一个 oldCap。

而新旧 index 是否一致就体现在 hash 值的第 4 位(我们把最低为称作第 0 位), 怎么拿到这一位的值呢, 只要:

1
hash & 0000 0000 0000 0000 0000 0000 0001 0000

也就是e.hash & oldCap.

故得出结论:

如果 (e.hash & oldCap) == 0 则该节点在新表的下标位置与旧表一致都为 j
如果 (e.hash & oldCap) == 1 则该节点在新表的下标位置 j + oldCap

根据这个条件, 我们将原位置的链表拆分成两个链表, 然后一次性将整个链表放到新的 Table 对应的位置上.

split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) - 拆分红黑树

扩容拆分红黑树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
 * Splits nodes in a tree bin into lower and upper tree bins,
 * or untreeifies if now too small. Called only from resize;
 * see above discussion about split bits and indices.
 *
 * @param map the map
 * @param tab the table for recording bin heads
 * @param index the index of the table being split
 * @param bit the bit of hash to split on
 */
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // 和链表拆分相同，定义两个链表，甚至都是按链表遍历
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    // 因为TreeNode也是双向链表，所以可以按链表遍历
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            // 确定lo链表首节点
            if ((e.prev = loTail) == null)
                loHead = e;
            // 添加到lo链表
            else
                loTail.next = e;
            loTail = e;
            // lo链表size+1
            ++lc;
        }
        else {
            // 确定hi链表首节点
            if ((e.prev = hiTail) == null)
                hiHead = e;
            // 添加到hi链表
            else
                hiTail.next = e;
            hiTail = e;
            // hi链表size+1
            ++hc;
        }
    }

    // lo链表首节点不为null
    if (loHead != null) {
        // 链表长度小于等于退化节点，退化为链表
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        // 链表长度满足条件，将头节点放在数组中
        else {
            tab[index] = loHead;
            // 如果hi链表为null，表示原链表没有拆分，结构就没有改变，不需要变为红黑树
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    // hi链表首节点不为null
    if (hiHead != null) {
        // 链表长度小于等于退化节点，退化为链表
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
         // 链表长度满足条件，将头节点放在数组中
        else {
            tab[index + bit] = hiHead;
            // 如果lo链表为null，表示原链表没有拆分，结构就没有改变，不需要变为红黑树
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

总结

花了 n 天时间，不知不觉就把 HashMap 源码看了大半，开始以为 get(),put(),remove()三个方法的工作量不会太多，后面发现总和起来基本就是一个完整的 HashMap 了。从中也看到一些很精妙的设计，为了减少哈希冲突，加快查询效率。有很多技巧都值得学习啊。