摘要：引子數(shù)組去重是一個老生常談的話題，在面試中也經(jīng)常會被問道。其中如果數(shù)組是排序的，去重運算效率更高，因為排序能夠?qū)⑾嗤臄?shù)排列在一起，方便前后比較。當(dāng)數(shù)組有序?qū)τ趯ο蟮娜ブ?，我們知道為，所以使用比較對象在實際場景中沒有意義。

數(shù)組去重是一個老生常談的話題，在面試中也經(jīng)常會被問道。對于去重，有兩種主流思想：

先排序，線性遍歷后去重，時間復(fù)雜度O(n*log2n)；
使用哈希，空間換時間，時間復(fù)雜度O(n);

上一篇文章，我分析了underscore的函數(shù)是如何組織的，我們能夠依照這種方法書寫自己的函數(shù)庫，這篇文章，來看看關(guān)于函數(shù)去重underscore是如何做的？

underscore的去重是指數(shù)組（Arrays）中uniq函數(shù)，其API如下：

uniq   _.uniq(array, [isSorted], [iteratee]) 別名： unique   
說明：返回 array去重后的副本, 使用 === 做相等測試. 如果您確定 array 已經(jīng)排序, 那么給 isSorted  參數(shù)傳遞 true值, 此函數(shù)將運行的更快的算法. 如果要處理對象元素, 傳參 iterator 來獲取要對比的屬性.

上述API主要想說明幾點：

返回數(shù)組副本，不影響原數(shù)組

相等的標準是a===b,表明不僅要值相等，類型也需要相等

如果數(shù)組是排序的，去重運算效率更高

uniq也可以比較對象，前提是需要指定比較的對象屬性

我們簡單使用以下_.uniq(array, [isSorted], [iteratee]),如下：

  console.log(_.uniq([1,4,2,2,3,3]));
  console.log(_.uniq([1,2,2,2,3,3],true));
  console.log(_.uniq([{
            name:1,
            gender:"male"
        },{
            name:2,
            gender:"female"
        },{
            name:2,
            gender:"male"
        },{
            name:4,
            gender:"male"
    }],true,"gender"));

結(jié)果如下：

underscore去重的核心思想：

新建結(jié)果集數(shù)組res，遍歷待去重數(shù)組，將每個遍歷值在res數(shù)組中遍歷檢查，將不存在當(dāng)前res中的遍歷值壓入res中，最后輸出res數(shù)組。

    function uniq(array){
        var res = [];
        array.forEach(function(element) {
            if(res.indexOf(element)<0){
                res.push(element);
            }
        }, this);
        return res;
    }
    console.log(uniq([1,4,2,2,3,3]));  //[1,4,2,3]

其中如果數(shù)組是排序的，去重運算效率更高，因為排序能夠?qū)⑾嗤臄?shù)排列在一起，方便前后比較。

    function uniq(array, isSorted) {
        var res = [];
        var seen = null;

        array.forEach(function (element,index) {
            if (isSorted) { 
                //當(dāng)數(shù)組有序
                if(!index || seen !== element) res.push(element);
                seen = element;
            } else {
                if (res.indexOf(element) < 0) {
                    res.push(element);
                }
            }
        }, this);
        return res;
    }
    console.log(uniq([1,2,"2",3,3,3,5],true)); //(5)?[1, 2, "2", 3, 5]

對于對象的去重，我們知道{}==={}為false，所以使用===比較對象在實際場景中沒有意義。
在這里我舉個實際場景的例子：

我要在小組中選擇一名男生（male）和一名女生（female），小組組員情況如下：

var array = [{
    name:"Tom",
    gender:"female"
},{
    name:"Lucy",
    gender:"female"
},{
    name:"Edward",
    gender:"male"
},{
    name:"Molly",
    gender:"female"
}] 

我們修改上面的uniq：

    function uniq(array, isSorted, iteratee) {
        var res = [];
        var seen = [];
        array.forEach(function (element, index) {
            if (iteratee) {
                //判斷iteratee是否存在，存在的話，取出真正要比較的屬性
                var computed = element[iteratee];
                if (seen.indexOf(computed) < 0) {
                    seen.push(computed);
                    res.push(element);
                }
            } else if (isSorted) {
                //當(dāng)數(shù)組有序
                if (!index || seen !== element) res.push(element);
                seen = element;
            } else {
                if (res.indexOf(element) < 0) {
                    res.push(element);
                }
            }
        }, this);
        return res;
    }
    console.log(uniq([{
            name:"Tom",
            gender:"female"
        },{
            name:"Lucy",
            gender:"female"
        },{
            name:"Edward",
            gender:"male"
        },{
            name:"Molly",
            gender:"female"
        }],true,"gender")); 

結(jié)果如下：

underscore的uniq的實現(xiàn)，基本上使用的上述思想。在附錄中我附上了源碼和一些注釋。

上述我分析了underscore的uniq函數(shù)實現(xiàn)，在這之前我也看過諸如《JavaScript去重的N種方法》...之類的文章，underscore中的uniq函數(shù)實現(xiàn)方法并不是最優(yōu)解，至少從時間復(fù)雜度來講不是最優(yōu)。
那么為什么underscore不用Set對象來解決去重問題，使用indexof查找的時間復(fù)雜度是O(n)，而hash查詢是O(1)。
我個人認為Set是ES6中引的對象，underscore是為了考慮兼容性問題。
那為什么不用obj作為Set的替代方案呢?
這里我猜是underscore的設(shè)計者只想用自己內(nèi)部實現(xiàn)的_.indexOf函數(shù)。此處是我的猜測，大家如果有想法，歡迎大家留言！
下面我附上ES6的實現(xiàn)（大家最熟悉的）：

var a = [1,1,2,3,4,4];
var res = [...new Set(a)];

再附上obj的實現(xiàn)：

    function uniq(array,iteratee){
        var res = [];
        var obj = {};
        array.forEach(function(element) {
            var computed = element;
            if(iteratee) computed = element[iteratee];
            if(!obj.hasOwnProperty(computed))
                obj[(typeof computed)+"_"+JSON.stringify(computed)] = element;
            }, this);
            for(var p in obj){
                res.push(obj[p]);
            }
            return res;
        }
    uniq([1,"1",2,3,4,4]);// (5)?[1, "1", 2, 3, 4]

underscore的uniq函數(shù)源碼及注釋：

    _.uniq = _.unique = function(array, isSorted, iteratee, context) {
    if (array == null) return [];
    if (!_.isBoolean(isSorted)) {
      //如果沒有排序
      context = iteratee;
      iteratee = isSorted;
      isSorted = false;
    }
    /**
    ** 此處_.iteratee
    **  function (key){
    *      return function(obj){
    *        return obj[key];
    *      }
    **  }
    **  key就是這里的iteratee（對象的屬性）,這里使用了閉包
    **/
    if (iteratee != null) iteratee = _.iteratee(iteratee, context); 
    var result = [];//返回去重后的數(shù)組（副本）
    var seen = [];
    for (var i = 0, length = array.length; i < length; i++) {
      var value = array[i];//當(dāng)前比較值
      if (isSorted) {
        //如果i=0時，或者seen（上一個值）不等于當(dāng)前值，放入去重數(shù)組中
        if (!i || seen !== value) result.push(value); 
        seen = value;//保存當(dāng)前值，用于下一次比較
      } else if (iteratee) {
        var computed = iteratee(value, i, array);
        if (_.indexOf(seen, computed) < 0) {
          seen.push(computed);
          result.push(value);
        }
      } else if (_.indexOf(result, value) < 0) {
        result.push(value);
      }
    }
    return result;
  };