javascript 数组去重的6种思路

AlphaWallet 发布于2019-08-26 11:39 / 2273人阅读

摘要：但是这并不妨碍我们从思维拓展的角度出发，看看去重可以用几种思路去实现。首先是常规的双层循环比对的思路实现定义一个变量表示当前元素在中是否存在。依次对中的元素和原数组元素进行比对。重点是保证碰撞的几率小到比中大奖还小就可以了。

前端在日常开发中或多或少都会碰到有对数据去重的需求，实际上，像是lodash这些工具库已经有成熟完备的实现，并且可以成熟地运用于生产环境。但是这并不妨碍我们从思维拓展的角度出发，看看去重可以用几种思路去实现。

首先是常规的双层循环比对的思路实现

function doubleLoopUniq(arr) {
  let result = [];
  for (let i = 0, len = arr.length, isExist; i < len; i++) {
    // 定义一个变量表示当前元素在 result 中是否存在。
    isExist = false;
    for (let j = 0, rLen = result.length; j < rLen; j++) {
      if (result[j] === arr[i]) {
        // 依次对result 中的元素 和 原数组元素进行比对。
        isExist = true;
        break;
      }
    }
    // 最后判断如果不存在，则将此元素插入result
    !isExist && result.push(arr[i]);
  }
  return result;
}

借助 js内置的indexOf 进行去重

function indexOfUniq(arr) {
  let result = [];
  for (let i = 0, len = arr.length; i < len; i++) {
    // 用indexOf 简化了二层循环的流程
    if (result.indexOf(arr[i]) === -1) result.push(arr[i]);
  }
  return result;
}

排序后前后比对去重

function sortUniq(arr) {
  let result = [], last;
  // 这里解构是为了不对原数组产生副作用
  [ ...arr ].sort().forEach(item => {
    if (item != last) {
      result.push(item);
      last = item;
    }
  });
  return result;
}

通过hashTable去重

function hashUniq(arr) {
  let hashTable = arr.reduce((result, curr, index, array) => {
    result[curr] = true;
    return result;
  }, {})
  return Object.keys(hashTable).map(item => parseInt(item, 10));
}

ES6 SET一行代码实现去重

function toSetUniq(arr) {
  return Array.from(new Set(arr));
}

splice 去重（直接操作数组本身，带副作用）

function inPlaceUniq(arr) {
  let idx = 0;
  while (idx < arr.length) {
    let compare = idx + 1;
    while (compare < arr.length) {
      if (arr[idx] == arr[compare]) {
        arr.splice(compare, 1);
        continue;
      }
      ++compare
    }
    ++idx;
  }
  return arr;
}

最后在nodejs下面简单跑个测试，看看哪个效率高~

let data = [];
for (var i = 0; i < 100000; i++) {
  data.push(Math.random())
}

// 实现一个性能测试的装饰器
function performanceTest(fn, descript) {
  var a = new Date().getTime();
  return function () {
    fn.apply(this, [].slice.call(arguments, 0));
    console.log(descript, new Date().getTime() - a)
  }
}

performanceTest(hashUniq, "hashTable")(data)
performanceTest(sortUniq, "sortUniq")(data)
performanceTest(toSetUniq, "toSetUniq")(data)
performanceTest(indexOfUniq, "indexOfUniq")(data)
performanceTest(doubleLoopUniq, "doubleLoopUniq")(data)
performanceTest(inPlaceUniq, "inPlaceUniq")(data)

结果如下

hashTable 168ms
sortUniq 332ms
toSetUniq 80ms
indexOfUniq 4280ms
doubleLoopUniq 13303ms
inPlaceUniq 9977ms

延伸思考：如果数组内的元素是对象该怎么去重呢？

既然是引用类型，那么不免会使用到deepEqual，固然这种思路可以解答这道问题，但难免不够高效。

从上面的测试中也可见通过new Set 和 hashTable 去重是最高效的。
所以毫无疑问，我们要基于这两种方式去改造，我想用的是hashTable，
另一方面，为了降低深度比较带来的耗时，我尝试用JSON.stringify 将引用类型转化为基本类型。

function collectionUniq(collection) {
  let hashTable = {};
  collection.forEach(item => {
    hashTable[JSON.stringify(item)] = true;
  })
  return Object.keys(hashTable).map(item => JSON.parse(item))
}

那么问题来了，我们都知道对象的属性是无序的，假如数据是这种情况，那就GG了。

let collection = [ { a: 1, b: 2, c: 3 }, { b: 2, c: 3, a: 1 } ]

有一种toHash的思路，在对这个数组进行一次基本的去重之后，为了保证准确，
先遍历JSON 字符串 =>
通过 charCodeAt()拿到每个字符串的 unicode 编码 =>
相加得到一个总数，最后再两两进行比较，数值相等的就是重复的，这样就达到去重的效果了。

function toHash(obj) {
  let power = 1;
  let res = 0;
  const string = JSON.stringify(obj, null, 2);
  for (let i = 0, l = string.length; i < l; i++) {
    switch (string[i]) {
      case "{":
        power *= 2
        break
      case "}":
        power /= 2
        break
      case " ":
      case "
":
      case "
":
      case "	":
      break
      default:
        res += string[i].charCodeAt(0) * power
    }
  }
  return res
}

这只是一个实现基本的思路，有很大的改进空间，为了减少hash碰撞的可能，可以对一些特殊字符进行权重的增减。

重点是保证碰撞的几率小到比中大奖还小就可以了。

2018.2.8
上面是一个比较清奇的思路，常规的做法，实际上还是应该从优化深度比较的效率入手。
看到一个很好的实现思路，是一个优先判错的思路，通过预设各种前置条件来避免高代价的循环，这种思路尽管在数据量小的时候因为前置判断可能有一些微乎其微的性能损耗，但是数据量越大，优势就越明显了。感兴趣的可以了解下。
https://github.com/epoberezki...

GPU云服务器云服务器数组去重 javascript思路数组去重 linux 6种模式

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/107306.html

JavaScript数组去重的6种算法

摘要：否则存入结果数组。否则存入结果数组排序后相邻去除法虽然原生数组的方法排序结果不怎么靠谱，但在不注重顺序的去重里该缺点毫无影响。实现思路给传入数组排序，排序后相同值相邻，然后遍历时新数组只加入不与前一值重复的值。 1.遍历数组法实现思路：新建一新数组，遍历传入数组，值不在新数组就加入该新数组中；注意点：判断值是否在数组的方法indexOf是ECMAScript5 方法，IE8以下不支持...

Panda 2019-08-22 13:48 评论0 收藏0
JavaScript数组去重（12种方法，史上最全）

摘要：数组去重，一般都是在面试的时候才会碰到，一般是要求手写数组去重方法的代码。如果是被提问到，数组去重的方法有哪些你能答出其中的种，面试官很有可能对你刮目相看。数组去重的方法一利用去重中最常用不考虑兼容性，这种去重的方法代码最少。数组去重，一般都是在面试的时候才会碰到，一般是要求手写数组去重方法的代码。如果是被提问到，数组去重的方法有哪些？你能答出其中的10种，面试官很有可能对你刮目相看...

rozbo 2019-08-23 12:01 评论0 收藏0
JavaScript数组去重

摘要：数组去重的几种方法遍历数组法这是最简单的数组去重方法，实现思路新建一新数组，传入要去重的数组，遍历该数组，若值不在新数组中则加入该数组需要注意点判断值是否在数组的方法是方法，以下不支持，示例如下对象键值对法思路新建一对象以及数组，遍历传入数组去重的几种方法 1.遍历数组法这是最简单的数组去重方法，实现思路：新建一新数组，传入要去重的数组，遍历该数组，若值不在新数组中则加入该数组；...

邹强 2019-08-23 12:07 评论0 收藏0
[Javascript]数组去重的三种实现方式

摘要：方式使用获取并删除删除数组的第一个元素，判断这个元素是否还存在于数组中，如果存在则说明这个元素的是重复的如果不存在，进行操作方式建立一个哈希表，通过对象属性查询去除重复元素方式思路和方式类似，但是简洁很多来源个人博客方式1：使用shift()获取并删除删除数组的第一个元素，判断这个元素是否还存在于数组中，如果存在则说明这个元素的是重复的；如果不存在，进行push()操作 functi...

TZLLOG 2019-08-22 10:45 评论0 收藏0
JavaScript专题之数组去重

摘要：专题系列第三篇，讲解各种数组去重方法，并且跟着写一个前言数组去重方法老生常谈，既然是常谈，我也来谈谈。它类似于数组，但是成员的值都是唯一的，没有重复的值。 JavaScript 专题系列第三篇，讲解各种数组去重方法，并且跟着 underscore 写一个 unique API 前言数组去重方法老生常谈，既然是常谈，我也来谈谈。双层循环也许我们首先想到的是使用 indexOf 来循...

fsmStudy 2019-08-21 15:55 评论0 收藏0