在資料處理、標籤篩選、清單渲染這類場景裡,「把重複項目清掉」幾乎是每個前端工程師都會遇到的需求。問題在於,網路上流傳的寫法少說有五六種,各自的取捨卻很少被講清楚。本文整理三種常見的陣列去重思維,並用十萬筆資料實測它們的耗時差異,最後補充現代 JavaScript 更簡潔的替代方案。
核心想法是拿一個空物件當索引表,走訪陣列時把每個值當成鍵去查表,查不到就視為首次出現。由於物件屬性讀寫接近常數時間,整體只需一次迴圈。
Array.prototype.unique = function () {
var newArr = [], obj = {};
for (var i = 0, len = this.length; i < len; i++) {
if (!obj[this[i]]) {
newArr.push(this[i]);
obj[this[i]] = true;
}
}
return newArr;
}; // 約 10ms
但這個版本有兩個盲點:數字 1 與字串 '1' 會被當成同一個鍵;而 {x:1} 這類物件會被統一轉成 "[object Object]",因此不同物件也會互相吃掉。
改良方式是把型別一起拼進鍵名,讓型別不同的值互不干擾:
Array.prototype.unique = function () {
var newArr = [], obj = {};
for (var i = 0, len = this.length; i < len; i++) {
var key = typeof (this[i]) + this[i];
if (!obj[key]) {
newArr.push(this[i]);
obj[key] = this[i];
}
}
return newArr;
}; // 約 30ms
代價是多了字串拼接與型別判斷,速度略慢,但語意正確得多。注意物件型別仍然無法真正區分,這是所有雜湊法的共同極限。
最直覺的做法:外層固定一個位置,內層往後掃,遇到相同就 splice 移除並把索引回退一格。
Array.prototype.unique = function () {
var newArr = this.concat();
for (var i = 0, len = newArr.length; i < len; i++) {
for (var j = i + 1; j < newArr.length; j++) {
if (newArr[i] === newArr[j]) {
newArr.splice(j, 1);
j--;
}
}
}
return newArr;
}; // 約 250ms
它用 === 嚴格比較,因此結果最貼近「真正相等」的定義,連物件參考也分得清。缺點是時間複雜度退化成 O(n²),加上 splice 本身要搬移元素,資料量一大就非常吃力。
把結果收進暫存陣列,用 indexOf 判斷是否已存在,不存在才推入。程式碼短、可讀性高。
Array.prototype.unique = function () {
var newArr = [];
for (var i = 0, len = this.length; i < len; i++) {
if (newArr.indexOf(this[i]) === -1) {
newArr.push(this[i]);
}
}
return newArr;
}; // 約 25ms
它同樣是嚴格相等比較,效能比雙層迴圈好一截,但仍然是 O(n²) 量級,而且無法處理物件內容相同的情況。
測試用的原始資料是一份混合了數字、字串與物件的樣本陣列,再用亂數反覆取樣湊成十萬筆:
var arr = [], num;
for (var i = 0; i < 100000; i++) {
num = Math.floor(Math.random() * 50);
arr.push(arr0[num]);
}
var t1 = new Date().getTime();
arr.unique();
var t2 = new Date().getTime();
console.log(t2 - t1);
同一份資料下,雜湊法約 10~30ms,indexOf 約 25ms,雙層迴圈則要 250ms 上下。差距接近十倍,資料量越大越明顯。
上述三種寫法都出自 Array.prototype 擴充的年代,如今有更好的選擇。ES6 的 Set 天生不含重複值,一行就能完成去重:
var unique = [...new Set(arr)];
如果需要依特定欄位判斷重複(例如以 id 為鍵),可以用 filter 搭配 Map 或索引物件:
var byId = arr.filter(function (item, i, list) {
return list.findIndex(function (o) { return o.id === item.id; }) === i;
});
結論很簡單:追求簡潔與效能就用 Set;需要自訂比較邏輯時,用索引物件搭配一次走訪;只有在必須嚴格區分物件參考、且資料量不大的舊專案裡,雙層迴圈才還有一席之地。另外,直接改寫原生 prototype 容易與第三方套件互撞,實務上建議改成獨立工具函式。