2009-12
7
到目前为止，javascript中array还没有内置的unique方法，本来这篇文章很早就写了，但由于之前的虚拟主机忘记续费导致数据丢了，前几天JerryQu问了我这个问题，觉得可能还有其他人要，这里在写出来，备大家参考。
实现方式
这里给出2中实现方式。一种是大家应该都知道的indexOf检测的方式，另一种是结合lastIndexOf和splice实现方式。
下载: array_unique.js
//首先给Array对象原型上添加indexOf和lastIndexOf方法.(如果没有的话)
if(!Array.prototype.indexOf){
Array.prototype.indexOf = function(element, index){
var length = this.length;
if(index == null){
index = 0;
}else{
index = +index || 0;
if(index < 0) index+= length;
if(index < 0) index = 0;
}
for(var current;index<length;index++){
current = this[index];
if(current === element) return index;
}
return -1;
}
}
if(!Array.prototype.lastIndexOf){
Array.prototype.lastIndexOf = function(element, index){
var length = this.length;
if(index == null){
index = length - 1;
}else{
index = +index || 0;
if(index < 0) index+= length;
if(index < 0) index = -1;
else if(index >= length) index = length - 1;
}
for(var current;index>=0;index--){
current = this[index];
if(current === element) return index;
}
return -1;
}
}
//很常见的实现方式
var arrayUnique1 = function(arr){
for(var i=0,len=arr.length,result=[],item;i<len;i++){
item = arr[i];
if(result.indexOf(item) < 0) {
result[result.length] = item;
}
}
return result;
}
//通过lastIndexOf和splice方法实现方式
var arrayUnique2 = function(arr){
var length = arr.length;
while(--length){
//如果在前面已经出现，则将该位置的元素删除
if(arr.lastIndexOf(arr[length],length-1) > -1) {
arr.splice(length,1);
}
}
return arr;
}
if(!Array.prototype.indexOf){
Array.prototype.indexOf = function(element, index){
var length = this.length;
if(index == null){
index = 0;
}else{
index = +index || 0;
if(index < 0) index+= length;
if(index < 0) index = 0;
}
for(var current;index<length;index++){
current = this[index];
if(current === element) return index;
}
return -1;
}
}
if(!Array.prototype.lastIndexOf){
Array.prototype.lastIndexOf = function(element, index){
var length = this.length;
if(index == null){
index = length - 1;
}else{
index = +index || 0;
if(index < 0) index+= length;
if(index < 0) index = -1;
else if(index >= length) index = length - 1;
}
for(var current;index>=0;index--){
current = this[index];
if(current === element) return index;
}
return -1;
}
}
//很常见的实现方式
var arrayUnique1 = function(arr){
for(var i=0,len=arr.length,result=[],item;i<len;i++){
item = arr[i];
if(result.indexOf(item) < 0) {
result[result.length] = item;
}
}
return result;
}
//通过lastIndexOf和splice方法实现方式
var arrayUnique2 = function(arr){
var length = arr.length;
while(--length){
//如果在前面已经出现，则将该位置的元素删除
if(arr.lastIndexOf(arr[length],length-1) > -1) {
arr.splice(length,1);
}
}
return arr;
}
测试结果
测试数据：var arr = [1,2,3,1,2,3,2,1,3,4,2,232];
IE7循环10,000次：
arrayUnique1为460ms，arrayUnique2为190ms。
FF3.5循环100,000次：
arrayUnique1为170ms，arrayUnique2为63ms。
从测试结果上可以看出，通过lastIndexOf和splice的方式的速度是普通方式的2-3倍。
其他实现方式
除了上面描述的2中实现方式外，其实还是有其他实现方式的。jQuery中就一种实现方式。我们可以看下具体的代码：
unique: function( array ) {
var ret = [], done = {};
try {
for ( var i = 0, length = array.length; i < length; i++ ) {
var id = jQuery.data( array[ i ] );
if ( !done[ id ] ) {
done[ id ] = true;
ret.push( array[ i ] );
}
}
} catch( e ) {
ret = array;
}
return ret;
}
var ret = [], done = {};
try {
for ( var i = 0, length = array.length; i < length; i++ ) {
var id = jQuery.data( array[ i ] );
if ( !done[ id ] ) {
done[ id ] = true;
ret.push( array[ i ] );
}
}
} catch( e ) {
ret = array;
}
return ret;
}
这种是通过创建一个临时的对象，然后获取元素的ID保存在对象的key中。但这种实现方式只能针对对象，对于普通的直接量（如：数字，字符串等）是无用的。并且经过测试，这种方式在执行速度上和lastIndexOf结合splice还是有点差距的。
多谢多谢～
我实际测试了一下，的确在循环10000次的时候你的方法很占优势，但是基于hash的方法在循环中主要消耗在创建hash对象上面，因此这个测试还很片面。
var arr = [];
for(var i = 0; i < 10000; i++) {
arr.push(i);
}
var d1 = new Date();
arr.distinct();
var d2 = new Date();
arrayUnique2(arr);
document.write((d2.getTime() – d1.getTime()) + “, ” + (new Date().getTime() – d2.getTime()));
更多的情况下是一个大数组进行单一化，这种情况下测试，你的方法太耗时了，因为时间复杂度是O（n2）。
我觉得可以考虑写成2个方法：一个适用于小数组多循环，一个适用于大数组少循环。
@army8735:
对于大数组唯一化来说，我写到的这种方式性能确实比较低下，但是不会有额外的遗漏情况。
你那种通过Hash方式虽然解决了一些弱类型的问题，但由于使用到了hash的key是数组每项的toString()值，value却是个类型数组 比较法。所以认为new String(’a')和new String(’a')是一样的，实际上它们是不同的对象。
嗯是的。后来我又考虑了新加的方法：如果不是基础类型的话（对象、数组、string等），存入hash的key是类型，而value数组中是引用即可。