这个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.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;//颜色(红或黑) }}
青春不是年华，而是心境；青春不是桃面丹唇柔膝，
