引子
数组去重是一个老生常谈的话题，在面试中也经常会被问道。对于去重，有两种主流思想：
先排序，线性遍历后去重，时间复杂度 O(n*log2n)；
使用哈希，空间换时间，时间复杂度 O(n);
上一篇文章，我分析了 underscore 的函数是如何组织的，我们能够依照这种方法书写自己的函数库，这篇文章，来看看关于函数去重 underscore 是如何做的？
Underscore 的去重
功能介绍
underscore 的去重是指数组（Arrays）中 uniq 函数，其 API 如下：
uniq _.uniq(array, [isSorted], [iteratee]) 别名：unique 说明：返回 array 去重后的副本, 使用 === 做相等测试. 如果您确定 array 已经排序, 那么给 isSorted 参数传递 true 值, 此函数将运行的更快的算法. 如果要处理对象元素, 传参 iterator 来获取要对比的属性.
上述 API 主要想说明几点：
返回数组副本，不影响原数组
相等的标准是 a ===b, 表明不仅要值相等，类型也需要相等
如果数组是排序的，去重运算效率更高
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”));
结果如下：
去重思想及实现
underscore 去重的核心思想：
新建结果集数组 res，遍历待去重数组，将每个遍历值在 res 数组中遍历检查，将不存在当前 res 中的遍历值压入 res 中，最后输出 res 数组。
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]
其中如果数组是排序的，去重运算效率更高，因为排序能够将相同的数排列在一起，方便前后比较。
function uniq(array, isSorted) {
var res = [];
var seen = null;
array.forEach(function (element,index) {
if (isSorted) {
// 当数组有序
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) {
// 当数组有序
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”));
结果如下：underscore 的 uniq 的实现，基本上使用的上述思想。在附录中我附上了源码和一些注释。
关于去重的思考
上述我分析了 underscore 的 uniq 函数实现，在这之前我也看过诸如《JavaScript 去重的 N 种方法》… 之类的文章，underscore 中的 uniq 函数实现方法并不是最优解，至少从时间复杂度来讲不是最优。那么为什么 underscore 不用 Set 对象来解决去重问题，使用 indexof 查找的时间复杂度是 O(n)，而 hash 查询是 O(1)。我个人认为 Set 是 ES6 中引的对象，underscore 是为了考虑兼容性问题。那为什么不用 obj 作为 Set 的替代方案呢? 这里我猜是 underscore 的设计者只想用自己内部实现的_.indexOf 函数。此处是我的猜测，大家如果有想法，欢迎大家留言！下面我附上 ES6 的实现（大家最熟悉的）：
var a = [1,1,2,3,4,4];
var res = […new Set(a)];
再附上 obj 的实现：
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 函数源码及注释：
_.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 = [];// 返回去重后的数组（副本）
var seen = [];
for (var i = 0, length = array.length; i < length; i++) {
var value = array[i];// 当前比较值
if (isSorted) {
// 如果 i = 0 时，或者 seen（上一个值）不等于当前值，放入去重数组中
if (!i || seen !== value) result.push(value);
seen = value;// 保存当前值，用于下一次比较
} 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;
};