Commons Collections 學習筆記（三）：DoubleOrderedMap - 雙向有序紅黑樹 Map 實作深度解析

DoubleOrderedMap 是 Commons Collections 中獨特的 Map 實作，內部維護兩棵紅黑樹：一棵按 Key 排序，一棵按 Value 排序，支援雙向高效查找、範圍操作與有序迭代。本文深度解析其核心資料結構、紅黑樹插入/刪除平衡邏輯、雙向索引同步機制與迭代器實作。

核心資料結構

public final class DoubleOrderedMap extends AbstractMap {
    private Node[] rootNode = new Node[] { null, null }; // [KEY_ROOT, VALUE_ROOT]
    private static final int KEY = 0, VALUE = 1;
    // Node 同時掛載於兩棵樹，含左右子節點、父節點、顏色陣列
    private static final class Node implements Map.Entry, KeyValue {
        private Comparable[] data;     // [key, value]
        private Node[] leftNode;       // [keyLeft, valueLeft]
        private Node[] rightNode;      // [keyRight, valueRight]
        private Node[] parentNode;     // [keyParent, valueParent]
        private boolean[] blackColor;  // [keyBlack, valueBlack]
    }
}

• 單一 Node 同時存在於 Key 樹與 Value 樹，透過索引 0/1 區分。
• 所有樹操作（查找、插入、刪除、旋轉）均需雙向同步執行。

關鍵操作實作

1. 雙向查找

private Node lookup(Comparable data, int index) {
    Node node = rootNode[index];
    while (node != null) {
        int cmp = compare(data, node.getData(index));
        if (cmp == 0) return node;
        node = (cmp < 0) ? node.getLeft(index) : node.getRight(index);
    }
    return null;
}

• index=0 走 Key 樹，index=1 走 Value 樹。
• get(key)、remove(key) 使用 Key 樹；entrySetByValue() 相關操作使用 Value 樹。

2. 紅黑樹插入平衡

private void doRedBlackInsert(Node insertedNode, int index) {
    makeRed(insertedNode, index);
    while (insertedNode != rootNode[index] && isRed(getParent(insertedNode, index), index)) {
        if (isLeftChild(getParent(insertedNode, index), index)) {
            Node uncle = getRightChild(getGrandParent(insertedNode, index), index);
            if (isRed(uncle, index)) { // Case 1: 紅叔叔
                makeBlack(getParent(insertedNode, index), index);
                makeBlack(uncle, index);
                makeRed(getGrandParent(insertedNode, index), index);
                insertedNode = getGrandParent(insertedNode, index);
            } else { // Case 2/3: 黑叔叔
                if (isRightChild(insertedNode, index)) { // LR
                    insertedNode = getParent(insertedNode, index);
                    rotateLeft(insertedNode, index);
                }
                makeBlack(getParent(insertedNode, index), index);
                makeRed(getGrandParent(insertedNode, index), index);
                rotateRight(getGrandParent(insertedNode, index), index);
            }
        } else { // 鏡像邏輯：父節點為右孩子
            // ... 對稱處理 ...
        }
    }
    makeBlack(rootNode[index], index);
}

• 標準紅黑樹插入修正：紅叔叔 → 重新著色上移；黑叔叔 → 旋轉重組。
• 雙樹同步：put() 先插入 Key 樹，再呼叫 insertValue() 插入 Value 樹，各自獨立平衡。

3. 紅黑樹刪除平衡

private void doRedBlackDelete(Node deletedNode) {
    for (int index = KEY; index <= VALUE; index++) {
        // 1. 兩個孩子皆存在 → 與後繼節點交換位置
        // 2. 至多一個孩子 → 直接替換
        // 3. 刪除節點為黑色 → doRedBlackDeleteFixup 修正
    }
    shrink(); // 更新 size/modCount
}

doRedBlackDeleteFixup 實作標準刪除修正四案例（兄弟紅/黑、姪子紅/黑），雙樹各自獨立執行。

4. 節點位置交換

private void swapPosition(Node x, Node y, int index) {
    // 處理一般情況與父子關係特殊情況
    // 交換父、左、右指標，修正子節點父指標
    // 交換顏色
    // 更新根節點引用
}

• 刪除時若節點有雙孩子，需與中序後繼節點交換位置而非單純複製值，以維持雙樹節點身分一致性。

5. 有序迭代器

private abstract class DoubleOrderedMapIterator implements Iterator {
    protected Node lastReturnedNode, nextNode;
    private int iteratorType; // KEY 或 VALUE
    public Object next() {
        if (modifications != expectedModifications) throw new ConcurrentModificationException();
        lastReturnedNode = nextNode;
        nextNode = nextGreater(nextNode, iteratorType); // 中序後繼
        return doGetNext();
    }
    public void remove() { doRedBlackDelete(lastReturnedNode); }
}

• entrySet() 走 Key 樹（leastNode 取最左節點起始）。
• entrySetByValue() 走 Value 樹，支援按值排序迭代。
• 快速失效機制：modCount 檢測並發修改。

put() 完整流程

public Object put(Object key, Object value) {
    checkKeyAndValue(key, value); // 非空、可比較
    Node node = rootNode[KEY];
    if (node == null) { // 空樹
        Node root = new Node((Comparable)key, (Comparable)value);
        rootNode[KEY] = rootNode[VALUE] = root;
        grow(); return null;
    }
    while (true) {
        int cmp = compare((Comparable)key, node.getData(KEY));
        if (cmp == 0) throw new IllegalArgumentException("Duplicate key");
        if (cmp < 0) {
            if (node.getLeft(KEY) != null) node = node.getLeft(KEY);
            else { insertNewNode(node, key, value, true); break; }
        } else {
            if (node.getRight(KEY) != null) node = node.getRight(KEY);
            else { insertNewNode(node, key, value, false); break; }
        }
    }
    return null;
}

insertNewNode 建立節點，掛入 Key 樹並 doRedBlackInsert，再呼叫 insertValue 掛入 Value 樹並平衡。

效能特徵與適用場景

適用：需同時支援「按 Key 查值」與「按 Value 查鍵/範圍」的場景，如雙向索引、反向查找、雙向排序顯示。不適用：單向查找、高寫入吞吐、記憶體敏感場景（優先 HashMap/TreeMap）。

結語

DoubleOrderedMap 以雙紅黑樹架構實現真正的雙向有序映射，代碼完整實現了插入/刪除/旋轉/著色/交換等核心演算法，展示了資料結構經典理論在 Java 集合框架中的工程化應用。理解其雙樹同步機制，有助於在需要雙向索引時做出正確技術選型。

1. 上一篇文章： Commons Collections 學習筆記（四）：BeanMap - JavaBean 與 Map 雙向轉換利器
2. 下一篇文章： Commons Collections 學習筆記（二）：Bag 介面與實作全家族解析

Java 相關知識

Java 高精度數值計算：指定小數位數、去尾零、最小位數補齊

金融、計量等場景需精確控制小數位。使用 BigDecimal

PureMVC 在 Swing 應用中的實戰入門：架構解析與範例實作

前言 PureMVC 是一個輕量級 MVC 框架，源自 Fl

Java 實現漢諾塔算法：可視化遞歸移動過程完整代碼

漢諾塔問題介紹 漢諾塔是經典的遞歸算法問題： 目標

Java 單例模式全解析：餓漢、懶漢、登記式三大實現與線程安全深度剖析

單例模式確保一個類在全局僅有一個實例，並提供全局訪問點。它是