JavaScript:数组去重

JavaScript的数组去重是一个老生常谈的话题了,随便搜一搜就能找到非常多不同版本的解法,近日总结一下,分析一下优劣。

无有起因,偶与微信公众号一篇文章,深感不错,特此致敬!

定义重复(相等)

要去重,首先得定义,什么叫作“重复”,即具体到代码而言,两个数据在什么情况下可以算是相等的。这并不是一个很容易的问题。
对于原始值而言,我们很容易想到1和1是相等的,’1’和’1’也是相等的。那么,1和’1’是相等的么?
如果这个问题还好说,只要回答“是”或者“不是”即可。那么下面这些情况就没那么容易了。

NaN

初看NaN时,很容易把它当成和null、undefined一样的独立数据类型。但其实,它是数字类型

1
2
//number
console.log(typeof NaN)

根据规范,比较运算中只要有一个值为NaN,则比较结果为false,所以会有下面这些看起来略蛋疼的结论:

1
2
3
4
5
//全都是false
0 < NaN
0 > NaN
0 == NaN
0 === NaN

任何涉及到NaN的情况都不能简单地使用比较运算来判定是否相等。比较科学的方法只能是使用isNaN()

原始值和包装对象

以’a’与new String(‘a’)为例,new String(‘a’)一个包装对象,它和’a’一样,代表一个字符串。它们都可以使用字符串的各种方法(比如trim()),也可以参与字符串运算(+号连接等)。
但他们有一个关键的区别:类型不同

1
2
typeof a;//object
typeof b;//string

在做字符串比较的时候,类型的不同会导致结果有一些出乎意料:

1
2
3
4
5
6
7
8
9
var a1 = 'a'
var a2 = new String('a')
var a3 = new String('a')
a1 == a2 //true
a1 == a3 //true
a2 == a3 //true
a1 === a2 //false
a1 === a3 //false
a2 === a3 //false

同样是表示字符串a的变量,在使用严格比较时竟然不是相等的,在直觉上这是一件比较难接受的事情,在各种开发场景下,也非常容易忽略这些细节

对象和对象

在涉及比较的时候,还会碰到对象。具体而言,大致可以分为三种情况:纯对象、实例对象、其它类型的对象。
纯对象
指代由字面量生成的、成员中不含函数和日期、正则表达式等类型的对象
如果直接拿两个对象进行比较,不管是==还是===,毫无疑问都是不相等的
实例对象
实例对象主要指通过构造函数(类)生成的对象。这样的对象和纯对象一样,直接比较都是不等的,但也会碰到需要判断是否是同一对象的情况。一般而言,因为这种对象有比较复杂的内部结构(甚至有一部分数据在原型上),无法直接从外部比较是否相等。比较靠谱的判断方法是由构造函数(类)来提供静态方法或者实例方法来判断是否相等。

1
2
3
var a = Klass();
var b = Klass();
Klass.isEqual(a,b)

其他对象
其它对象主要指数组、日期、正则表达式等这类在Object基础上派生出来的对象。这类对象各有各的特殊性,一般需要根据场景来构造判断方法,决定两个对象是否相等。
比如,日期对象,可能需要通过Date.prototype.getTime()方法获取时间戳来判断是否表示同一时刻。正则表达式可能需要通过toString()方法获取到原始字面量来判断是否是相同的正则表达式

==和===

在一些文章中,看到某一些数组去重的方法,在判断元素是否相等时,使用的是==比较运算符。众所周知,这个运算符在比较前会先查看元素类型,当类型不一致时会做隐式类型转换。这其实是一种非常不严谨的做法。因为无法区分在做隐匿类型转换后值一样的元素,例如0、’’、false、null、undefined等。
JS三位一体的黑问题:

1
[] == ![] //true

Array.prototype.indexOf()

1
2
3
4
5
6
function unique(arr){
return arr.filter(function(item, index){
//indexof 返回第一个索引值;如果当前索引不是第一个索引,说明是重复值
return arr.indexof(item) === index;
})
}
1
2
3
4
5
6
7
8
9
10
function unique(arr){
var ret = [];
arr.forEach(function(item){
if(ret.indexOf(item) === -1){
ret.push(item)
}
})
return ret;
}
console.log(unique([1,1,23,23,4,5,6,7,7,8,9,8,6,6,NaN,NaN,'1','1','2',null,null,undefined]))

既然==和===在元素相等的比较中是有巨大差别的,那么indexOf的情况又如何呢?大部分的文章都没有提及这点,于是只好求助规范。通过规范,我们知道了indexOf()使用的是严格比较,也就是===。
再次强调:按照前文所述,===不能处理NaN的相等性判断

Array.prototype.includes()

Array.prototype.includes()是ES2016中新增的方法,用于判断数组中是否包含某个元素,所以上面使用indexOf()方法的第二个版本可以改写成如下版本:

1
2
3
4
5
6
7
8
9
10
function unique(arr){
var ret = [];
arr.forEach(function(item){
if(!ret.includes(item)){
ret.push(item)
}
})
return ret;
}
console.log(unique([1,1,23,23,4,5,6,7,7,8,9,8,6,6,NaN,NaN,'1','1','2',null,null,undefined,undefined])

查找规范使用的另一种比较方法,叫作“SameValueZero”比较,includes()是可以正确判断是否包含了NaN的。我们写一段代码验证一下:

1
2
3
var arr =[1,2,NaN];
arr.indexOf(NaN); // -1
arr.includes(NaN); //true

可以看到indexOf()和includes()对待NaN的行为是完全不一样的

从上面的一大段文字中,我们可以看到,要判断两个元素是否相等(重复)并不是一件简单的事情。在了解了这个背景后,我们来看一些前面没有涉及到的去重方案。

遍历

双重遍历是最容易想到的去重方案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function unique(arr){
var ret = [];
var len = arr.length;
var isRepeat;
for(var i =0;i<len ;i++){
isRepeat = false;
console.log(i +'i')
for( var j=i+1;j<len;j++){
if(arr[i] === arr[j]){
isRepeat = true;
console.log(j +'j')
break;
}
}
if(!isRepeat){
ret.push(arr[i])
}
}
return ret;
}
console.log(unique([1,23,23,4,5,6,7,7,8,9,8,6,6,NaN,NaN,'1','1','2',null,null,undefined]))

双重遍历还有一个优化版本,但是原理和复杂度几乎完全一样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function unique(arr){
var ret = [];
var len = arr.length;
for(var i =0;i<len ;i++){
for( var j=i+1;j<len;j++){
if(arr[i] === arr[j]){
j = ++i
}
}
ret.push(arr[i])
}
return ret;
}
console.log(unique([1,23,23,4,5,6,7,7,8,9,8,6,6,NaN,NaN,'1','1','2',null,null,undefined]))

这种方案没什么大问题,用于去重的比较部分也是自己编写实现(arr[i] === arr[j]),所以相等性可以自己针对上文说到的各种情况加以特殊处理。唯一比较受诟病的是使用了双重循环,时间复杂度比较高,性能一般。

使用对象key来去重

1
2
3
4
5
6
7
8
9
10
11
12
13
function unique(arr){
var ret = [];
var len = arr.length;
var tmp = {};
for(var i =0;i<len ;i++){
if(!tmp[arr[i]]){
tmp[arr[i]] = 1;
ret.push(arr[i])
}
}
return ret;
}
console.log(unique([1,23,23,4,5,6,7,7,8,9,8,6,6,NaN,NaN,'1','1','2',null,null,undefined]))

利用了对象(tmp)的key不可以重复的特性来进行去重。但由于对象key只能为字符串,因此这种去重方法有许多局限性:
无法区分隐式类型转换成字符串后一样的值,比如1和’1’
无法处理复杂数据类型,比如对象(因为对象作为key会变成[object Object])
特殊数据,比如’proto‘会挂掉,因为tmp对象的proto属性无法被重写
对于第一点,有人提出可以为对象的key增加一个类型,或者将类型放到对象的value中来解决:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function unique(arr){
var ret = [];
var len = arr.length;
var tmp = {};
var tmpKey;
for(var i =0;i<len ;i++){
tmpKey = typeof arr[i] + arr[i];
if(!tmp[tmpKey]){
tmp[tmpKey] = 1;
ret.push(arr[i])
}
}
return ret;
}
console.log(unique([1,23,23,4,5,6,7,7,8,9,8,6,6,NaN,NaN,'1','1','2',null,null,undefined]))

该方案也同时解决第三个问题
而第二个问题,如果像上文所说,在允许对对象进行自定义的比较规则,也可以将对象序列化之后作为key来使用。这里为简单起见,使用JSON.stringify()进行序列化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function unique(arr){
var ret = [];
var len = arr.length;
var tmp = {};
var tmpKey;
for(var i =0;i<len ;i++){
tmpKey = typeof arr[i] + JSON.stringify(arr[i]);
if(!tmp[tmpKey]){
tmp[tmpKey] = 1;
ret.push(arr[i])
}
}
return ret;
}
console.log(unique([1,23,23,4,5,6,7,7,8,9,8,6,6,NaN,NaN,'1','1','2',null,null,undefined]))

Map Key

可以看到,使用对象key来处理数组去重的问题,其实是一件比较麻烦的事情,处理不好很容易导致结果不正确。而这些问题的根本原因就是因为key在使用时有限制。
那么,能不能有一种key使用没有限制的对象呢?答案是——真的有!那就是ES2015中的Map。
Map是一种新的数据类型,可以把它想象成key类型没有限制的对象。此外,它的存取使用单独的get()、set()接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var tmp = new Map();
tmp.set(1,1)
tmp.get(1) //1
tmp.set('2', 2);
tmp.get('2') //2
tmp.set(true, 3);
tmp.get(true) //3
tmp.set(undefined, 4)
tmp.get(undefined) //4
tmp.set(NaN, 5)
tmp.get(NaN); //5
var arr = [], obj = {};
tmp.set(arr,6);
tmp.get(arr); //6
tmp.set(obj,6);
tmp.get(obj); //6

由于Map使用单独的接口来存取数据,所以不用担心key会和内置属性重名(如上文提到的proto)。使用Map改写一下我们的去重方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
function unique(arr){
var ret = [];
var len = arr.length;
var tmp = new Map();
for(var i =0;i<len ;i++){
if(!tmp.get[arr[i]]){
tmp.set(arr[i], 1);
ret.push(arr[i])
}
}
return ret;
}
console.log(unique([1,23,23,4,5,6,7,7,8,9,8,6,6,NaN,NaN,'1','1','2',null,null,undefined]))

Set

除了Map以外,ES2015还引入了一种叫作Set的数据类型。顾名思义,Set就是集合的意思,它不允许重复元素出现,这一点和数学中对集合的定义还是比较像的。

1
2
3
4
5
6
7
8
9
var s= new Set()
s.add(1)
s.add("1")
s.add(null)
s.add(undefined)
s.add(NaN)
s.add(true)
s.add([])
s.add({})

如果你重复添加同一个元素的话,Set中只会存在一个。包括NaN也是这样。于是我们想到,这么好的特性,要是能和数组互相转换,不就可以去重了吗?

1
2
3
4
function unique(arr){
var set = new Set(arr);
return Array.from(set)
}

有一句话是这么说的“不要因为走得太远而忘了为什么出发”。我们为什么要为数组去重呢?因为我们想得到不重复的元素列表。而既然已经有Set了,我们为什么还要舍近求远,使用数组呢?是不是在需要去重的情况下,直接使用Set就解决问题了?这个问题值得思考

最后,用一个测试用例总结一下文中出现的各种去重方法:

1
2
3
var arr =
[1,1,'1','1',0,0,'0',undefined,undefined,null,null,NaN,{},{},[],[],/a/,/a/]
console.log(unique(arr))

测试中没有定义对象的比较方法,因此默认情况下,对象不去重是正确的结果,去重是不正确的结果
测试用例
任何脱离场景谈技术都是妄谈,本文也一样。去重这道题,没有正确答案,请根据场景选择合适的去重方法。

文章目录
  1. 1.
  2. 2.
    1. 2.1. 定义重复(相等)
      1. 2.1.1. NaN
      2. 2.1.2. 原始值和包装对象
      3. 2.1.3. 对象和对象
    2. 2.2. ==和===
    3. 2.3. Array.prototype.indexOf()
    4. 2.4. Array.prototype.includes()
  3. 3.
    1. 3.1. 遍历
    2. 3.2. 使用对象key来去重
    3. 3.3. Map Key
    4. 3.4. Set
  4. 4.
|