这个Map类是基于红黑树构建的，每个树节点有两个域，一个存放节点的Key,一个存放节点的Value,相当于是两棵红黑树，一棵是关于key的红黑树，一棵是关于Value的红黑树。
关于红黑树的详细介绍，参考《C#与数据结构--树论--红黑树（Red Black Tree）》这篇文章。
复制代码
public final class DoubleOrderedMap extends AbstractMap
{
private Node[] rootNode = new Node[] { null, null };//根节点
public Set entrySetByValue()
{//按Value获取Entry集合
if (setOfEntries[VALUE] == null) {
setOfEntries[VALUE] = new AbstractSet() {
public Iterator iterator() {
return new DoubleOrderedMapIterator(VALUE) {
protected Object doGetNext() {
return lastReturnedNode;
}
};
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
Map.Entry entry = (Map.Entry) o;
Object key = entry.getKey();
Node node = lookup((Comparable) entry.getValue(),
VALUE);
return (node != null) && node.getData(KEY).equals(key);
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
Map.Entry entry = (Map.Entry) o;
Object key = entry.getKey();
Node node = lookup((Comparable) entry.getValue(),
VALUE);
if ((node != null) && node.getData(KEY).equals(key)) {
doRedBlackDelete(node);
return true;
}
return false;
}
public int size() {
return DoubleOrderedMap.this.size();
}
public void clear() {
DoubleOrderedMap.this.clear();
}
};
}
return setOfEntries[VALUE];
}
private Object doRemove(final Comparable o, final int index)
{
Node node = lookup(o, index);//在红黑树中查找节点
Object rval = null;
if (node != null)
{
rval = node.getData(oppositeIndex(index));
doRedBlackDelete(node);//在红黑树中删除指定节点
}
return rval;
}
private Object doGet(final Comparable o, final int index)
{
checkNonNullComparable(o, index);//检查参数非空
Node node = lookup(o, index);//按Key或Value查找指定节点
return ((node == null)? null: node.getData(oppositeIndex(index)));
}
private Node lookup(final Comparable data, final int index)
{
Node rval = null;
Node node = rootNode[index];//根节点
while (node != null)
{
int cmp = compare(data, node.getData(index));//与当前节点比较
if (cmp == 0)
{//找到了
rval = node;
break;
} else {//在左子树或右子树中寻找
node = (cmp < 0)
? node.getLeft(index)
: node.getRight(index);
}
}
return rval;
}
private static Node leastNode(final Node node, final int index)
{//返回指定节点的最右子节点
Node rval = node;
if (rval != null) {
while (rval.getLeft(index) != null) {
rval = rval.getLeft(index);
}
}
return rval;
}
private Node nextGreater(final Node node, final int index)
{//返回下一个大于指定节点的节点
Node rval = null;
if (node == null) {
rval = null;
} else if (node.getRight(index) != null)
{//右子树不为空，返回右子树最左子节点
rval = leastNode(node.getRight(index), index);
}
else
{//不断向上，只要仍然是右子节点
Node parent = node.getParent(index);
Node child = node;
while ((parent != null) && (child == parent.getRight(index))) {
child = parent;
parent = parent.getParent(index);
}
rval = parent;
}
return rval;
}
private void rotateLeft(final Node node, final int index)
{//左旋操作
Node rightChild = node.getRight(index);
node.setRight(rightChild.getLeft(index), index);
if (rightChild.getLeft(index) != null) {
rightChild.getLeft(index).setParent(node, index);
}
rightChild.setParent(node.getParent(index), index);
if (node.getParent(index) == null)
{//设置为根节点
rootNode[index] = rightChild;
} else if (node.getParent(index).getLeft(index) == node) {
node.getParent(index).setLeft(rightChild, index);
} else {
node.getParent(index).setRight(rightChild, index);
}
rightChild.setLeft(node, index);
node.setParent(rightChild, index);
}
private void rotateRight(final Node node, final int index)
{//右旋操作
Node leftChild = node.getLeft(index);
node.setLeft(leftChild.getRight(index), index);
if (leftChild.getRight(index) != null) {
leftChild.getRight(index).setParent(node, index);
}
leftChild.setParent(node.getParent(index), index);
if (node.getParent(index) == null)
{//设置为根节点
rootNode[index] = leftChild;
} else if (node.getParent(index).getRight(index) == node) {
node.getParent(index).setRight(leftChild, index);
} else {
node.getParent(index).setLeft(leftChild, index);
}
leftChild.setRight(node, index);
node.setParent(leftChild, index);
}
private void doRedBlackInsert(final Node insertedNode, final int index)
{//进行红黑树节点插入后的调整
Node currentNode = insertedNode;//新插入节点置为当前节点
makeRed(currentNode, index);//标记新节点为红色
while ((currentNode != null) && (currentNode != rootNode[index])&& (isRed(currentNode.getParent(index), index)))
{//确保当前节点父节点为红色才继续处理
if (isLeftChild(getParent(currentNode, index), index))
{//父节点是祖父节点的左孩子
Node y = getRightChild(getGrandParent(currentNode, index),index);//叔节点是祖父节点的右孩子
if (isRed(y, index))
{//红叔(图4)
makeBlack(getParent(currentNode, index), index);//标记父节点为黑色
makeBlack(y, index);//标记叔节点为黑色
makeRed(getGrandParent(currentNode, index), index);//标记祖父节点为红色
currentNode = getGrandParent(currentNode, index);//置祖父节点为当前节点
}
else
{//黑叔(对应图5和图6)
if (isRightChild(currentNode, index))
{//当前节点是父节点的右孩子(图6)
currentNode = getParent(currentNode, index);//置父节点为当前节点
rotateLeft(currentNode, index);//左旋
}
makeBlack(getParent(currentNode, index), index);//当前节点的父节点置为黑色
makeRed(getGrandParent(currentNode, index), index);//祖父节点置为红色
if (getGrandParent(currentNode, index) != null)
{//对祖父节点进行右旋
rotateRight(getGrandParent(currentNode, index),index);
}
}
} else
{//父节点是祖父节点的右孩子
Node y = getLeftChild(getGrandParent(currentNode, index),index);//叔节点是祖父节点的左孩子
if (isRed(y, index))
{//红叔(图4)
makeBlack(getParent(currentNode, index), index);//标记父节点为黑色
makeBlack(y, index);//标记叔节点为黑色
makeRed(getGrandParent(currentNode, index), index);//标记祖父节点为红色
currentNode = getGrandParent(currentNode, index);//置祖父节点为当前节点
}
else
{//黑叔(对应图7和图8)
if (isLeftChild(currentNode, index))
{//当前节点是父节点的左孩子(图8)
currentNode = getParent(currentNode, index);//置父节点为当前节点
rotateRight(currentNode, index);//右旋
}
makeBlack(getParent(currentNode, index), index);//当前节点的父节点置为黑色
makeRed(getGrandParent(currentNode, index), index);//祖父节点置为红色
if (getGrandParent(currentNode, index) != null)
{//对祖父节点进行左旋
rotateLeft(getGrandParent(currentNode, index), index);
}
}
}
}
makeBlack(rootNode[index], index);//标记根节点为黑色
}
private void doRedBlackDelete(final Node deletedNode)
{//在红黑树中删除指定节点
for (int index = FIRST_INDEX; index < NUMBER_OF_INDICES; index++) {
// if deleted node has both left and children, swap with
// the next greater node
if ((deletedNode.getLeft(index) != null)
&& (deletedNode.getRight(index) != null)) {
swapPosition(nextGreater(deletedNode, index), deletedNode,
index);
}
Node replacement = ((deletedNode.getLeft(index) != null)
? deletedNode.getLeft(index)
: deletedNode.getRight(index));
if (replacement != null) {
replacement.setParent(deletedNode.getParent(index), index);
if (deletedNode.getParent(index) == null) {
rootNode[index] = replacement;
} else if (deletedNode
== deletedNode.getParent(index).getLeft(index)) {
deletedNode.getParent(index).setLeft(replacement, index);
} else {
deletedNode.getParent(index).setRight(replacement, index);
}
deletedNode.setLeft(null, index);
deletedNode.setRight(null, index);
deletedNode.setParent(null, index);
if (isBlack(deletedNode, index)) {
doRedBlackDeleteFixup(replacement, index);
}
} else {
// replacement is null
if (deletedNode.getParent(index) == null) {
// empty tree
rootNode[index] = null;
} else {
// deleted node had no children
if (isBlack(deletedNode, index)) {
doRedBlackDeleteFixup(deletedNode, index);
}
if (deletedNode.getParent(index) != null) {
if (deletedNode
== deletedNode.getParent(index)
.getLeft(index)) {
deletedNode.getParent(index).setLeft(null, index);
} else {
deletedNode.getParent(index).setRight(null,
index);
}
deletedNode.setParent(null, index);
}
}
}
}
shrink();
}
private void doRedBlackDeleteFixup(final Node replacementNode,
final int index)
{//重新局部平衡红黑树
Node currentNode = replacementNode;
while ((currentNode != rootNode[index])
&& (isBlack(currentNode, index))) {
if (isLeftChild(currentNode, index)) {
Node siblingNode =
getRightChild(getParent(currentNode, index), index);
if (isRed(siblingNode, index)) {
makeBlack(siblingNode, index);
makeRed(getParent(currentNode, index), index);
rotateLeft(getParent(currentNode, index), index);
siblingNode = getRightChild(getParent(currentNode, index), index);
}
if (isBlack(getLeftChild(siblingNode, index), index)
&& isBlack(getRightChild(siblingNode, index),
index)) {
makeRed(siblingNode, index);
currentNode = getParent(currentNode, index);
} else {
if (isBlack(getRightChild(siblingNode, index), index)) {
makeBlack(getLeftChild(siblingNode, index), index);
makeRed(siblingNode, index);
rotateRight(siblingNode, index);
siblingNode =
getRightChild(getParent(currentNode, index), index);
}
copyColor(getParent(currentNode, index), siblingNode,
index);
makeBlack(getParent(currentNode, index), index);
makeBlack(getRightChild(siblingNode, index), index);
rotateLeft(getParent(currentNode, index), index);
currentNode = rootNode[index];
}
} else {
Node siblingNode = getLeftChild(getParent(currentNode, index), index);
if (isRed(siblingNode, index)) {
makeBlack(siblingNode, index);
makeRed(getParent(currentNode, index), index);
rotateRight(getParent(currentNode, index), index);
siblingNode = getLeftChild(getParent(currentNode, index), index);
}
if (isBlack(getRightChild(siblingNode, index), index)
&& isBlack(getLeftChild(siblingNode, index), index)) {
makeRed(siblingNode, index);
currentNode = getParent(currentNode, index);
} else {
if (isBlack(getLeftChild(siblingNode, index), index)) {
makeBlack(getRightChild(siblingNode, index), index);
makeRed(siblingNode, index);
rotateLeft(siblingNode, index);
siblingNode =
getLeftChild(getParent(currentNode, index), index);
}
copyColor(getParent(currentNode, index), siblingNode,
index);
makeBlack(getParent(currentNode, index), index);
makeBlack(getLeftChild(siblingNode, index), index);
rotateRight(getParent(currentNode, index), index);
currentNode = rootNode[index];
}
}
}
makeBlack(currentNode, index);
}
private void swapPosition(final Node x, final Node y, final int index)
{//交换树中两个节点
// Save initial values.
Node xFormerParent = x.getParent(index);
Node xFormerLeftChild = x.getLeft(index);
Node xFormerRightChild = x.getRight(index);
Node yFormerParent = y.getParent(index);
Node yFormerLeftChild = y.getLeft(index);
Node yFormerRightChild = y.getRight(index);
boolean xWasLeftChild =
(x.getParent(index) != null)
&& (x == x.getParent(index).getLeft(index));
boolean yWasLeftChild =
(y.getParent(index) != null)
&& (y == y.getParent(index).getLeft(index));
// Swap, handling special cases of one being the other's parent.
if (x == yFormerParent) { // x was y's parent
x.setParent(y, index);
if (yWasLeftChild) {
y.setLeft(x, index);
y.setRight(xFormerRightChild, index);
} else {
y.setRight(x, index);
y.setLeft(xFormerLeftChild, index);
}
} else {
x.setParent(yFormerParent, index);
if (yFormerParent != null) {
if (yWasLeftChild) {
yFormerParent.setLeft(x, index);
} else {
yFormerParent.setRight(x, index);
}
}
y.setLeft(xFormerLeftChild, index);
y.setRight(xFormerRightChild, index);
}
if (y == xFormerParent) { // y was x's parent
y.setParent(x, index);
if (xWasLeftChild) {
x.setLeft(y, index);
x.setRight(yFormerRightChild, index);
} else {
x.setRight(y, index);
x.setLeft(yFormerLeftChild, index);
}
} else {
y.setParent(xFormerParent, index);
if (xFormerParent != null) {
if (xWasLeftChild) {
xFormerParent.setLeft(y, index);
} else {
xFormerParent.setRight(y, index);
}
}
x.setLeft(yFormerLeftChild, index);
x.setRight(yFormerRightChild, index);
}
// Fix children's parent pointers
if (x.getLeft(index) != null) {
x.getLeft(index).setParent(x, index);
}
if (x.getRight(index) != null) {
x.getRight(index).setParent(x, index);
}
if (y.getLeft(index) != null) {
y.getLeft(index).setParent(y, index);
}
if (y.getRight(index) != null) {
y.getRight(index).setParent(y, index);
}
x.swapColors(y, index);
// Check if root changed
if (rootNode[index] == x) {
rootNode[index] = y;
} else if (rootNode[index] == y) {
rootNode[index] = x;
}
}
public Object put(final Object key, final Object value)
throws ClassCastException, NullPointerException,
IllegalArgumentException {
checkKeyAndValue(key, value);
Node node = rootNode[KEY];
if (node == null) {//空树
Node root = new Node((Comparable) key, (Comparable) value);
rootNode[KEY] = root;
rootNode[VALUE] = root;
grow();
} else {
while (true) {
int cmp = compare((Comparable) key, node.getData(KEY));
if (cmp == 0) {
throw new IllegalArgumentException(
"Cannot store a duplicate key (\"" + key
+ "\") in this Map");
} else if (cmp < 0) {
if (node.getLeft(KEY) != null) {
node = node.getLeft(KEY);
} else {
Node newNode = new Node((Comparable) key,
(Comparable) value);
insertValue(newNode);
node.setLeft(newNode, KEY);
newNode.setParent(node, KEY);
doRedBlackInsert(newNode, KEY);
grow();
break;
}
} else { // cmp > 0
if (node.getRight(KEY) != null) {
node = node.getRight(KEY);
} else {
Node newNode = new Node((Comparable) key,
(Comparable) value);
insertValue(newNode);
node.setRight(newNode, KEY);
newNode.setParent(node, KEY);
doRedBlackInsert(newNode, KEY);
grow();
break;
}
}
}
}
return null;
}
private abstract class DoubleOrderedMapIterator implements Iterator
{
private int expectedModifications;
protected Node lastReturnedNode;//上次访问的节点
private Node nextNode;//下一个节点(最左子节点)
private int iteratorType;
DoubleOrderedMapIterator(final int type)
{
iteratorType = type;
expectedModifications = DoubleOrderedMap.this.modifications;
lastReturnedNode = null;
nextNode = leastNode(rootNode[iteratorType],
iteratorType);
}
protected abstract Object doGetNext();
public final boolean hasNext() {
return nextNode != null;
}
public final Object next()
throws NoSuchElementException,
ConcurrentModificationException {
if (nextNode == null) {
throw new NoSuchElementException();
}
if (modifications != expectedModifications) {
throw new ConcurrentModificationException();
}
lastReturnedNode = nextNode;
nextNode = nextGreater(nextNode, iteratorType);
return doGetNext();
}
public final void remove()
throws IllegalStateException,
ConcurrentModificationException {
if (lastReturnedNode == null) {
throw new IllegalStateException();
}
if (modifications != expectedModifications) {
throw new ConcurrentModificationException();
}
doRedBlackDelete(lastReturnedNode);
expectedModifications++;
lastReturnedNode = null;
}
}
//内部节点类
private static final class Node implements Map.Entry, KeyValue
{
private Comparable[] data;//数据域（key和value）
private Node[] leftNode;//左子节点
private Node[] rightNode;//右子节点
private Node[] parentNode;//父节点
private boolean[] blackColor;//颜色(红或黑)
}
}
复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2008/12/19/1358486.html，如需转载请自行联系原作者
