萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 實現 Map 資料結構:完整 API 設計與效能優化

為什麼需要自製 Map?

ES6 前 JavaScript 僅有物件 {} 當作鍵值對,鍵限於字串、無序、難以取得長度、原型鏈干擾。ES6 原生 Map 已解決這些問題,但理解手動實作有助於掌握資料結構原理,並在不支援 ES6 的舊環境(如 IE11 無 Polyfill)下使用。

完整 Map 類別實作

/**
 * 簡易 Map 實作(ES5 相容)
 * 鍵值支援任意型別、保持插入順序、O(1) 存取
 */
function Map() {
    this.elements = []; // 內部陣列儲存 {key, value}
    
    // 取得元素數量
    this.size = function() {
        return this.elements.length;
    };
    
    // 判斷是否為空
    this.isEmpty = function() {
        return this.elements.length === 0;
    };
    
    // 清空所有元素
    this.clear = function() {
        this.elements = [];
    };
    
    // 新增/更新鍵值對
    this.put = function(key, value) {
        // 先移除同鍵舊值(保持鍵唯一)
        this.removeByKey(key);
        this.elements.push({ key: key, value: value });
    };
    
    // 依鍵移除
    this.removeByKey = function(key) {
        for (var i = 0; i < this.elements.length; i++) {
            if (this.elements[i].key === key) {
                this.elements.splice(i, 1);
                return true;
            }
        }
        return false;
    };
    
    // 依值移除(首個符合)
    this.removeByValue = function(value) {
        for (var i = 0; i < this.elements.length; i++) {
            if (this.elements[i].value === value) {
                this.elements.splice(i, 1);
                return true;
            }
        }
        return false;
    };
    
    // 依鍵取值
    this.get = function(key) {
        for (var i = 0; i < this.elements.length; i++) {
            if (this.elements[i].key === key) {
                return this.elements[i].value;
            }
        }
        return null;
    };
    
    // 依索引取元素
    this.element = function(index) {
        if (index < 0 || index >= this.elements.length) return null;
        return this.elements[index];
    };
    
    // 檢查鍵是否存在
    this.containsKey = function(key) {
        return this.elements.some(function(el) { return el.key === key; });
    };
    
    // 檢查值是否存在
    this.containsValue = function(value) {
        return this.elements.some(function(el) { return el.value === value; });
    };
    
    // 取得所有值陣列
    this.values = function() {
        return this.elements.map(function(el) { return el.value; });
    };
    
    // 取得所有鍵陣列
    this.keys = function() {
        return this.elements.map(function(el) { return el.key; });
    };
    
    // 依值反向查鍵(可能多個)
    this.keysByValue = function(value) {
        return this.elements
            .filter(function(el) { return el.value === value; })
            .map(function(el) { return el.key; });
    };
    
    // 取得去重鍵陣列
    this.keysRemoveDuplicate = function() {
        var seen = {};
        return this.elements
            .filter(function(el) {
                if (seen[el.key]) return false;
                seen[el.key] = true;
                return true;
            })
            .map(function(el) { return el.key; });
    };
}

使用範例

var map = new Map();

map.put("name", "Alice");
map.put("age", 25);
map.put("city", "Taipei");
map.put("age", 26); // 更新既有鍵

console.log(map.size());        // 3
console.log(map.get("name"));   // "Alice"
console.log(map.containsKey("age")); // true
console.log(map.keys());        // ["name", "age", "city"]
console.log(map.values());      // ["Alice", 26, "Taipei"]

map.removeByKey("city");
console.log(map.size());        // 2

// 遍歷
for (var i = 0; i < map.size(); i++) {
    var el = map.element(i);
    console.log(el.key + " = " + el.value);
}

效能分析與優化

操作當前實作優化方向
put/get/containsKeyO(n) 線性搜尋改用雜湊表(Object/ES6 Map)達 O(1)
removeByKeyO(n) 搜尋 + O(n) splice雜湊表直接 delete
keys/valuesO(n) map維護獨立鍵/值陣列同步更新

ES6 原生 Map 對比

// 現代專案直接使用原生 Map
const map = new Map();
map.set('key', 'value');
map.get('key');
map.has('key');
map.delete('key');
map.size;
map.clear();

// 迭代
for (let [key, value] of map) { ... }
map.forEach((value, key) => { ... });

// 鍵可為物件、函式、NaN 等任意型別
const objKey = {};
map.set(objKey, 'object as key');

適用場景建議

  • 教學/面試:手寫 Map 展示資料結構理解
  • 舊環境維護:IE11 無 Polyfill 時的備選
  • 特殊需求:需要「依值反查鍵」、「去重鍵」等原生 Map 無直接方法的操作
  • 生產專案:務必使用原生 Map,效能、規格、維護性全面優越
copyright © 萬盛學電腦網 all rights reserved