ConcurrentHashMap 的红黑树实现分析

正文

请到「今天看啥」查看全文

for (Node e = b; e != null; e = e.next) {

TreeNode p =

new TreeNode (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 (hd));

}

}

}

}

}

从上述实现可以看出：并非一开始就创建红黑树结构，如果当前Node数组长度小于阈值MIN_TREEIFY_CAPACITY，默认为64，先通过扩大数组容量为原来的两倍以缓解单个链表元素过大的性能问题。

红黑树构造过程

下面对红黑树的构造过程进行分析：

1、通过遍历Node链表，生成对应的TreeNode链表，其中TreeNode在实现上继承了Node类；

class TreeNode extends Node {

TreeNode parent;  // red-black tree links

TreeNode left;

TreeNode right;

TreeNode prev;

// needed to unlink next upon deletion

boolean red;

}

假设TreeNode链表如下，其中节点中的数值代表hash值：

2、根据TreeNode链表初始化TreeBin类对象，TreeBin在实现上同样继承了Node类，所以初始化完成的TreeBin类对象可以保持在Node数组中；

class TreeBin extends Node {

TreeNode root;

volatile TreeNode first;

volatile Thread waiter;

volatile int lockState;

// values for lockState

// set while holding write lock

static final int WRITER = 1;

// set when waiting for write lock

static final int WAITER = 2;

// increment value for setting read lock

static final int READER = 4;

}

3、遍历TreeNode链表生成红黑树，一开始二叉树的根节点root为空，则设置链表中的第一个节点80为root，并设置其red属性为false，因为在红黑树的特性1中，明确规定根节点必须是黑色的；

for (TreeNode x = b, next; x != null; x = next) {

next = (TreeNode )x.next;

x.left = x.right = null;

if (r == null) {

x.parent = null;

x.red = false;

r = x;

请到「今天看啥」查看全文