1.8HashMap链表转红黑树

发表于 | 评论数： | 阅读次数：

ConcurrentHashMap的底层数据为数组加链表，哈希冲突的值会放在链表中，如果哈希冲突严重，对ConcurrentHashMap的操作会变为对长链表的操作，为了解决效率问题，1.8会进行红黑树的转换

红黑树

什么是红黑树

红黑树是一种特殊的平衡二叉树，存放有序的数据，检索的时间复杂度为O(lgn)

红黑树的特性

  1. 红黑树的节点非红即黑
  2. 根节点为黑色
  3. 叶子节点为黑色叶子节点为NIL节点即空节点
  4. 如果一个节点为红色，那么他的子节点一定是黑色
  5. 从一个节点到该节点的子孙节点的所有路径包含相同个数个黑色节点
    红黑树的结构修改
  6. 左旋
    • 将节点A的子右节点调整为自己的父节点，将该子右节点下的子左节点调整为自己的子右节点
  7. 右旋
    • 将节点A的子左节点调整为自己的父节点，将该子左节点下的子右节点调整为自己的子左节点
  8. 着色

在什么情况下进行转换

java针对链表进行监控，给链表的最大长度设定默认阈值为8，超过阈值就会进行结构改变

1
2
3
4
5
6
7
8
9
/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2, and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

具体时间是在put方法调用的真实方法putVal中，处理完数据的放置后进行检查

1
2
3
4
5
6
7
if (binCount != 0) {
    if (binCount >= TREEIFY_THRESHOLD)
        treeifyBin(tab, i);
    if (oldVal != null)
        return oldVal;
    break;
}

首先对节点进行处理，先判断是否需要进行链表的扩容，以64长度为界限，64以下扩容2倍，64以上将Node转换为TreeNode

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
/**
 * Replaces all linked nodes in bin at given index unless table is
 * too small, in which case resizes instead.
 */
private final void treeifyBin(Node<K,V>[] tab, int index) {
    Node<K,V> b; int n, sc;
    if (tab != null) {
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            tryPresize(n << 1);
        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
            synchronized (b) {
                if (tabAt(tab, index) == b) {
                    TreeNode<K,V> hd = null, tl = null;
                    for (Node<K,V> e = b; e != null; e = e.next) {
                        TreeNode<K,V> p =
                            new TreeNode<K,V>(e.hash, e.key, e.val,
                                              null, null);
                        if ((p.prev = tl) == null)
                            hd = p;
                        else
                            tl.next = p;
                        tl = p;
                    }
                    setTabAt(tab, index, new TreeBin<K,V>(hd));
                }
            }
        }
    }
}