js 给引用类型数组去重

男娘i 2022-02-21 07:00 183阅读 0赞

参考一

# js 包含引用类型数组 - 对象标记法去重 #

**前言**

Js数组去重已经有很多中实现方式：包括逐个检索对比(使用Array.property.indexOf)，先排序后对比，使用hash表，利用ES6中的Set()等。这些数组去重办法中速度最快的是hash表，最安全也最慢的是逐个检索对比(先排序后对比是优化成先分组再逐个检索)，而ES6的Set对象目前浏览器兼容不全。

有没有结合那些以上方式的优点，像hash表一样快，和Array.property.indexOf一样全，又没有兼容问题的解决方案呢？

**Js中的基本类型**

Undefined, Number, String,Boolean, Null, Object，除了前5种是值传递类型，其他所有的都是引用类型。

**待解决问题**

假设有o1 = o2 = new Object()

hash表去重方式的缺陷在于不能判断\[o1,o2,\{\}\]中的o1与o2是同一个对象的引用，因为得到的结果都是 ”object”。

那么如果有办法判断引用变量后面是同一个对象，就可以达到Array.property.indexOf方式所做的效果了。但是js本身又不提供对象内存地址索引，所以，那就造一个吧。

**标记法**

比如有个人类，在学校老师叫他做“小明”，在家爸妈叫他做“乖乖”，邻居叫他做“别人家的孩子”，虽然叫法不同，但是实际都是指向同一个人类个体。有一次商家搞活动给小孩子发免费糖果，一个小屁孩只能领一次，为了避免熊孩子以“小明”的名义领一次，又以“乖乖”的名义领一次，商家想了一个办法，每一个来领糖果的小孩子，先检查手掌有没有商家画的logo，如果没有，就可以领糖果，发完糖果后就在小孩子手掌上画商家logo，下次再来时只要看手掌上是不是已经有logo了，有就说明已经领过了，就不发糖果。同时为了不让logo与小孩子身上其他涂涂画画的东西相同，商家特意找了一种叫“全宇宙重复概率可能性低到接近不存在”的符号当logo，成功解决了涂鸦与logo相似的问题。小孩子领了糖果也吃完了，怕回家被爸妈发现，就去洗了手上的logo，就像一切都没有发生过一样。

所以呢，只要用一个uuid(商家logo)作为属性值添加到对象里面(画到手掌上)，就可以判断这个对象在前面已经被收录(领过糖果)了，也就达到检测多个引用变量是否指向同一个对象的效果了。引用类型在去重之后，还要将uuid属性清除掉，避免后续该对象的使用出现问题。

使用uuid做标记key名，目的是避免与对象上本来就存在的属性名冲突，比如原对象有个minName属性名，标记名就不能叫minName，所以选uuid做标记属性名是为了与该对象当前所有可能存在的属性名区分，而每一个对象都是独立的，那么只需要一个uuid字符串就可以了。

![1][]

**具体代码实现与数据测试**

1 !(function() {
      2     "user strict";
      3 
      4     /**
      5      * 创建一个 带有默认格式的uuid字符串
      6      * @param {Number} length        4个字符串为一组的组数数量 default:8
      7      * @param {String} connectString 组数之间连接符 default:"_"
      8      * @return uuidString:7953_1e59_9cc4_8f44_ab7d_c959_3b5c_ef94
      9      * @author Z
     10      */
     11 
     12     function UUID(length, connectString) {
     13         var uuid = [],
     14             max0x = 0x10000, //65535+1
     15             i;
     16 
     17         // 设置参数num,connectString默认值
     18         length = Math.abs(0 | length) || 8;
     19         typeof connectString !== "string" && (connectString = "_");
     20 
     21         for (i = 0; i < length; i++) {
     22             uuid.push((Math.random() * max0x | 0).toString(16));
     23         }
     24 
     25         return uuid.join(connectString);
     26     }
     27     // demo
     28     // UUID() ===> eae1_bb78_1f00_4ef2_c5d0_d28b_6708_e73f
     29     // UUID(null,"-") ===> ff15-8779-ce3d-3c83-cab3-b645-9150-cdd2
     30     // UUID(4) ===> d9d9_7a23_4ce7_c5c0
     31     // UUID(4,"&") ===> 8703&6daf&8daa&f36d
     32     /** ----test UUID()--- */
     33     // console.log(UUID());
     34     // console.log(UUID(null, "-"));
     35     // console.log(UUID(4));
     36     // console.log(UUID(4, "&"));
     37 
     38 
     39 
     40     /**
     41      * 用于拓展操作Array对象的工具集合
     42      * @type {Object}
     43      */
     44     var _arrayExpand = {};
     45 
     46     /**
     47      * 将传入的数组去掉重复的项，并返回一个新数组。
     48      * @param  {Array}  array 目标去重数组，原始数组
     49      * @param  {Boolean} isQuick 可选参数, 等于true时使用判断步骤更少的hash去重
     50      * @return {Array}          去重后的新数组
     51      * @author Z
     52      */
     53     _arrayExpand.unique = function(array, isQuick) {
     54         var temp = [],
     55             valueHash = {
     56                 "number": {},
     57                 "string": {},
     58                 "boolean": {},
     59                 "undefined": {},
     60                 "null": true // 只需要判断一次即可
     61             },
     62             objectHash = {},
     63             objectRecord = [],
     64             quickHash = {},
     65             keyUUID, item, type, i, len, _set
     66 
     67         // 优先使用 ES6 中的 Set对象
     68         if (window.Set) {
     69             _set = new Set(array);
     70             for (i of _set) {
     71                 if (_set.has(i)) {
     72                     temp.push(i);
     73                 }
     74             }
     75             return temp;
     76         }
     77 
     78         // 已知所有项都是值传递类型的数组，可以指定使用快速去重,isQuick指定为true值时生效
     79         if (isQuick === true) {
     80             for (i = 0, len = array.length; i < len; i++) {
     81                 item = array[i];
     82                 if (!quickHash[item]) {
     83                     temp.push(item);
     84                     quickHash[item] = true;
     85                 }
     86             }
     87         }
     88         // 包含引用类型的混合数组去重
     89         else {
     90             // 标记属性使用uuid,避免与其他属性冲突, 使用上面的UUID创建，或者直接手写。
     91             keyUUID = UUID();
     92 
     93             for (i = 0, len = array.length; i < len; i++) {
     94                 item = array[i];
     95                 type = valueHash[typeof item];
     96                 // number, string, boolean, undefined
     97                 if (type) {
     98                     if (!type[item]) {
     99                         temp.push(item);
    100                         type[item] = true;
    101                     }
    102                 }
    103                 // object, null
    104                 else {
    105                     // object
    106                     if (item) {
    107                         if (!item.hasOwnProperty(keyUUID)) {
    108                             temp.push(item);
    109                             item[keyUUID] = true;
    110                             // 标记污染了原先的object，后续需要清除标记
    111                             objectRecord.push(item);
    112                         }
    113                     }
    114                     // null
    115                     else if (valueHash.null) {
    116                         temp.push(item);
    117                         valueHash.null = false;
    118                     }
    119                 }
    120             }
    121 
    122             // 清除标记
    123             if (objectRecord.length) {
    124                 for (i = 0, len = objectRecord.length; i < len; i++) {
    125                     delete objectRecord[i][keyUUID];
    126                 }
    127             }
    128 
    129         }
    130 
    131         return temp;
    132     };
    133     // demo
    134     // _arrayExpand.unique([1,"1",{o1},{o1},{m1},{m2}, new Number(1), null,undefined,NaN,Infinity,null,undefined,NaN,Infinity]) ===> [1,"1",{o1},{m1},{m2}, new Number(1), null,undefined,NaN,Infinity]
    135     // _arrayExpand.unique([1,2,3,4,1,2,3,4], true) ===> [1,2,3,4]
    136     /** -----test _arrayExpand.unique()--- */
    137     // var o1 = {},
    138     //     o2 = o1,
    139     //     o3 = o1;
    140     // console.log(_arrayExpand.unique([new Number(1), 1, 1, {}, "1", {}, true, null, "true", null, undefined, 0, NaN, NaN, o2, Infinity, o1, o3]));
    141 
    142 
    143     // 添加到window,对外调用
    144     var _ArrayExpandName = "ArrayExpand";
    145     if (window.hasOwnProperty(_ArrayExpandName)) {
    146         alert(_ArrayExpandName + " was existed in the window");
    147     } else {
    148         window[_ArrayExpandName] = _arrayExpand;
    149     }
    150     // openApi demo
    151     // ArrayExpand[key](arguments)
    152     // window.ArrayExpand[key](arguments)
    153 
    154 }(undefined));

**总是又有但是，更加全面的去重是先检测当对象已经被阻止扩展或者冻结,如Object.preventExtensions，Object.seal，Object.freeze之类，就不能使用标记法了，只能上用ES6的Set对象，或者降级使用Array.property.indexOf。**

**参考二：**

# [JavaScript数组去重][JavaScript] #

数组去重，一般都是在面试的时候才会碰到，一般是要求手写数组去重方法的代码。如果是被提问到，数组去重的方法有哪些？你能答出其中的10种，面试官很有可能对你刮目相看。  
在真实的项目中碰到的数组去重，一般都是后台去处理，很少让前端处理数组去重。虽然日常项目用到的概率比较低，但还是需要了解一下，以防面试的时候可能回被问到。

## 数组去重的方法 ##

## 一、利用ES6 Set去重（ES6中最常用） ##

function unique (arr) {
      return Array.from(new Set(arr))
    }
    var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
    console.log(unique(arr))
     //[1, "true", true, 15, false, undefined, null, NaN, "NaN", 0, "a", {}, {}]

不考虑兼容性，这种去重的方法代码最少。这种方法还无法去掉“\{\}”空对象，后面的高阶方法会添加去掉重复“\{\}”的方法。

## 二、利用for嵌套for，然后splice去重（ES5中最常用） ##

双层循环，外层循环元素，内层循环时比较值。值相同时，则删去这个值。

## 三、利用indexOf去重 ##

新建一个空的结果数组，for 循环原数组，判断结果数组是否存在当前元素，如果有相同的值则跳过，不相同则push进数组。

## 四、利用sort() ##

利用sort()排序方法，然后根据排序后的结果进行遍历及相邻元素比对。

## 五、利用对象的属性不能相同的特点进行去重（这种数组去重的方法有问题，不建议用，有待改进） ##

## 六、利用includes ##

## 七、利用hasOwnProperty ##

function unique(arr) {
        var obj = {};
        return arr.filter(function(item, index, arr){
            return obj.hasOwnProperty(typeof item + item) ? false : (obj[typeof item + item] = true)
        })
    }
        var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
            console.log(unique(arr))
    //[1, "true", true, 15, false, undefined, null, NaN, "NaN", 0, "a", {…}]   //所有的都去重了

利用hasOwnProperty 判断是否存在对象属性

## 八、利用filter ##

## 九、利用递归去重 ##

## 十、利用Map数据结构去重 ##

创建一个空Map数据结构，遍历需要去重的数组，把数组的每一个元素作为key存到Map中。由于Map中不会出现相同的key值，所以最终得到的就是去重后的结果。

## 十一、利用reduce+includes ##

参考三：

function unique6 (arr) {
      let newArr = []
      let obj = {}
      arr.forEach(item => {
        if (typeof item !== 'object') {
          if (newArr.indexOf(item) === -1) {
            newArr.push(item)
          }
        } else {
          let str = JSON.stringify(item)
          if (!obj[str]) {
            newArr.push(item)
            obj[str] = 1
          }
        }
      })
      return newArr
    }
    let arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{},{a:1},{b:1},{a:1}]
    console.log(unique6(arr))
    // [1, "true", true, 15, false, undefined, null, NaN, NaN, "NaN", 0, "a",{}, {a:1}, {b:1}]

参考四：

ES6中新增了Set数据结构，类似于数组，但是 它的成员都是唯一的 ，其构造函数可以接受一个数组作为参数，如：

let array = \[1, 1, 1, 1, 2, 3, 4, 4, 5, 3\];  
 let set = new Set(array);  
 console.log(set);  
 // => Set \{1, 2, 3, 4, 5\}  
ES6中Array新增了一个静态方法Array.from，可以把类似数组的对象转换为数组，如通过querySelectAll方法得到HTML DOM Node List，以及ES6中新增的Set和Map等可遍历对象，如：

let set = new Set();  
 set.add(1).add(2).add(3);  
 let array = Array.from(set);  
 console.log(array);  
 // => \[1, 2, 3\]  
于是，现在我们可以用一行代码实现数组去重了：

let array = Array.from(new Set(\[1, 1, 1, 2, 3, 2, 4\]));  
console.log(array);  
// => \[1, 2, 3, 4\]  
附：ES5实现数组去重

参考五：

### 普通数组去重 ###

一、普通数组去重

方法一：遍历数组法

function func1(array){
        var temp = [];//临时数组
        //遍历当前数组
        for(var i=0;i<array.length;i++){
            //判断array[i]是否在临时数组中，不在则将array[i]的值复制到temp里
            //indexOf()方法可返回某个指定的字符串或数组值在字符串或数组中首次出现的位置，若不在其中则返回-1
            if (temp.indexOf(array[i]) === -1)
                temp.push(array[i]); 
        }
        return temp;
    }

方法二：排序法

function func2(array){
        var temp = [];//临时数组
        array.sort();//先给当前数组排序
        temp.push(array[0]);
        //因为数组已经经过排序，所以重复元素一定相邻，判断当前数组第i个元素与temp的最后一个元素是否相等，不相等时才复制元素
        for(var i=1;i<array.length;i++){
            if(array[i] != temp[temp.length-1])
                temp.push(array[i]);
        }
        return temp;
    }

方法三：对象法

### 对象数组去重 ###

方法一：将对象数组中name属性相同的项去重

方法二：使用reduce方法将对象数组中name属性相同的项去重

*  代码汇总与执行

<!doctype html>
    <title></title>
    
    <body>
    
    </body>
    <script type="text/javascript">
    (function(){
        array = [1,2,3,3,3];//测试数组
        objArray = [{age:1,name:'a'},{age:2,name:'a'},{age:3,name:'c'}];//测试对象数组
        console.log(func1(array));//遍历数组法
        console.log(func2(array));//排序法
        console.log(func3(array));//对象法
        console.log(func4(objArray));//将对象数组中name属性相同的项去重
        console.log(func5(objArray));//使用数组内置的reduce方法将对象数组中name属性相同的项去重
    })()
    
    //遍历数组法
    function func1(array){
        var temp = [];//临时数组
        //遍历当前数组
        for(var i=0;i<array.length;i++){
            //判断array[i]是否在临时数组中，不在则将array[i]的值复制到temp里
            //indexOf()方法可返回某个指定的字符串或数组值在字符串或数组中首次出现的位置，若不在其中则返回-1
            if (temp.indexOf(array[i]) === -1)
                temp.push(array[i]); 
        }
        return temp;
    }
    
    //排序法
    function func2(array){
        var temp = [];//临时数组
        array.sort();//先给当前数组排序
        temp.push(array[0]);
        //因为数组已经经过排序，所以重复元素一定相邻，判断当前数组第i个元素与temp的最后一个元素是否相等，不相等时才复制元素
        for(var i=1;i<array.length;i++){
            if(array[i] != temp[temp.length-1])
                temp.push(array[i]);
        }
        return temp;
    }
    
    //对象法
    function func3(array){
        var temp = [];//临时数组
        var json = {};//创建一个空对象
        //将当前数组的元素值当作对象的属性，遍历数组，比对对象，如果对象的这个属性不存在则将当前数组元素复制到临时数组，并添加该属性且将属性值赋值为1
        for(var i = 0; i<array.length; i++){
            if(!json[array[i]]){//如果对象没有该属性
                temp.push(array[i]);
                json[array[i]] = 1;//添加属性，将属性值赋值为1
            }
        }
        return temp;
    }
    
    //将对象数组中name属性相同的项去重
    function func4(objArray) {
        var result = [];//去重后返回的结果数组
        var temp = {};//临时对象
        //将对象数组中每一项的name值作为属性，若temp不拥有此属性时则为temp添加此属性且将其值赋为true，并将这一项push到结果数组中
        for(var i=0;i<objArray.length;i++){  
            var myname = objArray[i].name;
            if(temp[myname]){//如果temp中已经存在此属性名，则说明遇到重复项
                continue;//不继续执行接下来的代码，跳转至循环开头
            }  
            temp[myname] = true;//为temp添加此属性（myname）且将其值赋为true
            result.push(objArray[i]);//将这一项复制到结果数组result中去
        }  
        return result;  
    }
    
    //使用reduce方法将对象数组中name属性相同的项去重
    function func5(objArray){
        var hash = {}; 
        //reduce方法有两个参数，第一个参数是一个callback，用于针对数组项的操作；第二个参数则是传入的初始值，这个初始值用于单个数组项的操作。
        objArray = objArray.reduce(function(item, next) {//这是针对数组项操作的函数，对于每个数组项，reduce方法都会将其调用一次
            //可使用最多四个参数来声明回调函数（第一个参数：通过上一次调用回调函数获得的值;第二个参数：当前数组元素的值；第三个参数：当前数组元素的数字索引；第四个参数：包含该元素的数组对象）
            //这里只使用了两个参数，所以item和next分别代表上一次调用回调函数后的值和objArray项值
            hash[next.name]?'':hash[next.name]=true&&item.push(next);//与func3逻辑相似 
            return item;
        }, []);//初始值是一个空对象，使用reduce方法返回的是空对象通过叠加执行之后的结果
        return objArray;
    }
    </script>
    </html>

[1]: https://user-gold-cdn.xitu.io/2017/4/1/c8fafca175378baf3164cb673dd2bf95?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[JavaScript]: https://segmentfault.com/a/1190000016418021