DIV CSS 佈局教程網

用 JS 模擬 Map 與 List 資料結構
編輯:關於JavaScript     

JavaScript 沒有內建的 Map 與 List(ES6 之前),但用物件與陣列可以模擬出相近的介面。以下是兩個實作,附上介面說明。

Map 實作

/*
 * MAP 對象,實現 MAP 功能
 *
 * 接口:
 * size()            獲取 MAP 元素個數
 * isEmpty()         判斷 MAP 是否為空
 * clear()           刪除 MAP 所有元素
 * put(key, value)   向 MAP 中增加元素(key, value)
 * remove(key)       刪除指定 KEY 的元素,成功返回 True,失敗返回 False
 * get(key)          獲取指定 KEY 的元素值 VALUE,失敗返回 NULL
 * element(index)    獲取指定索引的元素,失敗返回 NULL
 * containsKey(key)  判斷 MAP 中是否含有指定 KEY 的元素
 * containsValue(value) 判斷 MAP 中是否含有指定 VALUE 的元素
 * values()          獲取 MAP 中所有 VALUE 的數組
 * keys()            獲取 MAP 中所有 KEY 的數組
 */
function Map() {
    this.elements = new Array();

    // 獲取 MAP 元素個數
    this.size = function () {
        return this.elements.length;
    };

    // 判斷 MAP 是否為空
    this.isEmpty = function () {
        return (this.elements.length < 1);
    };

    // 刪除 MAP 所有元素
    this.clear = function () {
        this.elements = new Array();
    };

    // 向 MAP 中增加元素(key, value)
    this.put = function (_key, _value) {
        this.elements.push({
            key : _key,
            value : _value
        });
    };

    // 刪除指定 KEY 的元素,成功返回 True,失敗返回 False
    this.remove = function (_key) {
        var bln = false;
        try {
            for (i = 0; i < this.elements.length; i++) {
                if (this.elements[i].key == _key) {
                    this.elements.splice(i, 1);
                    return true;
                }
            }
        } catch (e) {
            bln = false;
        }
        return bln;
    };

    // 獲取指定 KEY 的元素值 VALUE,失敗返回 NULL
    this.get = function (_key) {
        try {
            for (i = 0; i < this.elements.length; i++) {
                if (this.elements[i].key == _key) {
                    return this.elements[i].value;
                }
            }
        } catch (e) {
            return null;
        }
    };

    // 獲取指定索引的元素,失敗返回 NULL
    this.element = function (_index) {
        if (_index < 0 || _index >= this.elements.length) {
            return null;
        }
        return this.elements[_index];
    };

    // 判斷 MAP 中是否含有指定 KEY 的元素
    this.containsKey = function (_key) {
        var bln = false;
        try {
            for (i = 0; i < this.elements.length; i++) {
                if (this.elements[i].key == _key) {
                    bln = true;
                }
            }
        } catch (e) {
            bln = false;
        }
        return bln;
    };

    // 判斷 MAP 中是否含有指定 VALUE 的元素
    this.containsValue = function (_value) {
        var bln = false;
        try {
            for (i = 0; i < this.elements.length; i++) {
                if (this.elements[i].value == _value) {
                    bln = true;
                }
            }
        } catch (e) {
            bln = false;
        }
        return bln;
    };

    // 獲取 MAP 中所有 VALUE 的數組
    this.values = function () {
        var arr = new Array();
        for (i = 0; i < this.elements.length; i++) {
            arr.push(this.elements[i].value);
        }
        return arr;
    };

    // 獲取 MAP 中所有 KEY 的數組
    this.keys = function () {
        var arr = new Array();
        for (i = 0; i < this.elements.length; i++) {
            arr.push(this.elements[i].key);
        }
        return arr;
    };
}

List 實作

/**
 * js 實現 list
 */
function List() {
    this.value = [];

    /* 添加 */
    this.add = function (obj) {
        return this.value.push(obj);
    };

    /* 大小 */
    this.size = function () {
        return this.value.length;
    };

    /* 返回指定索引的值 */
    this.get = function (index) {
        return this.value[index];
    };

    /* 刪除指定索引的值 */
    this.remove = function (index) {
        this.value.splice(index, 1);
        return this.value;
    };

    /* 刪除全部值 */
    this.removeAll = function () {
        return this.value = [];
    };

    /* 是否包含某個對象 */
    this.constains = function (obj) {
        for (var i in this.value) {
            if (obj == this.value[i]) {
                return true;
            } else {
                continue;
            }
        }
        return false;
    };

    /* 取得全部內容字串 */
    this.getAll = function () {
        var allInfos = '';
        for (var i in this.value) {
            if (i != (this.value.length - 1)) {
                allInfos += this.value[i] + ",";
            } else {
                allInfos += this.value[i];
            }
        }
        return allInfos;
    };
}

這些實作的問題

作為理解資料結構的練習很有價值,但仔細看會發現幾個值得檢討的設計:

  • put 不去重複。真正的 Map 語意是同一個 key 只能有一個值,再 put 應該覆蓋而非新增。這裡直接 push,導致 put('a', 1); put('a', 2) 之後 get('a') 會拿到 1,且 size 變成 2。
  • 所有查詢都是 O(n) 線性掃描。這是模仿陣列而非真正的 Map,資料量大時效能很差。
  • try-catch 沒有意義。程式碼裡沒有任何會丟例外的操作,包 try 只是掩蓋問題。
  • 迴圈變數漏宣告。for (i = 0; ...) 少了 var,i 會變成全域變數,在多個實例並用時互相干擾。這是很容易忽略的 bug。
  • getAll 用 for...in 遍歷陣列。for...in 會列出原型鏈上的可列舉屬性,不保證順序,不該用於陣列。
  • 方法名拼錯。constains 應該是 contains。

ES6 已經內建了

現在完全不需要自己實作:

var map = new Map();
map.set('a', 1);
map.set('a', 2);          // 覆蓋,不新增
map.get('a');             // 2
map.has('a');             // true
map.delete('a');
map.size;

// Map 還支援任意型別當 key(物件、函式都可以),並保持插入順序
var objKey = { id: 1 };
map.set(objKey, 'value');

原生 Map 相比手寫版本有幾個關鍵優勢:key 可以是任何型別而不只是字串;大小查詢是 O(1);保持插入順序;不會與 Object.prototype 的屬性混淆(用 {} 當 map 時,obj['constructor'] 會拿到意外的東西)。

至於 List,JavaScript 的陣列本來就具備 push、pop、splice、indexOf、includes 這些能力,包一層只是增加間接成本。如果需要的是「不可變清單」語意,直接用 Object.freeze() 或搭配 structuredClone 更合適。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved