摘要：而數組元素去重是基于運算符的。而如果有迭代函數，則計算傳入迭代函數后的值，對值去重，調用方法，而該方法的核心就是調用方法，和我們上面說的方法一異曲同工。

（覺得這部分眼熟的可以直接跳到下一段了...）

最近開始看 underscore.js 源碼，并將 underscore.js 源碼解讀 放在了我的 2016 計劃中。

閱讀一些著名框架類庫的源碼，就好像和一個個大師對話，你會學到很多。為什么是 underscore？最主要的原因是 underscore 簡短精悍（約 1.5k 行），封裝了 100 多個有用的方法，耦合度低，非常適合逐個方法閱讀，適合樓主這樣的 JavaScript 初學者。從中，你不僅可以學到用 void 0 代替 undefined 避免 undefined 被重寫等一些小技巧 ，也可以學到變量類型判斷、函數節流&函數去抖等常用的方法，還可以學到很多瀏覽器兼容的 hack，更可以學到作者的整體設計思路以及 API 設計的原理（向后兼容）。

之后樓主會寫一系列的文章跟大家分享在源碼閱讀中學習到的知識。

underscore-1.8.3 源碼解讀項目地址 https://github.com/hanzichi/underscore-analysis

underscore-1.8.3 源碼全文注釋 https://github.com/hanzichi/underscore-analysis/blob/master/underscore-1.8.3.js/underscore-1.8.3-analysis.js

underscore-1.8.3 源碼解讀系列文章 https://github.com/hanzichi/underscore-analysis/issues

歡迎圍觀~ （如果有興趣，歡迎 star & watch~）您的關注是樓主繼續寫作的動力

今天要聊的，也是我以前筆試時碰到過的一個問題，數組去重，不知道現在的筆試題還考不考這個？

數組去重，一般需求是給你一個數組，調用去重方法，返回數值副本，副本中沒有重復元素。一般來說，兩個元素通過 === 比較返回 true 的視為相同元素，需要去重，所以，1 和 "1" 是不同的元素，1 和 new Number(1) 是不同的元素，{} 和 {} 是不同的元素（引用不同）。（當然如果需求認為 {} 和 {} 算作相同的元素，那么解法就不一樣了）

無需思考，我們可以得到 O(n^2) 復雜度的解法。定義一個變量數組 res 保存結果，遍歷需要去重的數組，如果該元素已經存在在 res 中了，則說明是重復的元素，如果沒有，則放入 res 中。

function unique(a) {
  var res = [];

  for (var i = 0, len = a.length; i < len; i++) {
    var item = a[i];

    for (var j = 0, jLen = res.length; j < jLen; j++) {
      if (res[j] === item)
        break;
    }

    if (j === jLen)
      res.push(item);
  }

  return res;
}

var a = [1, 1, "1", "2", 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]

代碼非常簡單，那么是否能更簡潔些？如果不考慮瀏覽器兼容，我們可以用 ES5 提供的 Array.prototype.indexOf 方法來簡化代碼。

function unique(a) {
  var res = [];

  for (var i = 0, len = a.length; i < len; i++) {
    var item = a[i];

    (res.indexOf(item) === -1) && res.push(item);
  }

  return res;
}

var a = [1, 1, "1", "2", 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]

既然用了 indexOf，那么不妨再加上 filter。

function unique(a) {

  var res = a.filter(function(item, index, array) {
    return array.indexOf(item) === index;
  });
  
  return res;
}


var a = [1, 1, "1", "2", 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]

法一是將原數組中的元素和結果數組中的元素一一比較，我們可以換個思路，將原數組中重復元素的最后一個元素放入結果數組中。

function unique(a) {
  var res = [];

  for (var i = 0, len = a.length; i < len; i++) {
    for (var j = i + 1; j < len; j++) {
      // 這一步十分巧妙
      // 如果發現相同元素
      // 則 i 自增進入下一個循環比較
      if (a[i] === a[j])
        j = ++i;
    }

    res.push(a[i]);
  }

  return res;
}


var a = [1, 1, "1", "2", 1];
var ans = unique(a);
console.log(ans); // => ["1", "2", 1]

雖然復雜度還是 O(n^2)，但是可以看到結果不同，1 出現在了數組最后面，因為結果數組取的是元素最后一次出現的位置。

如果筆試面試時只答出了上面這樣 O(n^2) 的方案，可能還不能使面試官滿意，下面就來說幾種進階方案。

將數組用 sort 排序后，理論上相同的元素會被放在相鄰的位置，那么比較前后位置的元素就可以了。

function unique(a) {
  return a.concat().sort().filter(function(item, pos, ary) {
    return !pos || item != ary[pos - 1];
  });
}


var a = [1, 1, 3, 2, 1, 2, 4];
var ans = unique(a);
console.log(ans); // => [1, 2, 3, 4]

但是問題又來了，1 和 "1" 會被排在一起，不同的 Object 會被排在一起，因為它們 toString() 的結果相同，所以會出現這樣的錯誤：

var a = [1, 1, 3, 2, 1, 2, 4, "1"];
var ans = unique(a);
console.log(ans); // => [1, 2, 3, 4]

當然你完全可以針對數組中可能出現的不同類型，來寫這個比較函數。不過這似乎有點麻煩。

用 JavaScript 中的 Object 對象來當做哈希表，這也是幾年前筆試時的解法，跟 sort 一樣，可以去重完全由 Number 基本類型組成的數組。

function unique(a) {
  var seen = {};

  return a.filter(function(item) {
    return seen.hasOwnProperty(item) ? false : (seen[item] = true);
  });
}


var a = [1, 1, 3, 2, 1, 2, 4];
var ans = unique(a);
console.log(ans); // => [1, 3, 2, 4]

還是和方法三一樣的問題，因為 Object 的 key 值都是 String 類型，所以對于 1 和 "1" 無法分別，我們可以稍微改進下，將類型也存入 key 中。

function unique(a) {
  var ret = [];
  var hash = {};

  for (var i = 0, len = a.length; i < len; i++) {
    var item = a[i];

    var key = typeof(item) + item;

    if (hash[key] !== 1) {
      ret.push(item);
      hash[key] = 1;
    }
  }

  return ret;
}


var a = [1, 1, 3, 2, "4", 1, 2, 4, "1"];
var ans = unique(a);
console.log(ans); // => [1, 3, 2, "4", 4, "1"]

雖然解決了討厭的 1 和 "1" 的問題，但是還有別的問題！

var a = [{name: "hanzichi"}, {age: 30}, new String(1), new Number(1)];
var ans = unique(a);
console.log(ans); // => [Object, String]

但是如果數組元素全部是基礎類型的 Number 值，鍵值對法應該是最高效的！

ES6 部署了 Set 以及 Array.from 方法，太強大了！如果瀏覽器支持，完全可以這樣：

function unique(a) {
  return Array.from(new Set(a));
}

var a = [{name: "hanzichi"}, {age: 30}, new String(1), new Number(1)];
var ans = unique(a);
console.log(ans); // => [Object, Object, String, Number]

最后來看看 underscore 對此的實現方式，underscore 將此封裝到了 _.unique 方法中，調用方式為 _.unique(array, [isSorted], [iteratee])。其中第一個參數是必須的，是需要去重的數組，第二個參數可選，如果數組有序，則可以傳入布爾值 true，第三個參數可選，如果需要對數組迭代的結果去重，則可以傳入一個迭代函數。而數組元素去重是基于 === 運算符的。

其實很簡單，underscore 中的實現方式和上面的方法一相似。

我們來看它的核心代碼：

for (var i = 0, length = getLength(array); i < length; i++) {
  var value = array[i],
      // 如果指定了迭代函數
      // 則對數組每一個元素進行迭代
      computed = iteratee ? iteratee(value, i, array) : value;

  // 如果是有序數組，則當前元素只需跟上一個元素對比即可
  // 用 seen 變量保存上一個元素
  if (isSorted) {
    // 如果 i === 0，則直接 push
    // 否則比較當前元素是否和前一個元素相等
    if (!i || seen !== computed) result.push(value);
    // seen 保存當前元素，供下一次對比
    seen = computed;
  } else if (iteratee) {
    // 如果 seen[] 中沒有 computed 這個元素值
    if (!_.contains(seen, computed)) {
      seen.push(computed);
      result.push(value);
    }
  } else if (!_.contains(result, value)) {  
    // 如果不用經過迭代函數計算，也就不用 seen[] 變量了
    result.push(value);
  }
}

外面的循環遍歷數組元素，對于每個元素，如果數組有序，則和前一個元素比較，如果相同，則已經出現過，不加入到結果數組中，否則則加入。而如果有迭代函數，則計算傳入迭代函數后的值，對值去重，調用 _.contains 方法，而該方法的核心就是調用 _.indexOf 方法，和我們上面說的方法一異曲同工。

關于 _.unique 方法的詳細代碼，可以參考 https://github.com/hanzichi/underscore-analysis/blob/master/underscore-1.8.3.js/src/underscore-1.8.3.js#L519-L547

數組去重 – JS Tips – A JS tip per day!

Remove Duplicates from JavaScript Array

從 JavaScript 數組去重談性能優化