DIV CSS 佈局教程網

高效去除 JS 數組重複項:借助哈希表的實現與分析
編輯:JavaScript基礎知識     

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。若項目需要兼容舊版瀏覽器,則沿用手寫的哈希方案,並記得補上上面提到的三處修正。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved