學習資源

https://labuladong.online/algo/data-structure-basic/linear-probing-code/

學習記錄

今天是學習的第 15 天，主要學習了線性探查法的兩種程式碼實現：

搬移資料版本

這種作法的思路是 remove 刪除元素後，重新整理後續元素的位置，以保持元素的連續性，搬移資料的這個過程也稱為 rehash。

remove(key) {
    const index = this.findKeyIndex(key);
    if (!this.table[index]) {
        return;
    }
    this.table[index] = null;
    // 保持元素的連續性，搬移資料（這個過程稱為 rehash）
    let nextIndex = (index + 1) % this.table.length;
    while (this.table[nextIndex]) {
        const entry = this.table[nextIndex];
        this.table[nextIndex] = null;
        // 這個操作是關鍵，利用 put 方法，將鍵值對重新插入
        this.put(entry.key, entry.val);
        nextIndex = (nextIndex + 1) % this.table.length;
    }
}

特殊佔位符標記版本

這種作法的思路是通過一個 DELETE 特殊值作為佔位符，來標記被刪除的元素。

remove(key) {
    const index = this.findKeyIndex(key);
    if (index === -1) {
        // key 不存在，不需要 remove
        return;
    }
    // 直接用佔位符表示刪除
    this.table[index] = this.DELETED;
}

當我們使用 findIndexKey 方法查找索引的時候，需要對 DELETED 做特殊處理。

// 線性探查法查找 key 在 table 中的索引
// 如果找不到，返回 -1
findKeyIndex(key) {
    // 因為標記刪除元素時只是標記為 DELETE，並不是真的刪除，所以 table 可能會被填滿，導致死循環
    // step 用來記錄查找的步數，防止死循環
    let step = 0;
    // 注意環形陣列特性
    for (let i = this.hash(key); this.table[i] !== null; i = (i + 1 ) % this.table.length) {
        // 防止死循環
        if (++step > this.table.length) {
            return -1;
        }
        // 遇到佔位符直接跳過
        if (this.table[i] === this.DELETED) {
            continue;
        }
        if (this.table[i].key === key) {
            return i;
        }
    }

    return -1;
}

特殊值標記版本

使用 DUMMY 佔位符來標記已刪除的位置。

// 被刪除的 KVNode 的佔位符
DUMMY = new KVNode(null, null);

remove(key) {
    ...
    // 開始 remove
    // 直接用佔位符表示刪除
    this.table[index] = this.DUMMY;
    ...
}

學習總結

• 搬移資料版本是在刪除之後，重新整理後續元素的位置
• 特殊佔位符版本是通過一個 DELETE 特殊值作為佔位符，來標記被刪除的元素
• 特殊值標記版本使用 DUMMY 來標記已刪除的位置