JavaScript 的物件天生就能當雜湊表用,但它和 Java 的 HashMap 有個關鍵差異:key 只能是字串或數字。
你可能會說:obj = {}; map[obj] = 1; 傳的既不是數字也不是字串,卻沒報錯啊。那是因為引擎把 obj 透過內建的 toString 轉成了 "[object Object]" 這個字串——用 for...in 列一下 map 就看得很清楚。所有物件型別的 key 都被塞進同一個格子裡,互相覆蓋。
Java 之所以能接受任意型別的 key,是因為 Object 實作了 hashCode(),而每個類都繼承或重寫了它,於是任何變數都有對應的雜湊值。那我們能不能在 JS 裡如法炮製?
toString 負責轉字串,與之對稱的 valueOf 負責轉數字。既然數字更好當索引,先從它下手:
Object.prototype.valueOf = function () {
alert("Hello~");
};
var map = [];
var obj = {};
map[obj] = 1;
對話框完全沒跳出來,說明引擎根本沒嘗試把 obj 轉成數字。
Object.prototype.toString = function () {
alert("Hello~");
};
var map = {};
var obj = {};
map[obj] = 1;
這次彈出來了。由於我們沒有回傳任何值,那個 1 最後被存進了 map["undefined"]。
由此可見,只要能保證每個物件回傳唯一的字串,就能用最原始的 map[key] 語法索引任意型別的 key:
var HASH_ID = 0;
Object.prototype.toString = function () {
if (this._HASH == null) this._HASH = HASH_ID++;
return "Obj:" + this._HASH;
};
var HashMap = {};
var obj1 = {};
var obj2 = {};
HashMap[obj1] = "Foo1";
HashMap[obj2] = "Foo2";
alert(HashMap[obj1] + " & " + HashMap[obj2]); // Foo1 & Foo2
HashMap[obj1] = "Bar1";
HashMap[obj2] = "Bar2";
alert(HashMap[obj1] + " & " + HashMap[obj2]); // Bar1 & Bar2
obj1 與 obj2 各自對應到固定的索引,互不干擾,第二次寫入也正確地覆蓋了各自的值。
其一,如果某個物件自己重寫了 toString,這套機制就不可靠了——它可能每次回傳不同的值,導致同一個 key 存進不同格子。使用前得先確認 key 物件沒有自訂 toString,或在實作裡改用其他保留屬性(如上面的 _HASH)時先判斷是否已存在。
其二,直接改 Object.prototype 是危險的。它會污染所有物件,特別是在使用 for...in 遍歷時——雖然 ECMAScript 5 之後新增的屬性預設不可枚舉,用 Object.defineProperty 定義能避開這個問題,但更穩妥的做法是把雜湊 ID 存在外部的 WeakMap 裡:
var ids = new WeakMap();
var HASH_ID = 0;
function hashOf(obj) {
if (!ids.has(obj)) ids.set(obj, HASH_ID++);
return ids.get(obj);
}
用 WeakMap 的好處是它不會改動任何原型,而且當 key 物件不再被引用時,對應記錄會自動被回收,不會像 obj._HASH 那樣把人為地續命。這個思路示範的價值在於理解「物件身分識別」這件事本身——而現代 JavaScript 已經有了專門的原生工具來解決它。