DIV CSS 佈局教程網

用原生 JavaScript 打造一個 Map:put、get、remove 完整實作
編輯:JavaScript綜合知識     

ES6 之前,JavaScript 沒有原生的 Map 資料結構,工程師只能用物件或陣列硬湊鍵值對。若想理解 Map 的底層思維,自己動手實作一次是最快的方式。以下示範如何用陣列包裝出一個具備 put、get、remove、size、isEmpty 的 Map。

設計思路

核心很單純:用一個陣列保存多個 { key, value } 結構。新增時先搜尋是否已有相同 key,有的話就覆寫值;沒有的話就附加到尾端。查詢則是線性掃描,找到就回傳對應值,找不到回傳 null。

完整程式碼

/**
 * 描述:以陣列模擬 Map 的鍵值對結構
 * @returns {Map}
 */
function Map(){
    var struct = function(key, value) {
        this.key = key;
        this.value = value;
    };

    // 新增鍵值對:key 已存在則更新,否則附加
    var put = function(key, value){
        for (var i = 0; i < this.arr.length; i++) {
            if ( this.arr[i].key === key ) {
                this.arr[i].value = value;
                return;
            }
        };
        this.arr[this.arr.length] = new struct(key, value);
    };

    // 依 key 取值,找不到回傳 null
    var get = function(key) {
        for (var i = 0; i < this.arr.length; i++) {
            if ( this.arr[i].key === key ) {
                return this.arr[i].value;
            }
        }
        return null;
    };

    // 依 key 刪除
    var remove = function(key) {
        var v;
        for (var i = 0; i < this.arr.length; i++) {
            v = this.arr.pop();
            if ( v.key === key ) {
                continue;
            }
            this.arr.unshift(v);
        }
    };

    // 取得鍵值對數量
    var size = function() {
        return this.arr.length;
    };

    // 判斷是否為空
    var isEmpty = function() {
        return this.arr.length <= 0;
    };

    this.arr = new Array();
    this.get = get;
    this.put = put;
    this.remove = remove;
    this.size = size;
    this.isEmpty = isEmpty;
}

使用方式

呼叫習慣刻意對齊 Java 的 Map,遷移過來幾乎零成本:

<script type="text/javascript">
var map = new Map();
map.put("num", 1);
map.put("ss", "wss");

alert(map.size());      // 2
alert(map.get("num"));  // 1

map.remove("num");
alert(map.size());      // 1
alert(map.get("num"));  // null
</script>

實作上的提醒

這個版本以教學為目的,時間複雜度是 O(n):查詢與刪除都要線性掃過整個陣列,資料量大時效能會是瓶頸。另外 remove 用 pop/unshift 反覆搬移元素,寫法雖然直觀,但每次 unshift 都會造成陣列重新索引。
若要在正式專案中使用,建議直接採用 ES6 的 Map;若必須相容舊環境,則可考慮改用「平行陣列 + 雜湊表」的雙結構,把查詢降到接近 O(1)。理解這個原型之後,你會更明白原生 Map 為什麼那樣設計。

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