算法導論 11.1-4 - 大數組直接定址字典 O(1) 初始化技巧

問題

陣列極大 (如 2³²)，無法 O(N) 初始化。需實現直接定址字典：
SEARCH/INSERT/DELETE 均 O(1)，初始化 O(1)，每元素 O(1) 空間。

核心思想：延遲初始化 + 栈式索引

• 真實資料存放在動態陣列 (棧) stack[]，大小 = 當前元素數。
• 大數組 big[] 只存 stack 的索引 (初始值未定義無所謂)。
• top 指向棧頂，有效索引範圍 [0, top]。

操作細節

INSERT(key, val)

1. stack[++top] = {key, val}
2. big[key] = top

SEARCH(key)

1. idx = big[key]
2. 若 idx < 0 || idx > top → 不存在。
3. 若 stack[idx].key != key → 碰撞/殘留垃圾值，不存在。
4. 否則回傳 stack[idx].val。

DELETE(key)

1. 先 SEARCH 確認存在，得 idx。
2. 將棧頂元素 stack[top] 移至 idx：
   　　stack[idx] = stack[top]
3. 更新大數組：big[stack[idx].key] = idx
4. --top，big[key] = -1 (或任意無效值)。

C++ 參考實現

struct Node { int key, val; };

class DirectAddressDict {
    vector big;   // 大數組，存 stack 索引
    vector stk;  // 棧，存真實節點
    int top = -1;
public:
    DirectAddressDict(int BIG_SIZE, int MAX_ELEM) : big(BIG_SIZE), stk(MAX_ELEM) {}

    void insert(int key, int val) {
        stk[++top] = {key, val};
        big[key] = top;
    }
    bool search(int key, int& val) {
        int idx = big[key];
        if (idx < 0 || idx > top) return false;
        if (stk[idx].key != key) return false;
        val = stk[idx].val;
        return true;
    }
    void erase(int key) {
        int idx = big[key];
        if (idx < 0 || idx > top) return;
        if (stk[idx].key != key) return;
        stk[idx] = stk[top];
        big[stk[idx].key] = idx;
        big[key] = -1;
        --top;
    }
};

正確性證明

• 有效性：big[key] 指向的 stk 位置若在 [0,top] 且 key 匹配，必為最新插入值 (DELETE 會更新)。
• 無誤判：未初始化的 big[key] 可能落在 [0,top]，但 stk[idx].key != key 會攔截。
• 複雜度：所有操作純陣列存取，O(1) 最壞情況。

應用場景

• 稀疏圖邊查詢 (點對極多、實際邊極少)。
• 巨大鍵空間 (IPv6、64-bit ID) 的存在性檢查。
• 任何「初始化成本不可接受」的直接定址場景。

這是教科書級的「空間換時間 + 延遲綁定」經典技巧，工程上常見於位圖、稀疏集合實現。