JavaScript 数组去重算法：从 O(N^2) 到 O(N) 的优化实践

数组去重 uniq 方法定义

为 Array 本地对象扩展一个原型方法，该方法旨在移除数组中所有重复的条目（无论重复次数多少），并返回一个包含所有被移除重复条目的新数组。

形式化描述：

输入

Array(size=N)

输出

Array1 为原数组中去除重复元素后保持原有顺序的子集，

去重定义为：对于 Array1 中任意两个元素 a 和 b，若 a 不等于 b，则它们不相等。

保序定义为：若元素 a 在原数组 Array 中的下标小于元素 b 的下标，则 a 在 Array1 中的下标也必须小于 b 在 Array1 中的下标。

Array2 定义为 Array 减去 Array1 的结果，且保持原有顺序。

realazy 提出了一种思路清晰的解法：顺序遍历数组中的每个元素，如果该元素的值之前已经访问过，则将其加入 Array2；否则将其加入 Array1。判断当前元素是否已访问过的策略是顺序遍历所有已访问过的元素。

显然，该算法的时间复杂度约为 O(N^2)。

基于桶算法的 O(N) 优化

在 realazy 的算法框架基础上，我对遍历过程中判断元素是否已访问的方式进行了改进。当原数组的值域为正整数且极差（range = max value - min value）较小时，可以采用简单的“桶”算法。

准备一个长度为 range 的布尔数组 b，初始值全为 false。遍历原数组中的每个值 value，如果 b[value] 为 true，说明该值已访问过，将其放入 Array2；否则将其放入 Array1，并将 b[value] 设为 true。

这显然是 O(N) 的算法，但其代价是额外的空间复杂度为 range，且要求原数组的值域必须为正整数。

该方案不难推广至值域为整数的情况，实际上只需考察桶号 value - min(Array)，即可转化为正整数的情形。

基于散列算法的通用实现

为了避免 range 过大造成的空间浪费，在“桶”算法基础上改进为散列算法，具体采用线性同余开散列法。目的是将值域压缩映射到一个可控的小连续正整数子集中，同时保证不同的原象映射到相同象的概率尽可能小，即确保桶与桶之间的负载均衡。

例如，这是一个适用于值域为实数的散列函数：

key = hashFun(value) = Math.floor(value) * 37 % 91

这仍然是 O(N) 的算法（显然 O(N) 是所有 uniq 算法的时间复杂度下界），其好处是可以控制空间开销，并且可以适应非整数值域，只需设计相应的散列函数即可。

以下是桶（bucket）算法的具体实现：

var resultArr = [],

returnArr = [],

origLen = this.length,

resultLen;

var maxv=this[0],minv=this[0];

for (var i=1; i<origLen; ++i){

if(this[i]>maxv)maxv=this[i];

else if(this[i]<minv)minv=this[i];

var blen=maxv-minv+1;

var b=new Array(blen);

for(var i=0;i<blen;++i)b[i]=false;

for (var i=0; i<origLen; ++i){

if (b[this[i]-minv]){

returnArr.push(this[i]);

} else {

resultArr.push(this[i]);

b[this[i]-minv]=true;

resultLen = resultArr.length;

this.length = resultLen;

for (var i=0; i<resultLen; ++i){

this[i] = resultArr[i];

return returnArr;

以下是散列（hash）算法的具体实现：

var shuffler = 37

var beta=0.007;

var origLen=this.length

var bucketSize=Math.ceil(origLen*beta);

var hashSet=new Array(bucketSize);

var hashFun = function(value){

var key = (Math.floor(value)*shuffler)%bucketSize;

return key;

//init hashSet

for(var i=0;i<bucketSize;i++)hashSet[i]=new Array();

var ret=[],self=[];

var key,value;

var bucket,openLen;

var everConflict;

for(var i=0;i<origLen;i++){

value=this[i];

key=hashFun(value);

bucket = hashSet[key];

openLen=bucket.length;//if(openLen>1)return;

everConflict=false;

for(var j=0;j<openLen;j++){

if(bucket[j]==value){

ret.push(value);

everConflict=true;

break;

if(!everConflict){

bucket.push(value);

self.push(value);

selfLen = self.length;

this.length = selfLen;

for (i=0; i<selfLen; ++i){

this[i] = self[i];

//compute average bucket size

var lens=[],sum=0;

for(var i=0;i<hashSet.length ;++i){lens.push(hashSet[i].length);sum+=hashSet[i].length};

average=sum/hashSet.length;//watch lens,average

return ret;

性能测试与对比分析

使用 k*10000 个 0~k*100 的随机整数测试计算时间（ms）

k 1 2 3 4 5

realazy 240 693 1399 2301 3807

bucket 55 101 141 219 293

hash 214 411 654 844 1083

测试框架借鉴了 http://realazy.org/lab/uniq.html

测试环境：Firefox2.0.0.6/Ubuntu7.10/2.66GHzP4/1024MBDDR