JS 数组去重与性能优化

javaScript

数组去重可是个经常出现的面试题。常见的类型是这样的：

有数组 var arr = ['a', 'b', 'c', '1', 0, 'c', 1, '', 1, 0]，请用 JavaScript 实现去重函数 unqiue，使得 unique(arr) 返回 ['a', 'b', 'c', '1', 0, 1, '']

作为面试题，需要明白它的考点：

• 1.正确。需要在各式各样的浏览器中保证函数的正确性，其实并不是一个很简单的事情。

• 2.性能。虽然大部分情况下 JavaScript 语言本身（狭义范畴，不包含 DOM 等延拓）不会导致性能问题，但很不幸这是一道考题，因此面试官们还是会把性能作为一个考点。

常见的做法

一个常见的直觉做法可以通过 数组的indexOf 属性来辅助：

function unique(arr){
 var result = [];
 for(var i = 0, length = arr.length; i< length; i++){
    if(result.indexOf(arr[i]) == -1){
        result.push(arr[i]);
    }
 }
 return result;
}

可惜的一个点就是：在 IE6-8 下，数组的 indexOf 方法还不存在。直觉方案要稍微改造一下：

var indexof = [].indexOf 
                ? function(arr, value){
                    return arr.indexOf(value);
                }
                : function(arr, value) {
                   for(var i = 0, length = arr.length; i< length; i++){
                        if(arr[i]) === value){
                            return i;
                        }
                     }
                    return -1;
                }
function unique(arr){
 var result = [];
 for(var i = 0; i< arr.length; i++){
    if(indexof(result, arr[i]) == -1){
        result.push(arr[i]);
    }
 }
 return result;
}

优化方案

上面的实现，竟然需要两层循环。这怎么可以接受呢？我们必须考虑另一种方案来加快这个查询的速度。使用{}来模拟hash表吧：

在这里，使用typeof item + JSON.stringify(item)作为hash的key值，

var array = [{value: 1}, {value: 1}, {value: 2}];
function unique(arr) {
  var ret = []
  var hash = {}
  for (var i = 0; i < arr.length; i++) {
    var item = arr[i]
    var key = typeof(item) + JSON.stringify(item)
    if (hash[key] !== 1) {
      ret.push(item)
      hash[key] = 1
    }
  }
  return ret
}

这个方案不错。如果是在ES6 中，那么必然会更加简单，只需要使用新的 Set 内置类即可。