前端知识体系

Appearance

大纲

数组去重 unique ​

手写数组去重方法（前端应用场景中一般不会遇到数组去重，都是使用后端去重后的数据，去重仅作为考察基础知识掌握能力）

  1. Set 实现（推荐）
  2. [for, for...of, forEach, filter] + [indexOf, includes, for] 组合实现
  3. [reduce] + [indexOf, includes] 实现
  4. sort + for 实现（利用底层 sort）
  5. 遍历 + hasOwnProperty 结合缓存实现（有限制）
  6. 遍历 + Map 缓存实现（推荐）
  7. 扩展：对象数组去重
    1. 基于某个对象属性去重
    2. 简单对象数组去重（对象为 json 数据）
    3. 基于宽松相等 (内容完全相等) 去重
      1. 主要考虑实现 looseEqual

1. Set 实现 ​

Set 对象 Set 确保值列表的唯一性，无论是原始值或者是对象引用。

  • 值的相等 (Set 使用 SameValueZero比较算法来区分不同的值。不是基于 === 也不是 Object.is)
    • 对于 Set, +0 严格相等于 -0
      • 对于 ===, ES2015 规范中更改为 +0 严格相等于-0
      • Object.is(+0, -0) 输出 false
    • Set 中， NaN 被认为是相同的，不同于 ===

SameValueZero 零值相等算法，同同值相等 Object.is() 方法类似，不过会认为 +0 与 -0 相等。

更多参看

2. for + indexOf 实现 ​

通过 for 实现双层循环遍历比对，foreach, filter 类似

indexOf() 使用严格相等 === 与 Array 的元素进行比较。这个不同于 SameValueZero 算法。

2. for...of + includes 实现 ​

includes() 方法使用 sameValueZero 算法来确定是否找到给定元素。

3. reduce + includes 实现 ​

通过 reduce 实现遍历，写法和 for 区别比较大

4. sort + forEach 实现（sort 并无意义，本质还是遍历） ​

该方法，是否使用 sort 并无区别，都要遍历所有。另注意 sort 会改变原数组，慎用 (可使用副本)

sort() 方法用原地算法对数组的元素进行排序，并返回数组。默认排序顺序是先将元素转换为字符串，然后比较它们的UTF-16代码单元值序列时构建的

就地算法是一种不使用辅助数据结构来转换输入的算法。

注意：sort() 默认排序时，需要调用 toString() 方法，在 null prototype 场景时就会报错

自 EcmaScript 2019 起，规范要求 Array.prototype.sort 为稳定排序。

5. 遍历 + hasOwnProperty 结合缓存实现（有限制） ​

此方案有限制，以下情况会异常

  • 不能处理 Object.create(null)，报错 VM49:4 Uncaught TypeError: Cannot convert object to primitive value
  • 不能处理 Symbol()，报错 TypeError: Cannot convert a Symbol value to a string

大多数 Javascript 对象的toString()方法都继承自Object.prototype。但是其中一些如 Object.create(null), Symbol() 具有 null prototype, not havetoString() 方法，因此 Javascript 将无法将这些对象转换为字符串原语。and can't convert object to primitive error will rise.

6. 遍历 + Map 实现 ​

利用 Map 缓存，实现 hashTable 去重

Map 键的相等 (Key equality) 是基于 sameValueZero 算法的 (NaN 是与 NaN 相等的，其他的值同 === 运算符)

异常处理

js
const map = new Map()

// 会报错 `Uncaught TypeError: Cannot convert object to primitive value`
map[Object.create(null)] = true

// 需改为
map.set(Object.create(null), true)

示例

js
// 调用 toString 会报错
Object.create(null) + ''
// 等同于
Object.create(null).toString()
点我查看详细
js
// 1. Set
function unique1(arr) {
  return [...new Set(arr)]
  // return Array.from(new Set(arr))
}

// 2. for + indexOf, (foreach, filter 类似)
function unique2(arr) {
  const result = []
  for (let i = 0; i < arr.length; i++) {
    if (result.indexOf(arr[i]) > -1) continue
    result.push(arr[i])
  }
  return result
}

// 3. for...of + includes
function unique3(arr) {
  const result = []
  for (const item of arr) {
    if (result.includes(item)) continue
    result.push(item)
  }
  return result
}

// 4. reduce + includes
function unique4(arr) {
  return arr.reduce(
    (prev, cur) => (prev.includes(cur) ? prev : [...prev, cur]),
    []
  )
  // return arr.reduce((prev, cur) => prev.includes(cur) ? prev : prev.concat(cur), [])
  // return arr.reduce((prev, cur) => prev.indexOf(cur) > -1 ? prev : prev.concat(cur), [])
}

// 废弃方案 5. sort + for
function unique5(arr) {
  let result = []
  let last

    // 这里解构是为了不对原数组产生副作用
  ;[...arr]
    // 默认将 key 转为字符串比较，会报错
    .sort((a, b) => (a === b ? 0 : 1))
    .forEach((item) => {
      if (item != last) {
        result.push(item)
        last = item
      }
    })
  return result
}

// 6. 遍历 + `hasOwnProperty` 实现
function unique6(arr) {
  const obj = {}
  return arr.filter((item) => {
    return obj.hasOwnProperty(typeof item + item)
      ? false
      : (obj[typeof item + item] = true)
  })
}

// 7. 遍历 + `Map` 实现
// map 的 key, 不能为 Object.create(null);
function unique7(arr) {
  const map = new Map() // 改为 Map
  return arr.filter((item) => {
    return map.has(item) ? false : !!map.set(item, true)
  })
}

// testing
let name
let symbol = Symbol(1)

// prettier-ignore
let arr = [
  +0, -0, 0, NaN, NaN,
  1, 1, false, false,
  '', '0', '0', '1','NaN',
  undefined, name, null, null,
  // symbol, symbol, Symbol(1), Symbol(2), Symbol(2),
  // 引用类型，不重复
  {}, {},
  Object.create(null), Object.create(null),
  {city: 'shanghai'}, {city: 'shanghai'}
]
console.log(unique1(arr))
console.log(unique2(arr))
console.log(unique3(arr))
console.log(unique4(arr))
console.log(unique5(arr))
console.log(unique6(arr))
console.log(unique7(arr))

// console.log(arr.sort((a, b) => a === b ? 0 : 1))

7. 扩展 ​

  • 数组对象去重（根据特定属性值判断去重）
  • new Set() 的时间复杂度
    • 本质是遍历一次，通过 SameValueZero 判断
    • O(n) 具有线性时间

简单对象数组去重（对象为 json 数据） ​

方案

  1. 先把每一项对象转为 json 字符串
  2. for 遍历去重，结合 cache 缓存，记住 index
  3. 将原数组对应位置去除
点我查看详细
js
// JSON 对象数组去重 (只做第一层级)
// 1. 遍历
// 2. 转为 JSON 字符串 (需要先按 key 排序)
// 3. 判断是否已缓存，是则直接跳过，否则就 push 到新数组里

function uniqueJsonArr(arr) {
  const cache = {}

  const result = []
  for (let i = 0; i < arr.length; i++) {
    let current = arr[i]
    current = sortObj(current) // 补充排序操作
    const jsonStr = JSON.stringify(current)
    if (cache[jsonStr]) continue
    cache[jsonStr] = true
    result.push(arr[i])
  }
  return result
}

// testing
const jsonArr = [
  { name: 'red', age: 25 },
  { age: 25, name: 'red' },
  { name: 'green', age: 27 },
  { name: 'green', age: 27 },
  { name: 'blue', age: 28 },
  { name: 'blue', age: 28, phone: '123' },
]
console.log(uniqueJsonArr(jsonArr))

// 对象按 key 排序
function sortObj(obj) {
  const keys = Object.keys(obj).sort()
  const result = {}

  while (keys.length) {
    const key = keys.pop()
    result[key] = obj[key]
  }
  return result
}

参考：