Array 類型本身並沒有提供去重方法,需要自己實現。下面這種基於哈希表的寫法在實用場景中效率相當不錯。
function hovercUnique(arr) {
var result = [], hash = {};
for (var i = 0, elem; (elem = arr[i]) != null; i++) {
if (!hash[elem]) {
result.push(elem);
hash[elem] = true;
}
}
return result;
}
做法是用一個對象 hash 充當「已出現過」的登記表:遍歷數組時,把元素值當作鍵去查 hash,第一次見到就推進 result 並在 hash 中標記,之後再遇到則跳過。
相比 O(n²) 的雙重循環,這種做法把查找降到 O(1),整體時間複雜度為 O(n)。核心在於用空間換時間:多消耗一個對象的內存,換來的是遍歷一次即可。
var h_array = ["hovertree", "easysector", "hovertree", "keleyi",
"keleyi", "何問起", "hovertree", "hoverclock",
"yestop", 163, "何問起", 163];
document.write("原始元素個數:" + h_array.length + "<br>");
var h_result = hovercUnique(h_array);
document.write("去重後個數:" + h_result.length + "<br>");
document.write(h_result.join("<br>"));
第一,遇到 null、undefined 或 0 會提前終止。循環條件 (elem = arr[i]) != null 用的是寬鬆不等,當某項為 null 或 undefined 時循環就結束了,後面的元素根本不會被處理。若數組中可能出現這類值,應改成標準的長度判斷:
for (var i = 0; i < arr.length; i++) {
var elem = arr[i];
if (!hash[elem]) { result.push(elem); hash[elem] = true; }
}
第二,用對象做哈希表會把值隱式轉為字符串。數字 1 與字符串 "1" 在 hash 中指向同一個鍵,因此會被誤判為重複。同理,hash[elem] 為假值判斷也有缺陷——若某個鍵對應的值恰好是 0 或空字符串,判斷會出錯,嚴謹的寫法應改用 hasOwnProperty:
if (!hash.hasOwnProperty(elem)) { ... }
第三,對象元素永遠不會被去重。兩個內容相同的對象是不同的引用,轉成字符串後都會變成 "[object Object]",因此第一個之後全部被當作重複。若數組中存放對象,需要自行定義比較規則(例如按某個 id 字段去重)。
ES6 提供了 Set,語義明確且沒有上述轉字符串的問題:
// 方法一:Array.from
var unique = Array.from(new Set(arr));
// 方法二:展開運算符
var unique = [...new Set(arr)];
// 對象數組按字段去重
var list = [{id:1}, {id:2}, {id:1}];
var seen = new Set();
var result = list.filter(item => {
if (seen.has(item.id)) return false;
seen.add(item.id);
return true;
});
Set 依據 SameValueZero 算法判斷相等,能正確區分 1 與 "1",也能處理 NaN。若項目需要兼容舊版瀏覽器,則沿用手寫的哈希方案,並記得補上上面提到的三處修正。