JavaScript 数组去重（uniq）的多种实现方案与性能对比

JavaScript 数组去重实现方案

以下是可直接使用的修正版代码示例。

下文将提供进阶教程与详细说明，适合希望深入理解原理的读者参考。

首先分析 YUI 库处理数组去重的实现逻辑：

 
var toObject = function(a) {
var o = {};
for (var i = 0; i < a.length; i = i+1) {
o[a[i]] = true;
} 
return o;
}; 
var keys = function(o) {
var a=[], i;
for (i in o) {
if (lang.hasOwnProperty(o, i)) { // YUI的方法
a.push(i);
} 
} 
return a;
}; 
var uniq = function(a) {
return keys(toObject(a));
}; 

详细分析过程，可参考同事 长天 分享的《巧妙去除数组中的重复项》一文。

单循环优化方案

作者使用的方案与 YUI 类似，但仅通过一次循环即可完成去重，具体实现如下：

 
var uniq = function (arr) {
var a = [],
o = {},
i,
v,
len = arr.length;
if (len < 2) {
return arr;
} 
for (i = 0; i < len; i++) {
v = arr[i];
if (o[v] !== 1) {
a.push(v);
o[v] = 1;
} 
} 
return a;
} 

经过简单测试，作者提出的单循环方式性能显著优于 YUI 的双循环方式。

旨在抛砖引玉，欢迎读者提供更优的处理方法。

2009年12月28日更新：

上述两种函数方法暂时无法处理包含混合类型的复杂数组（感谢 小猫 提出的疑问），例如：[0,"0",1,"1",0] 或 ["null",null]。

混合类型数组处理

若数组元素类型可约定为数字（注：要求非0开头的数字，小数除外）或字符串，可采用改进后的函数方法（感谢 closurecache 提供的思路）：

 
var uniq = function (arr) {
var a = [],
o = {},
i,
v,
cv, // corrected value
len = arr.length;
if (len < 2) {
return arr;
} 
for (i = 0; i < len; i++) {
v = arr[i];
/* closurecache 提供的函数中使用的是 cv = v + 0;
* 这样就无法辨别类似[1, 10, "1", "10"]的数组，
* 因为运算后 => 1, 10, 10, 100，很明显，出现了重复的标示符。
* 加前面就难道没问题吗？
* 有的：数组中不能出现类似01 、001，以 0 开头的数字，
* 但适用性比原先更广。
*/ 
cv = 0 + v;
if (!o[cv]) {
a.push(v);
o[cv] = true;
} 
} 
return a;
} 

若希望在此解题思路上更完善，推荐 Dexter.Yy 的方法，即进行类型判断并生成唯一标示符，详见 评论 20 楼。

基于 indexOf 的兼容方案

没有绝对最好的方法，只有最合适的方案。实际上，使用 Array.indexOf() 的思路也是不错的选择。对于已支持该方法的浏览器，可直接使用原生 API；对于未支持的浏览器，可手动扩展 Array.indexOf() 方法，实现如下：

 
if(!Array.prototype.indexOf) {
Array.prototype.indexOf = function (obj, fromIndex) {
if (fromIndex == null) {
fromIndex = 0;
} else if (fromIndex < 0) {
fromIndex = Math.max(0, this.length + fromIndex);
} 
for (var i = fromIndex; i < this.length; i++) {
if (this[i] === obj)
return i;
} 
return -1;
}; 
} 

接下来，实现过程便变得非常简单。

针对使用 Array.indexOf() 方法的优化提示：在找到相同值时，从数组中移除该元素，以减少后续遍历的数据量。