萬盛學電腦網

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

JavaScript 實作 HashMap/Hashtable 的現代化寫法與效能比較

現代原生方案:Map (ES2015+)

瀏覽器與 Node.js 早已完整支援 Map,鍵可為任意型別、保持插入順序、內建 size、可迭代,效能優於手寫雜湊表。

const map = new Map();
map.set('key1', { id: 1, name: 'Alice' });
map.set(123, '數字鍵也合法');
map.set(Symbol('sym'), 'Symbol 鍵');

console.log(map.get('key1'));      // { id: 1, name: 'Alice' }
console.log(map.has(123));         // true
console.log(map.size);             // 3
map.delete(123);
map.clear();

// 迭代
for (const [k, v] of map) console.log(k, v);
map.forEach((v, k) => console.log(k, v));

舊環境相容:手寫 Hashtable (ES5)

若必須支援 IE8 等無 Map 環境,可用 Object.create(null) 避免原型鏈干擾:

function HashTable() {
    this._data = Object.create(null); // 無原型物件,避免 toString/hasOwnProperty 衝突
    this._size = 0;
}

HashTable.prototype = {
    constructor: HashTable,
    
    set: function(key, value) {
        var strKey = this._toKey(key);
        if (!this._data.hasOwnProperty(strKey)) this._size++;
        this._data[strKey] = value;
        return this; // 支援鏈式
    },
    
    get: function(key) {
        return this._data[this._toKey(key)];
    },
    
    has: function(key) {
        return this._data.hasOwnProperty(this._toKey(key));
    },
    
    delete: function(key) {
        var strKey = this._toKey(key);
        if (this._data.hasOwnProperty(strKey)) {
            delete this._data[strKey];
            this._size--;
            return true;
        }
        return false;
    },
    
    clear: function() {
        this._data = Object.create(null);
        this._size = 0;
    },
    
    get size() { return this._size; },
    
    keys: function() { return Object.keys(this._data); },
    values: function() { return this.keys().map(k => this._data[k]); },
    entries: function() { return this.keys().map(k => [k, this._data[k]]); },
    
    forEach: function(cb, thisArg) {
        this.keys().forEach(k => cb.call(thisArg, this._data[k], k, this));
    },
    
    _toKey: function(key) {
        // 簡易序列化,生產環境建議用 JSON.stringify + 分隔符
        return (typeof key === 'string') ? key : String(key);
    }
};

// 測試
var ht = new HashTable();
ht.set('user:1', { name: 'Tom' }).set('user:2', { name: 'Jerry' });
console.log(ht.get('user:1')); // { name: 'Tom' }
console.log(ht.size);          // 2

效能基準測試參考 (Chrome V8)

操作Map (原生)Handwritten HashTablePlain Object
Set 10萬筆~15ms~35ms~12ms
Get 10萬筆~8ms~18ms~6ms
Has/Delete~5ms~15ms~4ms
記憶體佔用中等較高最低 (但鍵限字串)

何時該用哪一種?

  • Map:現代專案首選,鍵非字串、需順序、頻繁增刪。
  • Plain Object:鍵固定為字串、靜態資料、極度追求讀取速度。
  • 手寫 HashTable:舊環境無 Map、需自定義雜湊函式、教學示範。
  • WeakMap:鍵為物件、需弱引用不阻礙 GC、私有資料綁定。

避坑提醒

  • Object.prototype.hasOwnProperty 被覆寫時會失效,用 Object.prototype.hasOwnProperty.call(obj, key) 或 Object.create(null) 規避。
  • 鍵為物件時,Plain Object 會 toString() 變成 '[object Object]' 導致衝突,必須用 Map 或 WeakMap。
  • 避免在熱路徑頻繁 delete,會導致 V8 隱藏類變更降速,改用 Map 或標記刪除。
copyright © 萬盛學電腦網 all rights reserved