JavaScript数组去重的三种实现方式与性能对比分析

基于对象键值的去重实现

在一次前端面试中，我被要求实现数组去重功能。最初考虑的是利用对象存储键值对的方法，具体实现代码如下：

 
Array.prototype.distinct1 = function() {
var i=0,tmp={},that=this.slice(0)
this.length=0;
for(;i<that.length;i++){
if(!(that[i] in tmp)){
this[this.length]=that[i];
tmp[that[i]]=true;
} 
} 
return this;
}; 

双重循环去重及其局限性

上述方法逻辑直观且实现简单，但在处理类型不同却能转换为相同字符串的数据时（例如数字1与字符串"1"）会出现误判，导致去重失败。因此，接下来尝试使用传统的双重循环方式，代码示例如下：

 
Array.prototype.distinct2 = function() {
var i=0,flag,that=this.slice(0);
this.length=0;
for(;i<that.length;i++){
var tmp=that[i];
flag=true;
for(var j=0;j<this.length;j++){
if(this[j]===tmp){flag=false;break}
} 
if(flag)this[this.length]=tmp;
} 
return this;
}; 

结合类型判断的优化方案

虽然双重循环能准确得到去重结果，但其时间复杂度较高，执行效率较低。为了在第一种方法的基础上进行优化，我们引入类型判断机制：在存储键值的同时记录数组项的数据类型，若遇到新类型则将其拼接到类型字符串中；查找时，若发现已存储类型字符串中包含当前项类型，则将其从存储字符串中移除（此处逻辑似有笔误，原意应为判断类型是否已存在），具体代码如下：

 
Array.prototype.distinct4 = function() {
var i=0,tmp={},t2,that=this.slice(0),one;
this.length=0;
for(;i<that.length;i++){
one=that[i];
t2=typeof one;
if(!(one in tmp)){
this[this.length]=one;
tmp[one]=t2;
}else if(tmp[one].indexOf(t2)==-1){
this[this.length]=one;
tmp[one]+=t2;
} 
} 
return this;
}; 

不同浏览器下的性能测试对比

为了直观展示不同算法在极端数据情况下的效率差异，我们选取了几组测试用例进行验证。首先测试数组中1至80所有项均不重复且循环执行1000次的情况，结果如下（注：IE6浏览器性能表现较弱）：

IE9:Chrome: Firefox: IE6:

接着测试数组中80项全部重复且循环执行1000次的情况。综合上述数据可知，除IE6至IE8外，其他现代浏览器中双重循环法的表现均较为优异；而在IE6至IE8中，双重循环法的执行速度比其他方法慢10至20倍左右。如果你的项目仅需支持IE9及以上版本的浏览器，可以安全使用双重循环法；否则，建议采用基于键值的方法，并根据具体数据特征选择方法一或方法三（图中所示为方法四，原方法三使用了Array的indexOf，因速度较慢且不兼容旧版浏览器而未列入对比图表）：

IE9： Chrome： Firefox： IE6：