前端►js

函数封装之数组去重

数组去重是编程中十分重要的方法，这篇文章将介绍多个数组去重的方法。

JS的数组去重

数组去重，顾名思义是要将数组中的重复数值去除，所以数值比对我们都需要使用 === 运算符。

然而去重我们还需要一些注意东西:

  1. NaN===NaN 为 false
    在去重时，我们应该是希望 NaN 是只保留一个，所以 NaN 需要做额外判断。

测试数据

我们将JS中存在的一些基础数据类型都列出来，构建一个简单的测试用例。

1
2
3
4
5

var obj1={x:1};
var obj2={x:2};
var textArr=[true,false,undefined,1,null,'true','undefined','null','1',obj1,obj2,obj1,obj2];

双重循环去重

数组去重一般最先想到的可能就是双循环去重，建立一个新数组，将没有重复的放到新数组中，循环比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

function unique_2loop(arr){//最简单的双循环去重
  var i,j;
  var result=[];
  var l=arr.length;
  loop1:
  for(i=0;i<l;i++){
    var rl=result.length;

    for(j=0;j<rl;j++){
      if(arr[i]===result[j]||typeof arr[i] ==='number' && typeof result[i] ==='number' && isNaN(arr[i])&&isNaN(result[i])){
        continue loop1;
      }
    }
    result.push(arr[i]);
  }
  return result;
}

unique_2loop(textArr);//[true, false, undefined, 1, null, "true", "undefined", "null", "1", obj1, obj2]

这样看起来我们可能觉的有点复杂，第二重循环我们用 indexOf 可以去掉这样代码更加直观。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

function unique_2loop_indexOf(arr){
  var result=[];
  var l=arr.length;
  var haveNaN=false;//标记是否有了NaN

  for(var i=0;i<l;i++){
    var rl=result.length;
    var data=arr[i];
    if(result.indexOf(data)===-1||typeof data ==='number' && isNaN(data) && !haveNaN){
      if(!haveNaN&&isNaN(data))haveNaN=true;
      result.push(data);
    }
  }

  return result;
}

unique_2loop_indexOf(textArr);//[true, false, undefined, 1, null, "true", "undefined", "null", "1", obj1, obj2]

甚至是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

function unique_2loop_indexOf_forEach(arr){
  var result = [];
  var haveNaN=false;//标记是否有了NaN

  arr.forEach((data)=>{
    if(result.indexOf(data)===-1||typeof data ==='number' && isNaN(data) && !haveNaN){
      if(!haveNaN&&isNaN(data))haveNaN=true;
      result.push(data);
    }
  });

  return result;
}

unique_2loop_indexOf_forEach(textArr);//[true, false, undefined, 1, null, "true", "undefined", "null", "1", obj1, obj2]

但是这些方法，由于采用了双重循环，当处理大数据时耗时特别长，所以只能用来处理一些较小的数组。

Hash表快速去重

双重循环去重的时间较长，而快速提升去重速度的方法大都是采用构建Hash标识的方式。

比如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

function unique_hash(arr){
  var result = [];
  var hashMap={};

  arr.forEach((data)=>{
    if(!hashMap[data]){
      result.push(data);
      hashMap[data]=true;
    }
  });

  return result;
}

unique_hash(textArr);//[true, false, undefined, 1, null, obj1]

然而结果和我们想想的不一样！你会发现，并没有真正的完成去重，因为使用对象作为Hash表时键值对中的键值会转化为 string 类型,

比如 true 变成了 'true',

所以我们必须分数据类型进行Hash表存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function unique_hash_type(arr){
  var result = [];
  var hashMap={};

  arr.forEach((data)=>{
    var type=typeof data;
    if(!hashMap[type])hashMap[type]={};
    if(!hashMap[type][data]){
      result.push(data);
      hashMap[type][data]=true;
    }
  });

  return result;
}

unique_hash_type(textArr);//[true, false, undefined, 1, null, "true", "undefined", "null", "1", obj1]

这里我们会发现 object 类型的数据依然没有正确的处理，因为 object 转换为 string 类型时，调用的 toString 都是获得的 [object Object]

同理我们来看 function 类型，虽然function 类型转化为 string 类型时，它展示的是源码，但是它的字符串过长，在比对时将会消耗大量时间，因为 function 类型的根源依然是 object 类型，所以我们可以将 function 类型当作 object 类型一同处理。

Hash表Object对象的处理

由于在JS不能获取Object对象的引用的特征，我们只能在Object对象的身上开刀，我们可以尝试在Object对象上进行标记来实现目的，然后在完成后去除标记即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

function unique_hash_type_sign(arr){
  var result = [];
  var objs = [];
  var hashMap={};
  var data,sign,type,l=arr.length;//标记

  for(var i=0;i<l;i++){
    data=arr[i];
    type=typeof data;
    if(type === 'object' || type === 'function'){
      sign="__sign__";//标记的键值
      while(true){
        if(data[sign] !== undefined){
          if(data[sign]===data){
            break;//存在重复的
          }else{//冲突避免
            sign+='_';
          }
        }else{
          objs.push({
            obj:data,
            str:sign
          });
          data[sign]=data;
          result.push(data);
          break;
        }
      }
    }else{
      if(!hashMap[type])hashMap[type]={};
      if(!hashMap[type][data]){
        hashMap[type][data]=true;
        result.push(data);
      }
    }
  }

  l=objs.length;
  for(i=0;i<l;i++){
    var obj=objs[i];
    delete obj.obj[obj.str];
  }

  return result;
}

unique_hash_type_sign(textArr);//[true, false, undefined, 1, null, "true", "undefined", "null", "1", obj1, obj2]

sort()排序后进行处理

使用Hash表会占据大量的存储空间，为了快速排序，我们可以使用sort()函数进行排序后在比较，这是我们只需要进行前后比较就可以实现去重，但是顺序还改变。

同时使用sort()对对象数组进行排序时，排序结果不确定，无法使用于含有对象的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

function unique_hash_sort(arr){
  if(arr.length===0)return [];
  arr= arr.slice().sort();
  var result=[];
  var haveNaN=false;
  result.push(arr[0]);
  arr.reduce((last,data)=>{

    if(data !== last||typeof data ==='number' && isNaN(data) && !haveNaN){
      if(!haveNaN&&isNaN(data))haveNaN=true;
      result.push(data);
    }

    return data
  });

  return result;
}

unique_hash_sort(textArr);//[1, "1", obj1, obj2, obj1, obj2, false, null, "null", "true", true, "undefined", undefined]

ES6新姿势

上面的方法都是利用ES5实现的，为嘛不使用ES6的Map之类的呢？，因为ES6只需要一行就可以啦~~

1
2
3
4
5
6
7

function unique_ES6_arrFrom(arr){
  return Array.from(new Set(arr));
}

unique_ES6(textArr);//[true, false, undefined, 1, null, "true", "undefined", "null", "1", obj1, obj2]

或者

1
2
3
4
5
6
7

function unique_ES6_Set(arr){
  return [...new Set(arr)];
}

unique_ES6(textArr);//[true, false, undefined, 1, null, "true", "undefined", "null", "1", obj1, obj2]

性能比较

那么上述的各个函数性能如何呢？

函数\测试数据 10 100 1000 10000 100000 500000 1000000 备注
双重循环去重(unique_2loop) <0ms <0ms ≈2ms ≈200ms ?? ?? ?? 无
双重循环去重(unique_2loop_indexOf) <0ms ≈0.03ms ≈0.3ms ≈11ms ≈1100ms ?? ?? 无
双重循环去重(unique_2loop_indexOf_forEach) <0ms ≈0.03ms ≈0.3ms ≈11ms ≈1100ms ?? ?? 无
Hash表快速去重(unique_hash_type_sign) <0ms ≈0.003ms ≈0.26ms ≈0.5ms ≈7.82ms ≈53.59ms ≈109.56ms 无
sort()排序后快速去重 ≈0.05ms ≈0.05ms ≈0.35ms ≈5ms ≈59ms ≈332ms ≈734ms 这个没有进行对对象数组的测试，因为无法去重对象
ES6新姿势(unique_ES6_arrFrom) ≈0.01ms ≈0.01ms ≈0.2ms ≈1.54ms ≈18ms ≈115ms ≈263ms 无
ES6新姿势(unique_ES6_Set) ≈0.01ms ≈0.013ms ≈0.13ms ≈1.14ms ≈14ms ≈93ms ≈229ms 无

PS：以上的数据都是采用通过处理10组(hash以及ES6为100组)相同数据，然后取平均值获得。

从这个表可以看出双循环是最慢的，慢到后面的数据我都等不下去了= =|||。

sort排序去重速度相较双循环要快的多，实现也比较简单。

Hash表快速去重的速度的ES6的去重很快，毕竟是O(n)的算法，但是在非ES6环境下实现较复杂。只有在数据多，而且含有大量对象的时候推荐使用。

当然ES6处理就简单的多啦~。

简单的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

;(function(){

  Array.prototype.unique=Array.prototype.unique||
  function(){
    var arr=this;
    if(window.Set&&Array.from){
      return Array.from(new Set(arr));
    }

    var result = [];
    var objs = [];
    var hashMap={};
    var data,sign,type,l=arr.length;//标记

    for(var i=0;i<l;i++){
      data=arr[i];
      type=typeof data;
      if(type === 'object' || type === 'function'){
        sign="__sign__";//标记的键值
        while(true){
          if(data[sign] !== undefined){
            if(data[sign]===data){
              break;//存在重复的
            }else{//冲突避免
              sign+='_';
            }
          }else{
            objs.push({
              obj:data,
              str:sign
            });
            data[sign]=data;
            result.push(data);
            break;
          }
        }
      }else{
        if(!hashMap[type])hashMap[type]={};
        if(!hashMap[type][data]){
          hashMap[type][data]=true;
          result.push(data);
        }
      }
    }

    l=objs.length;
    for(i=0;i<l;i++){
      var obj=objs[i];
      delete obj.obj[obj.str];
    }
    return result;
  }

}())

var obj1={x:1};
var obj2={x:2};
[true,false,undefined,1,null,'true','undefined','null','1',obj1,obj2,obj1,obj2].unique();
//[true, false, undefined, 1, null, "true", "undefined", "null", "1", obj1, obj2]

END

2017-03-01 编写完成

2017-02-20 立项