一道有意思的面试题

[miniflycn]

要求对对象数组[{}, {}, {}...]去重，要求：{ a: 1 }和{ a: 1 }引用不一样，但算重复，则如何去重效率高。

[miniflycn]

@Elliott-Hu 来分享下

[Elliott-Hu]

谢……邀？哈哈，我先抛个砖~ 其实这道面试题相信大家一开始都会想到一个常规的思路，既然引用类型，那么不免会使用到deepEqual，固然这种思路可以解答这道问题，但难免不够高效。

我做过一个小小的测试，像是常规的只带基本类型的数组中，有几种常见的做法。 我们依次跑10万长度随机数的数组去重，耗时如下。

可见通过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 '\n':
      case '\r':
      case '\t':
      break
      default:
        res += string[i].charCodeAt(0) * power
    }
  }
  return res
}

这只是一个基本的思路，为了减少hash碰撞的可能，可以对一些特殊字符进行权重的增减。 重点是保证碰撞的几率小到比中大奖还小就可以了。（交给你们了）

实际效果如何，我去测试一波……

[Elliott-Hu]

关于去重的实现思路，我无耻地甩个链接 https://segmentfault.com/a/1190000013192950

[loskael]

toHash 存在几个问题： 1、JSON.stringify(obj) 比 JSON.stringify(obj, null, 2) 好 2、以下处理在遇到 String 的时候存在碰撞的风险

      case ' ':
      case '\n':
      case '\r':
      case '\t':
      break

3、toHash({a: 12}) === toHash({a: 21})，类似的情况都存在较大碰撞风险

[loskael]

刚搜了一下，发现这个 https://github.com/epoberezkin/fast-deep-equal 发现是通过 length, Object.keys.length, 类型之类的手段做的优化

[miniflycn]

看了一下fast-deep-equal，感觉这样最安全，主要的想法就是判错比判对容易，尽早退出

[Elliott-Hu]

尽可能减少循环的可能，学到了。这种思路应该是数据量越大越明显，所以并不在乎小数据的时候前置判断带来的一点性能损耗了。感觉一开始思路就偏了啊哈哈哈，应该从优化深度比较入手。