Why underscore

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

最近開(kāi)始看 underscore.js 源碼唆迁，并將 underscore.js 源碼解讀 放在了我的 2016 計(jì)劃中。

閱讀一些著名框架類(lèi)庫(kù)的源碼芋簿，就好像和一個(gè)個(gè)大師對(duì)話匿辩，你會(huì)學(xué)到很多束凑。為什么是 underscore杠园？最主要的原因是 underscore 簡(jiǎn)短精悍（約 1.5k 行），封裝了 100 多個(gè)有用的方法筒狠，耦合度低剪芍，非常適合逐個(gè)方法閱讀，適合樓主這樣的 JavaScript 初學(xué)者窟蓝。從中罪裹，你不僅可以學(xué)到用 void 0 代替 undefined 避免 undefined 被重寫(xiě)等一些小技巧 饱普，也可以學(xué)到變量類(lèi)型判斷、函數(shù)節(jié)流&函數(shù)去抖等常用的方法状共，還可以學(xué)到很多瀏覽器兼容的 hack套耕，更可以學(xué)到作者的整體設(shè)計(jì)思路以及 API 設(shè)計(jì)的原理（向后兼容）。

之后樓主會(huì)寫(xiě)一系列的文章跟大家分享在源碼閱讀中學(xué)習(xí)到的知識(shí)峡继。

• underscore-1.8.3 源碼解讀項(xiàng)目地址 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~）您的關(guān)注是樓主繼續(xù)寫(xiě)作的動(dòng)力

數(shù)組去重

今天要聊的，也是我以前筆試時(shí)碰到過(guò)的一個(gè)問(wèn)題碾牌，數(shù)組去重康愤，不知道現(xiàn)在的筆試題還考不考這個(gè)？

數(shù)組去重舶吗，一般需求是給你一個(gè)數(shù)組征冷，調(diào)用去重方法，返回?cái)?shù)值副本誓琼，副本中沒(méi)有重復(fù)元素检激。一般來(lái)說(shuō)，兩個(gè)元素通過(guò) === 比較返回 true 的視為相同元素腹侣，需要去重叔收，所以，1 和 "1" 是不同的元素傲隶，1 和 new Number(1) 是不同的元素饺律，{} 和 {} 是不同的元素（引用不同）。（當(dāng)然如果需求認(rèn)為 {} 和 {} 算作相同的元素跺株，那么解法就不一樣了）

方法一

無(wú)需思考复濒，我們可以得到 O(n^2) 復(fù)雜度的解法。定義一個(gè)變量數(shù)組 res 保存結(jié)果帖鸦，遍歷需要去重的數(shù)組芝薇，如果該元素已經(jīng)存在在 res 中了胚嘲，則說(shuō)明是重復(fù)的元素作儿，如果沒(méi)有，則放入 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"]

代碼非常簡(jiǎn)單攻锰，那么是否能更簡(jiǎn)潔些？如果不考慮瀏覽器兼容妓雾，我們可以用 ES5 提供的 Array.prototype.indexOf 方法來(lái)簡(jiǎn)化代碼娶吞。

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"]

方法二

法一是將原數(shù)組中的元素和結(jié)果數(shù)組中的元素一一比較妒蛇，我們可以換個(gè)思路，將原數(shù)組中重復(fù)元素的最后一個(gè)元素放入結(jié)果數(shù)組中。

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

  for (var i = 0, len = a.length; i < len; i++) {
    for (var j = i + 1; j < len; j++) {
      // 這一步十分巧妙
      // 如果發(fā)現(xiàn)相同元素
      // 則 i 自增進(jìn)入下一個(gè)循環(huán)比較
      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]

雖然復(fù)雜度還是 O(n^2)绣夺，但是可以看到結(jié)果不同吏奸，1 出現(xiàn)在了數(shù)組最后面，因?yàn)榻Y(jié)果數(shù)組取的是元素最后一次出現(xiàn)的位置陶耍。

方法三（sort)

如果筆試面試時(shí)只答出了上面這樣 O(n^2) 的方案奋蔚，可能還不能使面試官滿意，下面就來(lái)說(shuō)幾種進(jìn)階方案烈钞。

將數(shù)組用 sort 排序后泊碑，理論上相同的元素會(huì)被放在相鄰的位置，那么比較前后位置的元素就可以了毯欣。

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]

但是問(wèn)題又來(lái)了馒过，1 和 "1" 會(huì)被排在一起，不同的 Object 會(huì)被排在一起仪媒，因?yàn)樗鼈?toString() 的結(jié)果相同沉桌，所以會(huì)出現(xiàn)這樣的錯(cuò)誤：

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

當(dāng)然你完全可以針對(duì)數(shù)組中可能出現(xiàn)的不同類(lèi)型，來(lái)寫(xiě)這個(gè)比較函數(shù)算吩。不過(guò)這似乎有點(diǎn)麻煩留凭。

方法四 （object）

用 JavaScript 中的 Object 對(duì)象來(lái)當(dāng)做哈希表，這也是幾年前筆試時(shí)的解法偎巢，跟 sort 一樣蔼夜，可以去重完全由 Number 基本類(lèi)型組成的數(shù)組。

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]

還是和方法三一樣的問(wèn)題压昼，因?yàn)?Object 的 key 值都是 String 類(lèi)型求冷，所以對(duì)于 1 和 "1" 無(wú)法分別，我們可以稍微改進(jìn)下窍霞，將類(lèi)型也存入 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" 的問(wèn)題，但是還有別的問(wèn)題但金！

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

但是如果數(shù)組元素全部是基礎(chǔ)類(lèi)型的 Number 值韭山，鍵值對(duì)法應(yīng)該是最高效的！

方法五 （ES6）

ES6 部署了 Set 以及 Array.from 方法冷溃，太強(qiáng)大了钱磅！如果瀏覽器支持，完全可以這樣：

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]

_.unique

最后來(lái)看看 underscore 對(duì)此的實(shí)現(xiàn)方式似枕，underscore 將此封裝到了 _.unique 方法中盖淡，調(diào)用方式為 _.unique(array, [isSorted], [iteratee])。其中第一個(gè)參數(shù)是必須的凿歼，是需要去重的數(shù)組褪迟，第二個(gè)參數(shù)可選冗恨，如果數(shù)組有序，則可以傳入布爾值 true味赃，第三個(gè)參數(shù)可選派近，如果需要對(duì)數(shù)組迭代的結(jié)果去重，則可以傳入一個(gè)迭代函數(shù)洁桌。而數(shù)組元素去重是基于 === 運(yùn)算符的渴丸。

其實(shí)很簡(jiǎn)單，underscore 中的實(shí)現(xiàn)方式和上面的方法一相似另凌。

我們來(lái)看它的核心代碼：

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

  // 如果是有序數(shù)組谱轨，則當(dāng)前元素只需跟上一個(gè)元素對(duì)比即可
  // 用 seen 變量保存上一個(gè)元素
  if (isSorted) {
    // 如果 i === 0，則直接 push
    // 否則比較當(dāng)前元素是否和前一個(gè)元素相等
    if (!i || seen !== computed) result.push(value);
    // seen 保存當(dāng)前元素吠谢，供下一次對(duì)比
    seen = computed;
  } else if (iteratee) {
    // 如果 seen[] 中沒(méi)有 computed 這個(gè)元素值
    if (!_.contains(seen, computed)) {
      seen.push(computed);
      result.push(value);
    }
  } else if (!_.contains(result, value)) {  
    // 如果不用經(jīng)過(guò)迭代函數(shù)計(jì)算土童，也就不用 seen[] 變量了
    result.push(value);
  }
}

外面的循環(huán)遍歷數(shù)組元素，對(duì)于每個(gè)元素工坊，如果數(shù)組有序献汗，則和前一個(gè)元素比較，如果相同王污，則已經(jīng)出現(xiàn)過(guò)罢吃，不加入到結(jié)果數(shù)組中，否則則加入昭齐。而如果有迭代函數(shù)尿招，則計(jì)算傳入迭代函數(shù)后的值，對(duì)值去重阱驾，調(diào)用 _.contains 方法就谜，而該方法的核心就是調(diào)用 _.indexOf 方法，和我們上面說(shuō)的方法一異曲同工里覆。

關(guān)于 _.unique 方法的詳細(xì)代碼丧荐，可以參考 https://github.com/hanzichi/underscore-analysis/blob/master/underscore-1.8.3.js/src/underscore-1.8.3.js#L519-L547

Read More

• 數(shù)組去重 – JS Tips – A JS tip per day!
• Remove Duplicates from JavaScript Array
• 從 JavaScript 數(shù)組去重談性能優(yōu)化