以下實作在 Array 原型上擴充一個方法,用來去除陣列中的重複項。
Array.prototype.del = function () {
var a = {}, c = [], l = this.length;
for (var i = 0; i < l; i++) {
var b = this[i];
var d = (typeof b) + b; // 把型別與值一起當成雜湊鍵
if (a[d] === undefined) {
c.push(b);
a[d] = 1;
}
}
return c;
};
這段程式碼有兩個設計值得說明。
第一,它用「物件當雜湊表」來記錄已出現的值,把每次的查詢從 O(n) 降為接近 O(1),整體複雜度由 O(n²) 降為 O(n)。
第二,var d = (typeof b) + b 把型別名稱拼在值前面當鍵。這是為了區分 1(數字)與 "1"(字串)——若不加上型別,物件的鍵一律是字串,兩者會被誤判為同一個值。
不該擴充 Array.prototype。為內建物件加上可枚舉屬性,會汙染所有陣列的 for-in 迴圈,也容易與其他函式庫衝突。改成獨立函式是更安全的做法。
物件值一律失效。(typeof b) + b 對物件來說會得到 "[object Object]",於是任意兩個不同的物件都會被視為重複。類似的問題也出現在陣列與 null 上。
原型鏈上的屬性可能造成誤判。用單純的 {} 當雜湊表時,若某個值剛好是 "constructor" 或 "toString",a[d] 會取到繼承而來的值而非 undefined,導致錯誤判斷。
// ES6 Set:最簡潔,且正確處理各種型別
const unique = arr => [...new Set(arr)];
// filter + indexOf:適合無法用 Set 的環境
const unique2 = arr => arr.filter((v, i) => arr.indexOf(v) === i);
// 需要自訂相等規則時(例如依物件某個屬性去重)
const byId = arr => {
const seen = new Set();
return arr.filter(item => {
const key = item.id;
if (seen.has(key)) return false;
seen.add(key);
return true;
});
};
Set 的優勢在於它使用 SameValueZero 比較演算法,能正確區分型別,也能正確處理 NaN(Set 視 NaN 等於 NaN,而 indexOf 找不到 NaN)。若需要「判斷是否存在重複」而非去重,用 new Set(arr).size !== arr.length 一句話就能得到答案。