JavaScript数组高性能去重解决方案

在大多数的人眼里，数组去重是一个很简单的课题，很多人甚至熟练掌握了多种数组去重的方法，然而大多时候，我们却忽略了数组去重所消耗的时间资源。譬如我们在做前端性能优化的时候，又有多少人会考虑JavaScript的运行性能。今天，我将通过一组测试数据来给大家展示高性能数组去重的必要性。当然以上仅针对像我这样的强迫症患者，。

先展示下结论，有些不喜欢看过程的同学可以直接拿去用，当然你也可以使用本人的高性能js工具集：npm i efficient-js

?// 最高性能数组去重方法 10万数量级：3毫秒，100万数量级：6毫秒，1000万数量级36毫秒Array.prototype.distinct = function () {var hash=[];var obj = {};for (i = 0; this[i] != null; i++) {if(!obj[this[i]]){hash.push(this[i]);obj[this[i]] = this[i];return hash;

一、收集数组去重的方法

1、遍历数组法：实现思路：新建一个数组，遍历去要重的数组，当值不在新数组的时候（indexOf为-1）就加入该新数组中；

2、数组下标判断法：实现思路：如果当前数组的第 i 项在当前数组中第一次出现的位置不是 i，那么表示第 i 项是重复的，忽略掉。否则存入结果数组。

3、排序后相邻去除法：实现思路：给传入的数组排序，排序后相同的值会相邻，然后遍历排序后数组时，新数组只加入不与前一值重复的值。

4、优化遍历数组法（推荐）：实现思路：双层循环，外循环表示从0到arr.length，内循环表示从i+1到arr.length，将没重复的右边值放入新数组。（检测到有重复值时终止当前循环同时进入外层循环的下一轮判断）

5、ES6实现：

a、实现思路：ES6提供了新的数据结构Set。它类似于数组，但是成员的值都是唯一的，没有重复的值。Set函数可以接受一个数组（或类似数组的对象）作为参数，用来初始化。

b、实现思路：Array.filter() + indexOf

6、双重 for 循环（最容易理解）：实现思路：外层循环遍历元素，内层循环检查是否重复，当有重复值的时候，可以使用 push()，也可以使用 splice()

7、for...of + includes() （双重for循环的升级版）：实现思路：外层用 for...of 语句替换 for 循环，把内层循环改为 includes()，先创建一个空数组，当 includes() 返回 false 的时候，就将该元素 push 到空数组中 ，类似的，还可以用 indexOf() 来替代 includes()

8、Array.sort()：实现思路：首先使用 sort() 将数组进行排序，然后比较相邻元素是否相等，从而排除重复项

9、for...of + Object： 实现思路：利用Object唯一key的特性来实现去重

以上的方法去重都没问题，都可以实现数组去重的目的，但是性能差距很大，可能处理10000条数据以内的表现不回太明显，但是无论哪个程序都是由很多很多的指令组成的，假如你不去关注每一条指令的优化，而想当然的想直接优化程序，那么你注定会失败。“毋以善小而不为”，虽然用在这里有些欠妥，但大体就是这个意思，一切都要从细节入手。我们先看看上面的去重方法，方法很多，我们需理一下，虽然上面的方法看起来思路不一样，但是可以分为两类：遍历数组和直接使用内置方法

然而遍历数组的方式有很多种，甚至不止上面的这些方法，我们首先对比遍历数组的方法的效率，然后在对比其他的

二、建立多维度的测试模板并验证

以下是测试结果的环境

首先我们列出所有的遍历数组的方法

?function getRandomIntInclusive(min, max) {min = Math.ceil(min);max = Math.floor(max);return Math.floor(Math.random() * (max - min + 1)) + min; //The maximum is inclusive and the minimum is inclusivevar orgArray = Array.from(new Array(100000), ()=>{return getRandomIntInclusive(1, 1000);// 普通for循环Array.prototype.distinct1 = function () {var hash=[];for (i = 0; i < this.length; i++) {if(hash.indexOf(this[i])==-1){hash.push(this[i]);return hash;// 优化版for循环Array.prototype.distinct2 = function () {var hash=[];for (i = 0, len = this.length; i < len; i++) {if(hash.indexOf(this[i])==-1){hash.push(this[i]);return hash;// 弱化版for循环Array.prototype.distinct3 = function () {var hash=[];for (i = 0; this[i] != null; i++) {if(hash.indexOf(this[i])==-1){hash.push(this[i]);return hash;// foreachArray.prototype.distinct4 = function () {var hash=[];this.forEach(item => {if(hash.indexOf(item)==-1){hash.push(item);return hash;// foreach变种Array.prototype.distinct5 = function () {var hash=[];Array.prototype.forEach.call(this, item => {if(hash.indexOf(item)==-1){hash.push(item);return hash;// forinArray.prototype.distinct6 = function () {var hash=[];for (key in this) {var item = this[key]if(hash.indexOf(item)==-1){hash.push(item);return hash;// mapArray.prototype.distinct7 = function () {var hash=[];this.map(item => {if(hash.indexOf(item)==-1){hash.push(item);return hash;// forofArray.prototype.distinct8 = function () {var hash=[];for (let item of this) {if(hash.indexOf(item)==-1){hash.push(item);return hash;var startTime,endTime, rtn;function test(types) {types.forEach(type => {startTime = new Date();rtn = orgArray[type]();endTime = new Date();console.log(`数量级[${orgArray.length/10000}万]去重后数组长度为${rtn.length},使用${type}消耗时长${endTime - startTime}毫秒`)console.log('----------------------------------------------------------------------');var testArray = [];for (i = 1; i <= 8;i++) {testArray.push('distinct' + i);test(testArray)

输出结果：

把数据量级提高到100万、1000万，测试结果如下：

基于以上测试结果我们可以排除forin，但是其他的遍历数组的方法相差不到，我们取目前表现最好的弱化版for循环（其实针对我们的测试环境是强化版，哈哈）

?function getRandomIntInclusive(min, max) {min = Math.ceil(min);max = Math.floor(max);return Math.floor(Math.random() * (max - min + 1)) + min; //The maximum is inclusive and the minimum is inclusivevar orgArray = Array.from(new Array(100000), ()=>{return getRandomIntInclusive(1, 1000);// indexOfArray.prototype.distinct1 = function () {var hash=[];for (i = 0; this[i] != null; i++) {if(hash.indexOf(this[i])==-1){hash.push(this[i]);return hash;// 数组下标判断法Array.prototype.distinct2 = function () {var hash=[];for (i = 0; this[i] != null; i++) {if(this.indexOf(this[i])==i){hash.push(this[i]);return hash;// includesArray.prototype.distinct3 = function () {var hash=[];for (i = 0; this[i] != null; i++) {if(!hash.includes(this[i])){hash.push(this[i]);return hash;// ObjectArray.prototype.distinct4 = function () {var hash=[];var obj = {};for (i = 0; this[i] != null; i++) {if(!obj[i]){hash.push(this[i]);obj[i] = this[i];return hash;var startTime,endTime, rtn;function test(types) {types.forEach(type => {startTime = new Date();rtn = orgArray[type]();endTime = new Date();console.log(`数量级[${orgArray.length/10000}万]去重后数组长度为${rtn.length},使用${type}消耗时长${endTime - startTime}毫秒`)console.log('----------------------------------------------------------------------');var testArray = [];for (i = 1; i <= 4;i++) {testArray.push('distinct' + i);test(testArray)

测试结果如下

这个结果就拉开差距了，在看下100万的结果

结论很明确，数据量级呈线性增长，正常的遍历数组的方式中中用objec的方法效率大大领先其他方法，我们再次来回顾下object方法的实现思路，

利用Object唯一key的特性来实现去重