Semper crescis Aut decrescis Vita detestabilis Nunc obdurat Et tunc curat Ludo mentis aciem Nunc obdurat Et tunc curat Ludo mentis aciem Egestatem Potestatem Dissolvit ut glaciem Divano Divano me Divano messi Divano messia Divano messia Divano Divano me Divano messia Divano messia Sors salutis Et virtutis Michi nunc contraria Est affectus Et defectus Semper in angaria Hac in hora Sine mora Corde pulsum tangite Divano Divano me Divano messi Divano messia Divano messia Divano Divano me Divano messia Divano messia Divano Divano me Divano messia Divano messia In divanooooo Sors salutis Et virtutis Michi nunc contraria Est affectus Et defectus Semper in angaria Hac in hora Sine mora Corde pulsum tangite Divano Divano me Divano messi Divano messia Divano messia Divano Divano me Divano messia Divano messia Hac in hora Sine mora Corde pulsum tangite Quod per sortem Sternit fortem Mecum omnes plangite 说到 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 时:

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


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

[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 数组去重