Serenader

Learning by sharing

JavaScript 去重

Mr. serenader Published at , updated at
on
故事的起因来自牛客网的一个测试，里面有一道数组去重的题，题目如下：
之前刚好碰到过数组的去重这个问题，于是按照之前的印象，想都没想就写下：
Array.prototype.uniq = function () {
	var map = {};
	return this.filter(function (item) {
		if (map[item]) {
			return false;
		} else {
			map[item] = true;
			return true;
		}
	});
};
写完之后鸡冻地点了提交运行，脸上挂满了微笑。过了几秒，页面提示提交的代码未通过测试用例。。唔。。。这不科学，我的代码居然不通过！这怎么可能！！！肯定是手抖打错字母了！！于是检查了几遍，在Chrome控制台测了几遍，然后再提交。结果还是一样。难道是写法不对？赶紧换个姿势写，再提交，结果特么的还是不通过。。好吧，我开始怀疑这网站是不是有bug了。。。不过想想，怎么别人就能通过我就老是过不去呢……肯定是自己代码有问题，再检查一下代码！
后来才发现，上面这段代码无法去重这样的数组：['1', 1] 。好吧，被自己的愚蠢给吓到了。突然间觉得自己 too young too simple, sometimes naive 啊。。
于是乎，赶紧Google一番，涨涨姿势压压惊。果然，皇天不负有心人呐，这不，StackOverflow里面就有一个 满分的答案，看完之后觉得很有必要做个笔记，于是就有了这篇文章。嗯，废话到此结束。

利用 filter 函数和 indexOf 函数

当一个数组里面有重复的元素时，那么为重复的元素调用 indexOf 方法得到的位置不总是正确的，因此可以根据该方法来去重。
Array.prototype.uniq = function () {
	var _this = this;
	return _this.filter(function (item, pos) {
		// 当元素实际位置与indexOf方法返回的位置一致时，则该元素不是重复的元素。// 反之，即为重复的元素，去除之。return _this.indexOf(item) == pos;
	});
};
优点：简洁明了。
缺点：效率低，而且无法去重 NaN 和 {} 。

利用 hash 表

利用对象的属性名不能重复这一特性，即可进行筛选。这种方法也就是开篇所提到的代码方法。相对而言，下面这段代码更加简练优美。
Array.prototype.uniq = function () {
	var map = {};
	return this.filter(function (item) {
		return map.hasOwnProperty(item) ? false : (map[item] = true);
	});
};
优点： 速度较第一种快。
缺点： 无法区分 '1' 和 1 ，以及对象 {foo: 1} 和 {foo: 2}。

进一步优化 hash 表，对每个元素进行类型判断

在上一个方法中，导致该方法的缺点的根本原因是因为，在执行 map[item] = true 时，会对 item进行一次 toString 转换，因此才会导致无法去重 ['1', 1]，因为此时均转换为 '1' 了。对于对象的话，则是转换成 '[object Object]' 了。那么，如果我们在一开始时即把他们的类型检测出来，再利用 hash 表方法，那么即可以达到去重的目的。
Array.prototype.uniq = function () {
	var prims = {boolean: {}, number: {}, string: {}};
	var obj = [];
	return this.filter(function (item) {
		var type = typeof item;
		if (type in prims) {
			return prims[type].hasOwnProperty(item) ? false : (prims[type][item] = true);
		} else {
			return obj.indexOf(item) != -1 ? false : (obj.push(item));
		}
	});
};
等等，为啥 prims 里面每个属性都是一个对象？不能用数组吗？像是这样：
Array.prototype.uniq = function () {
	var prims = {boolean: [], number: [], string: []};
	var obj = [];
	return this.filter(function (item) {var type = typeof item;
    	if (type in prims) {
		    return prims[type].indexOf(item) != -1 ? false : (prims[type].push(item));
	    } else {
	    return obj.indexOf(item) != -1 ? false : (obj.push(item));
	    }
    });
};
我们先来看下面一段代码：
var arr = [undefined, null, NaN, {}];
arr.indexOf(undefined); // 0
arr.indexOf(null); // 1
arr.indexOf(NaN); // -1
arr.indexOf({}); // -1
可见，indexOf 方法对于 NaN 和空对象而言总是返回 -1，也因此，如果 prims 的属性是数组的话，那么 prims.number 数组里面则可能会出现多个 NaN，从而无法去重 NaN 。根本原因在于
undefined === undefined // true
null === null //true
NaN === NaN // false
typeof NaN === 'number'
({}) === ({}) // false
值得一提的是，这种方法去重能够通过牛客网的那道去重的题目。
优点： 比较理想的去重。
缺点： 无法去除两个相同的对象，比如 {} 和 {}。这是因为 ({}) === ({}) // false 这个原因。具体可以看我之前写的博文 == VS === ? The Evil or the Angel ?

继续修改 hash 表，使得完美去除相同的对象

Array.prototype.uniq = function () {
	var map = {};
	return this.filter(function (item) {
		var key = typeof item + item;
		return map.hasOwnProperty(key) ? false : (map[key] = true);
	});
};
优点： 速度快，效果好。
缺点： 好像木有？
另一个思路，使用 JSON.stringify 将每个元素转化为字符串，再用 hash 表去重：
Array.prototype.uniq = function () {
	var map = {};
	return this.filter(function (item) {
		var key = JSON.stringify(item);
		return map.hasOwnProperty(key) ? false : (map[key] = true);
	});
};
不过上面的方法无法去重 ['1', 1] 这样的数组，要达到去重这种数组的话，可以结合上面那一种方法，先判断元素类型，再进行检查是否重复。

对于数组只包含基本类型值时，可以先排序，再去重

Array.prototype.uniq = function () {
	var _this = this;
	return _this.sort().filter(function (item, pos) {
		return !pos || item != _this[pos - 1];
	});
};
其原理是排序后的数组中，依次比较前后两个元素的值即可知道是否有重复。优点： 更快。
缺点： 只能对基本类型值进行排序，而对对象无效，因为对于 sort 函数而言对象都是一致的。

Reference