前端大厂面试问答[2]

声明：关于以下面试题收集来源
壹题答案综合了自己理解如有误区请帮忙指出，谢谢 😆

第 4 题：介绍下 Set、Map、WeakSet 和 WeakMap 的区别？

后面俩个我都没听过，没事问题不大，一起学习一下。

Set 和 Map ,是ES6 提供的新数据结构

Set

它类似于数组，但是成员的值都是唯一的，没有重复的值。Set 本身是一个构造函数，用来生成 Set 数据结构。

let s = new Set();
[2, 3, 5, 4, 5, 2, 2].forEach(x => s.add(x));
// for...of 语句创建一个循环来迭代可迭代的对象。也是ES6新增 用来替代for-in（这里提一下forin会遍历到原型链的上非枚举属性）
for (let i of s) {
  console.log(i);
}
// 2 3 5 4

WeakSet

WeakSet 结构与 Set 类似，也是不重复的值的集合。但是，它与 Set 有两个区别。
1.WeakSet 的成员只能是对象，而不能是其他类型的值。
2.WeakSet 中的对象都是弱引用，即垃圾回收机制不考虑 WeakSet 对该对象的引用，也就是说，如果其他对象都不再引用该对象，那么垃圾回收机制会自动回收该对象所占用的内存，不考虑该对象还存在于 WeakSet 之中。

const ws = new WeakSet();
ws.add(1);
// TypeError: Invalid value used in weak set
ws.add(Symbol());
// TypeError: invalid value used in weak set

WeakSet 里面的引用，都不计入垃圾回收机制，所以就不存在这个问题。因此，WeakSet 适合临时存放一组对象，以及存放跟对象绑定的信息。只要这些对象在外部消失，它在 WeakSet 里面的引用就会自动消失。由于上面这个特点，WeakSet 的成员是不适合引用的，因为它会随时消失。另外，由于 WeakSet 内部有多少个成员，取决于垃圾回收机制有没有运行，运行前后很可能成员个数是不一样的，而垃圾回收机制何时运行是不可预测的，因此 ES6 规定 WeakSet 不可遍历。
!WeakSet 的一个用处，是储存 DOM 节点，而不用担心这些节点从文档移除时，会引发内存泄漏。

Map

它类似于对象，也是键值对的集合，但是“键”的范围不限于字符串，各种类型的值（包括对象）都可以当作键。也就是说，Object 结构提供了“字符串—值”的对应，Map 结构提供了“值—值”的对应，是一种更完善的 Hash 结构实现。如果你需要“键值对”的数据结构，Map 比 Object 更合适。

简单来说就是记录映射关系的集合

const m = new Map();
const o = { p: 'Hello World' };

m.set(o, 'content');
m.get(o); // "content"

m.has(o); // true
m.delete(o); // true
m.has(o); // false

WeakMap

WeakMap 结构与 Map 结构类似，也是用于生成键值对的集合。
WeakMap 与 Map 的区别有两点。

1.WeakMap 只接受对象作为键名（null 除外），不接受其他类型的值作为键名
2.WeakMap 的键名所指向的对象，不计入垃圾回收机制。(同 WeakSet 一个道理)

const wm = new WeakMap();

// size、forEach、clear 方法都不存在
wm.size; // undefined
wm.forEach; // undefined
wm.clear; // undefined

以上就是这几个函数的主要区别，暂不做深入讨论。

第 5 题：介绍下深度优先遍历和广度优先遍历，如何实现？

深度优先遍历（DFS）

深度优先遍历（Depth-First-Search），是搜索算法的一种，它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点 v 的所有边都已被探寻过，将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已探寻源节点到其他所有节点为止，如果还有未被发现的节点，则选择其中一个未被发现的节点为源节点并重复以上操作，直到所有节点都被探寻完成。

※ 简单理解就是遍历完最近的所有子节点

注意：深度 DFS 属于盲目搜索，无法保证搜索到的路径为最短路径，也不是在搜索特定的路径，而是通过搜索来查看图中有哪些路径可以选择。

广度优先遍历（BFS）

广度优先遍历（Breadth-First-Search）是从根节点开始，沿着图的宽度遍历节点，如果所有节点均被访问过，则算法终止，BFS 同样属于盲目搜索，一般用队列数据结构来辅助实现 BFS

BFS 从一个节点开始，尝试访问尽可能靠近它的目标节点。本质上这种遍历在图上是逐层移动的，首先检查最靠近第一个节点的层，再逐渐向下移动到离起始节点最远的层

※ 简单理解为按层级依次遍历完每层

下面我们着手去试着简单实现一些

// 一个模拟随机层级节点对象
const obj = {
  a: {
    a1: {
      a11: {},
      a12: {}
    },
    a2: {},
    a3: {}
  },
  b: {
    b1: {},
    b2: {}
    b3: {
        b31:{}
    }
  },
  c:{
      c1:{}
  }
};

// 以下代码并非严谨，仅仅用于理解两种遍历算法
// 深度优先遍历
function dfs(obj) {
  for (k of obj) {
    const item = obj[k];
    if (!!item && typeof item === 'object') {
      dfs(item);
    }
  }
}
// 广度优先遍历
function bfs(obj) {
  let queue = [];
  for (k of obj) {
    const item = obj[k];
    if (!!item && typeof item === 'object') {
      queue.unshift(item);
    }
  }
  queue.forEach(v => {
    if (!!v && typeof v === 'object') {
      bfs(v);
    }
  });
}

第 6 期：请分别用深度优先思想和广度优先思想实现一个拷贝函数？

那么结合上面算法思路我想简单实现一些实际生产环境中遇到的问题，关于对象的深拷贝；

// ================ 工具函数 ============
const TYPE_MAP = {
  array: '[object Array]',
  object: '[object Object]',
  function: '[object Function]',
  string: '[object String]',
  null: '[object Null]',
  undefined: '[object Undefined]',
  boolean: '[object Boolean]',
  number: '[object Number]'
};
const _toString = function(obj) {
  return Object.prototype.toString.call(obj);
};
const isTypeof = function(obj, type = 'object') {
  if (!TYPE_MAP[type]) throw new Error('传入类型不支持');
  return _toString(obj) === TYPE_MAP[type];
};
// ====================================
function dfsClone(obj) {
  let newObj = {};
  if (isTypeof(obj, 'object') || isTypeof(obj, 'array')) {
    newObj = isTypeof(obj, 'array') ? [] : {};
    for (k in obj) {
      newObj[k] = dfsClone(obj[k]);
    }
  } else if (isTypeof(obj, 'function')) {
    newObj = eval(`(${obj.toString()})`);
  } else {
    newObj = obj;
  }
  return newObj;
}
/**
 * 遍历首层对象
 * 依次判断每一项值是不是对象
 * 如果是，存入队列，继续走完当前层
 * 走完队列遍历，判断
 **/

function bfsClone(obj) {
  let newObj = {};
  let queue = [];
  let org = [obj];
  // TODO 没写完大脑一片空白，兄弟们帮忙补一下
  if (isTypeof(obj, 'object') || isTypeof(obj, 'array')) {
    for (k in obj) {
      newObj[k] = obj[k];
      bfsClone(obj);
    }
  }
}