从数组去重来看 javascript 的进化

说到 javascript 数据去重，估计所有做前端的都并不陌生
数组去重的算法即使在实际生产中不一定用的多，但是在面试中几乎成为了必考的题目
这是一个神奇的题目，看上去好像是死的，应该已经没有什么发挥空间了
但事实上它随着 ECMAScript 标准的发展，数据去重的实现反倒是在不断变化
许多公司甚至可以单从一个数组去重直接看出一个前端工程师的大致水平
今天我也来说说我所知道的 javascript 数组去重吧

一、最传统的实现方式

var array = [1, 0, 1, NaN, '1', '', true, false, true];
var result = [];
var i, j;
var flag;
for (i = 0; i < array.length; i++) {
  flag = true;
  for (j = 0; j < result.length; j++) {
    if (array[i] === result[j]) {
      flag = false;
      break;
    }
  }
  if (flag) {
    result.push(array[i]);
  }
}
console.log(result);
// 输出结果：[1, 0, NaN,"1","", true, false]

这种写法在 ECMAScript 3 的标准（也就是 ECMA-262 第 3 版）下，还可以稍微缩写一下

var array = [1, 0, 1, NaN, '1', '', true, false, true];
Array.prototype.uniq = function() {
  var result = [];
  for (var i = 0; i < this.length; i++) {
    if (result.indexOf(this[i]) === -1) {
      result.push(this[i]);
    }
  }
  return result;
}
console.log(array.uniq());
// 输出结果：[1, 0, NaN,"1","", true, false]

这就是我所说的最传统的方式，几乎所有学过编程的都能想得到，逻辑简单粗暴，而且大多数情况下都管用

二、借助 javascript 对象的特性来构造 hash 表实现去重

上面最传统的写法，我说大多数情况下管用，没有说绝对好用，事实上是因为它确实有缺陷
比如当数组中存在多个 NaN 时：

1	var array = [1, 0, 1, NaN, '1', '', true, false, true, NaN];

上面的第一种方法就会返回以下结果：

1	[1, 0, NaN, "1", "", true, false, NaN]

可见，第一种方法无法去掉 NaN 的重复，所以后来有人就想到了第二种方法
借助 javascript 对象天然的 hash 特性来去除数组中重复的值

var array = [1, 0, 1, NaN, '1', '', true, false, true, NaN];
Array.prototype.uniq = function() {
  var result = [], map = {};
  for (var i = 0; i < this.length; i++) {
    map[this[i]] = this[i];
  }
  for (var key in map) {
    result.push(map[key]);
  }
  return result;
}
console.log(array.uniq());
// 输出结果 [0,"1", NaN,"", true, false]

去重成功，说明这种方法是可行的，而且这样子去重的速度比前面第一种方式要快得多，因为只有一层循环，所以时间复杂度为 O(n)
相比前面的两层循环（时间复杂度为Ο(n2)），确实有了质的提升。
不过输出结果似乎跟前面相比，除了 NaN 去掉了之外，数字 1 和字符串 1 也被当成重复的给去掉了
所以使用这种方法去重的时候，需要注意这种方法跟前面的去重方式相比，有一种本质性的不同
前面的去重是用三个等号判断的，也就是强类型去重，而这种使用 hash 表的去重方法，其实是借助转换成字符串的方式去重
这种借助 hash 表中的 key（字符串类型）的去重方式，不属于强类型去重，也不属于弱类型去重（因为 NaN == NaN 不成立），它应该属于一种独特的去重方式
往往我们对这种去重方式还是不满意，因为它把数字 1 和字符串 1 也给合并了，我们可以稍微修改一下，在 key 里面同时加上类型：

var array = [1, 0, 1, NaN, '1', '', true, false, true, NaN];
Array.prototype.uniq = function() {
  var result = [], map = {};
  for (var i = 0; i < this.length; i++) {
    map[typeof this[i] + this[i]] = this[i];
  }
  for (var key in map) {
    result.push(map[key]);
  }
  return result;
}
console.log(array.uniq());
// 输出结果 [1, 0, NaN,"1","", true, false]

这样子基本上就算是实现了我们预期的目标了，同时支持了去除 NaN 的功能

三、借助 ECMAScript 5 的新特性进行简写

上面的写法在发展到 ES5 以后有了更简便的写法，可以借助过滤函数 filter 进行优化：

var array = [1, 0, 1, NaN, '1', '', true, false, true, NaN];
Array.prototype.uniq = function() {
  var map = {};
  return this.filter(function(item) {
    var key = typeof item + item;
    return map.hasOwnProperty(key) ? false : (map[key] = true);
  })
}
console.log(array.uniq());
// 输出结果 [1, 0, NaN,"1","", true, false]

四、借助 ECMAScript 6 的新特性进行简写

到了 ES6 还有更简便的写法，第一种是借助 Map 对象和箭头函数语法糖：

var array = [1, 0, 1, NaN, '1', '', true, false, true, NaN];
Array.prototype.uniq = function() {
  const seen = new Map();
  return this.filter(a => !seen.has(a) && seen.set(a, true))
}
console.log(array.uniq());
// 输出结果 [1, 0, NaN,"1","", true, false]

第二种是直接借助 Set：

var array = [1, 0, 1, NaN, '1', '', true, false, true, NaN];
Array.prototype.uniq = function() {
  return Array.from(new Set(this));
}
console.log(array.uniq());
// 输出结果 [1, 0, NaN,"1","", true, false]

可见，发展到 ES6 之后，已经可以一行就实现数组去重了
不由得感叹一下，标准的发展使得生产真是越来越便利了！

参考资料：

Remove Duplicates from JavaScript Array
求一个 javascript 数组去重方法？
也谈 JavaScript 数组去重
 JavaScript 数组去重