前端大厂面试问答[2]

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

第 4 题:介绍下 Set、Map、WeakSet 和 WeakMap 的区别?

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

SetMap ,是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 结构类似,也是用于生成键值对的集合。
WeakMapMap 的区别有两点。

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);
}
}
}

未完待续。。。


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×