an ckick pictrue

吃饭不洗...segmentfault 专栏

重新认识ES6中的Set(刷Leetcode有感)

Issue链接更新于:2020-03-17

面试官:对这个数组去重:

const dupArr = [2,3,4,4,2,3,3,4,4,5,5,6,6,7,5,32,3,4,5];

doddle:

[...new Set()]; // [2, 3, 4, 5, 6, 7, 32]

面试官:嗯,不错,知道用ES6语法,关于Set还知道什么? doddle:嗯…(不知所云一堆堆) 面试官:WeakSet呢?

距离ES6的发布应该有5年了,但除了const、import,…, 箭头函数这些新特性在工作中常接触外,Map、Set、Symbol出场机会还是寥寥无几,至少不如const、import露脸机会多。进来抽空去刷了一下算法,发现好的算法实现真的需要依赖好的数据结构。这篇文章着重讲怎么讲这些新的数据结构应用进日常开发以及刷Leetcode

重学Set

关于Set,我个人觉得最好的入门文档,还是出自MDN:JavaScript 标准内置对象-Set;里面涵盖了一些标准用法,使用场景,API介绍等,这里就不再赘述。

一句很长的话总结:
「1」:Set 对象允许你存储任何类型的唯一值,无论是原始值或者是对象引用;
「2」:你可以按照插入的顺序迭代它的元素;
「3」:Set中的元素只会出现一次,即 Set 中的元素是唯一的;

通过上面的了解,我们会感觉与我们熟知的Array真的好像,除了第三点,元素是唯一的,所以有了开场的数组去重。但Set与Array区别不止于此,从CURD四个方面来描述他们操作时间复杂度:

  • C-添加:一样,都为O(1),但是在遇到多类数组(数组元素类型不一样),Set操作是快要Array的;
  • U-更新:因为Set的键和值是相同的(数组键是索引,值是数组元素),所以不存在更新操作;
  • R-查:Set的has是O(1),而Array不管是indexOf或ES6新出的inclueds,都是O(n);
  • D-删除:Set的delete是O(1),而Array严格意义来讲是没有删除操作,借助于splice,谁都知道这性能可能达不到O(n);

活学活用

前几天我对接公司新的埋点库时,遇到这样一个问题,当埋点需要动态传参时,不能传一些埋点已有的关键字,比如传参是这个格式:

{
    bid: 'h5_activity', // 活动Id
    page_name: 'index', // 页面名
    event_id: '', // 埋点时间Id
    ... // 自定义动态传参扩展部分
}

但传到埋点库的数据远不止上面这些,埋点库会自己去捕获一些数据,比如userId,user_agent,app_version…等等,在自定义传参时,再用这些字段,会导致原始数据被修改,埋点失效,所以我当时第一个直觉就是将这个隐藏的知识点做成一个白名单,在非生产模式下进行提示,虽然白名单中的元素不多(30左右),选择array来做,也没什么问题,但是我还是选择了Set,利用Has操作,来提高代码性能,现在来看看具体实现(伪代码);

  const whiteList = new Set(['userId', 'user_agent', 'app_version', ...]);
  function findInvalidKeys(values) {
    // 判断是否是生产环境,是的话,就不检查了
    return isProduction ? [] :Object.keys(values).filter(key => whiteList.has(key));
  }

代码实现很简单,虽然提升很小,但在日常工作中,我们需要有这种打破传统,打破固有思维,应用新学知识的习惯。

你好Set,这是WeakSet

如果说Set偶尔能用上,那WeakSet在日常开发基本就出于隐身的状态了,但最近刷Leetcode,我对WeakSet的运用突然多了起来。关于WeakSet,还是推荐MDN文档:JavaScript 标准内置对象-WeakSet

一句话总结:WeakSet 集合只存储对象弱引用,不可存储原始值;集合中的弱引用如果是对象唯一的引用,则会被垃圾回收

因为上面的特性,WeakSet相比Set也失去了一些方法和特性

  • 只支持has,add,delete方法
  • 没有size属性,不可迭代

没有size属性,不可迭代,原对象已被删除,那证实垃圾回收机制是否真的已经回收了呢,代码测试好像不可行?但是,还是有办法的,比如可以依赖Chrome的内存分析,我写了这样一段代码:

const length = 100000;

function createSet() {
  let arr = [];
  const head = { head: true };
  // 将Set换成WeakSet,即是对比试验的代码;
  const st = new Set();
  st.add(head);
  for (let i = 0; i < length; i++) {
    arr[i] = {
      value: i
    };
    st.add(arr[i]);
  }
  console.log('set create test success');
  return function destory() {
    // 销毁数组的对象引用
    for (let i = 0; i < length; i++) {
      arr[i] = null;
    }
    console.log('is:', st.has(head));
  }
}

设置了两个按钮,一个按钮是创建一个数组对象,并相应的创建一个Set集合,通过查看创建前,创建后,销毁后

<script>
  let callback;
  document.querySelector('#step1').addEventListener('click', () => {
      callback = createSet();
  });

  document.querySelector('#step2').addEventListener('click', () => {
      callback && callback();
  });
</script>

然后通过对比,得到下面的内存分析结果(创建前 -> 创建后-> 销毁后): 对比图

意外的惊喜就是,chrome的内存分析,对于WeakSet也是能看到集合的大小的:

image

事实证明,弱引用真的让垃圾回收起效果了,最后剩的那一个是我故意留下的标志

const head = { head: true }。  

关于内存分析哪些需要知道的概念:V8内存分析

刷LeetCode好帮手

我发现在链表的操作中,Set是一个极好使的API,虽然我刷的都是一些中等或则简单的题目,举个例子:

相交链表

image
这个题难度简单,方法有很多,比如暴力两重循环,双指针,但我觉得最简单的解法就是利用Set,或则Weakset来解,时间复杂度也最低,代码示例:

// 第一步,循环一个链表,Set集合存储所有指针索引
// 第二部,循环第二个链表,看索引是否已存在集合中
var getIntersectionNode = function(headA, headB) {
    if (!headA || !headB) {
        return null;
    }
    let wet = new WeakSet();
    while(headA) {
        wet.add(headA);
        headA = headA.next;
    }
    while(headB) {
        if(wet.has(headB)) {
            break;
        }
        headB = headB.next;
    }
    return headB;
};

相似的题目还有下面这些,我遇到过的:

相信还有更多的用法等着你来发现。

如果你有好的应用场景,或则我的文章有什么不足之处,请在下方留下你的评论指正。

原文见:https://github.com/closertb/closertb.github.io/issues/43