DIV CSS 佈局教程網

JavaScript 陣列去重的五種解法與效能比較
編輯:JavaScript綜合知識     

陣列去重是前端面試的高頻題,也是實務上真的會遇到的需求。本文先給一個自己寫的直觀版本,再對照幾種常見寫法,順便談談各自的陷阱。

版本一:indexOf 逐項檢查

Array.prototype.unique = function () {
  var oldArr = this,
      newArr = [oldArr[0]],
      len = oldArr.length,
      i = 1;

  if (!len) return this;

  for (; i < len; i++) {
    newArr.indexOf(oldArr[i]) < 0 ? newArr.push(oldArr[i]) : '';
  }

  return newArr;
};

var arr = ['a', 'a', 'b', 'a', 'c', 'd'];
console.log(arr.unique());  // ["a", "b", "c", "d"]

邏輯直白:預留第一個元素,後續每個元素先問 indexOf「你在新陣列裡嗎?」,不在才推進去。回傳新陣列,不動到原陣列。

自己寫一遍的好處是邏輯在腦中清楚,之後要擴充很容易——改成針對物件屬性去重、或同時處理多個陣列,都是順著這條思路往下長。

但這裡有個問題:直接掛在 Array.prototype 上會污染全域,任何 for...in 遍歷陣列的程式碼都可能因此出錯。實務上請寫成獨立函式。

版本二:以物件做雜湊表

function oSort(arr) {
  var result = {};
  var newArr = [];
  for (var i = 0; i < arr.length; i++) {
    if (!result[arr[i]]) {
      newArr.push(arr[i]);
      result[arr[i]] = 1;
    }
  }
  return newArr;
}

用一個暫存物件記錄「看過哪些值」,查詢是 O(1),整體降到 O(n)。這是最經典的去重手法。

版本三:for...in 加 indexOf

var student = ['qiang', 'ming', 'tao', 'li', 'liang', 'you', 'qiang', 'tao'];

function unique(arr) {
  var tmp = [];
  for (var i in arr) {
    // 該元素在 tmp 中不存在才追加
    if (tmp.indexOf(arr[i]) == -1) {
      tmp.push(arr[i]);
    }
  }
  return tmp;
}

概念與版本一相同,只是換成 for...in。要提醒的是,for...in 會遍歷繼承來的可列舉屬性,處理陣列時用傳統 for 或 forEach 更安全。

版本四:把值與索引對調

function unique(arr) {
  var tmp = [];
  for (var m in arr) {
    tmp[arr[m]] = 1;   // 值當鍵,重複的自動覆蓋
  }

  var tmparr = [];
  for (var n in tmp) {
    tmparr.push(n);    // 再把鍵倒回來當值
  }
  return tmparr;
}

想法相當聰明:利用物件鍵的唯一性,重複值在賦值時自然被合併,最後把鍵名倒回陣列。缺點是所有值都被轉成字串,1 與 "1" 會被視為同一個。

版本五:封裝成可重用的函式

/**
 * 去除陣列重複元素
 */
function uniqueArray(data) {
  data = data || [];
  var a = {};

  for (var i = 0; i < data.length; i++) {
    var v = data[i];
    if (typeof (a[v]) == 'undefined') {
      a[v] = 1;
    }
  }

  data.length = 0;          // 清空原陣列
  for (var i in a) {
    data[data.length] = i;
  }
  return data;
}

用 data.length = 0 清空陣列是個值得記的技巧,比重新指派人參更快也更乾淨。

幾個實務上的判斷

上面五種寫法思路相近,效能差異主要在「查詢是否為 O(1)」:版本二與版本五用物件做雜湊,明顯快於版本一、三、四的線性搜尋。

但雜湊法有個共同的弱點——型別會被字串化,而且像 __proto__ 這種鍵名會造成物件原型污染。若要處理數字、物件或混合型別,用 Set 才是正確答案:

function unique(arr) {
  return [...new Set(arr)];
}

// 依物件屬性去重
function uniqueBy(arr, key) {
  var seen = new Set();
  return arr.filter(function (item) {
    if (seen.has(item[key])) return false;
    seen.add(item[key]);
    return true;
  });
}

Set 的值比較使用 SameValueZero 演算法,能正確區分 1 與 "1",也不會有原型污染的顧慮。面試時寫出版本二展現思路,再補一句「實務上我會用 Set」,通常是比較完整的回答。

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