数组去重：深度比较对象属性
在JavaScript中，数组去重是一个常见的任务。但当数组中包含对象时，这个任务变得更加复杂。因为对象的比较是基于引用，而不是值。本文将探讨如何实现一个数组去重函数，该函数可以深度比较对象的属性，从而正确地去除重复的对象。
1. 基本思路
我们的目标是创建一个uniqueArray函数，该函数可以去除数组中的重复项。对于原始类型（如数字、字符串和布尔值），这很简单。但对于对象、数组和其他复杂类型，我们需要进行深度比较。
2. 实现
function uniqueArray(arr) {
const result = [];
for (let i = 0; i < arr.length; i++) {
const item1 = arr[i];
let isFind = false;
for (let j = 0; j < result.length; j++) {
const item2 = result[j];
if (equals(item1, item2)) {
isFind = true;
break;
}
}
if (!isFind) {
result.push(item1);
}
}
return result;
}上述函数使用了一个equals辅助函数来比较两个值是否相等。这个函数可以处理原始类型、对象、数组和其他复杂类型。
function isPrimitive(value) {
return value === null || !['object', 'function'].includes(typeof value);
}
function equals(value1, value2) {
if (isPrimitive(value1) || isPrimitive(value2)) {
return Object.is(value1, value2);
}
const entries1 = Object.entries(value1);
const entries2 = Object.entries(value2);
if (entries1.length !== entries2.length) {
return false;
}
for (const [key, value] of entries1) {
if(!(key in value2) || !equals(value, value2[key])){
return false;
}
}
return true;
}3. 测试
我们可以使用以下测试用例来验证我们的函数是否正确：
console.log(equals({a: 1}, {a: 1})); // true
console.log(equals({a: 1}, {a: 2})); // false
console.log(equals([1, 2, 3], [1, 2, 3])); // true
console.log(equals([1, 2, 3], [1, 2, 4])); // false
console.log(equals({a: 1, b: undefined}, {a: 1, c: undefined})); // false
console.log(equals(function funcA(){let a = 1; this.b = 2;}, function funcB(){})); // true
console.log(equals(new Date(), new Date())); // true
console.log(equals(/a/, /a/)); // true
console.log(equals(Symbol(), Symbol())); // false4. 总结
在JavaScript中，数组去重是一个常见的任务，但当数组中包含对象时，这个任务变得更加复杂。我们需要进行深度比较来确保正确地去除重复的对象。本文提供了一个解决方案，该方案可以处理原始类型、对象、数组和其他复杂类型。希望这篇文章能帮助你更好地理解JavaScript中的对象比较和数组去重。
代码汇总
/**
* 数组去重
* 两个属性相同时的对象也认为是重复的
* @param {Array} arr
* @return {Array}
*/
function uniqueArray(arr) {
// 用Set的话是根据Object.is(a, b)去比较的，对于对象之间的比较，因为地址不同，所以被视为不同对象，进而无法做到去重
// return [...new Set(arr)]; // No!
const result = [];
for (let i = 0; i < arr.length; i++) {
const item1 = arr[i];
let isFind = false;
for (let j = 0; j < result.length; j++) {
const item2 = result[j];
if (equals(item1, item2)) {
isFind = true;
break;
}
}
if (!isFind) {
result.push(item1);
}
}
return result;
}
function isPrimitive(value) {
return value === null || !['object', 'function'].includes(typeof value);
}
function equals(value1, value2) {
if (isPrimitive(value1) || isPrimitive(value2)) {
return Object.is(value1, value2);
}
const entries1 = Object.entries(value1);
const entries2 = Object.entries(value2);
if (entries1.length !== entries2.length) {
return false;
}
for (const [key, value] of entries1) {
if(!(key in value2) || !equals(value, value2[key])){
return false;
}
}
return true;
}
console.log(equals({a: 1}, {a: 1})); // true
console.log(equals({a: 1}, {a: 2})); // false
console.log(equals([1, 2, 3], [1, 2, 3])); // true
console.log(equals([1, 2, 3], [1, 2, 4])); // false
console.log(equals({a: 1, b: undefined}, {a: 1, c: undefined})); // false
console.log(equals(function funcA(){let a = 1; this.b = 2;}, function funcB(){})); // true
console.log(equals(new Date(), new Date())); // true
console.log(equals(/a/, /a/)); // true
console.log(equals(Symbol(), Symbol())); // false使用Map进行优化
存在的问题
uniqueArray函数的时间复杂度是O(n^2)，因为它对于每个arr中的元素都遍历了result数组。如果数组很大，这可能会导致性能问题。
分析与解决
为了提高效率，我们可以使用一个Map来存储已经遍历过的对象的字符串表示形式。这样，我们就可以在O(1)的时间内检查一个对象是否已经存在。
意思是利用Map的特性来跟踪和检查对象是否已经被处理过，从而避免重复的检查。这种方法的关键是将对象转换为一个唯一的字符串表示形式，然后使用这个字符串作为Map的键。
以下是这个方法的基本思路：
-
创建一个Map：这个
Map将用于存储已经处理过的对象。键是对象的字符串表示形式，值是对象本身。 -
为每个对象生成一个唯一的字符串表示形式：这可以通过
JSON.stringify实现。但请注意，这种方法只适用于不包含函数、undefined或循环引用的对象。 -
检查对象是否已经存在于Map中：使用对象的字符串表示形式作为键，查找
Map。如果找到了，说明对象是重复的；否则，将对象添加到结果数组和Map中。
这种方法的优点是检查一个对象是否已经存在的操作的时间复杂度是O(1)，因为Map的查找操作非常快。但这种方法也有一些限制，例如它不能处理包含函数或循环引用的对象。
以下是一个简化的示例：
function uniqueArray(arr) {
const seen = new Map();
const result = [];
for (const item of arr) {
const key = JSON.stringify(item);
if (!seen.has(key)) {
seen.set(key, true);
result.push(item);
}
}
return result;
}该方法的短处
这个函数将会比原始的版本更快，特别是对于大数组。但是，这种方法只适用于可以被安全地转换为JSON的对象。
Comments NOTHING