JavaScript中Map和Set数据结构的底层实现原理
- Map
- 原理：JavaScript中的
Map是一种键值对的集合。它的底层实现通常基于哈希表。在哈希表中，通过对键进行哈希运算，得到一个哈希值，这个哈希值对应到哈希表中的一个位置，用来存储键值对。哈希表通过解决哈希冲突（比如链地址法或开放地址法）来处理不同键可能产生相同哈希值的情况。Map与普通对象的区别在于，Map可以使用任何类型的值作为键，而普通对象的键只能是字符串或Symbol类型。而且Map维护键值对的插入顺序，在迭代Map时，会按照插入顺序返回元素。
- Set
- 原理：
Set是一种值的集合，其中每个值都是唯一的。其底层实现也是基于哈希表。Set在添加值时，通过对值进行哈希运算，找到对应的哈希位置进行存储。同样会处理哈希冲突。当检查一个值是否在Set中时，会再次对该值进行哈希运算，快速定位到可能存储该值的位置，然后进行比较判断。
实现具有过期时间的Set数据结构
- 设计思路
- 基于原生
Set进行扩展，创建一个新的类，比如ExpiringSet。
- 每个存储在
Set中的值，都需要关联一个过期时间。可以使用一个辅助的Map来存储值与其对应的过期时间。
- 提供一个方法来定期检查并移除过期的元素。
- 代码实现
class ExpiringSet {
constructor() {
this.set = new Set();
this.expiryMap = new Map();
this.interval = null;
}
add(value, duration) {
this.set.add(value);
const expiration = Date.now() + duration;
this.expiryMap.set(value, expiration);
if (!this.interval) {
this.startAutoCleanup();
}
return this;
}
has(value) {
if (!this.set.has(value)) {
return false;
}
const expiration = this.expiryMap.get(value);
return expiration > Date.now();
}
startAutoCleanup() {
this.interval = setInterval(() => {
const now = Date.now();
this.set.forEach((value) => {
const expiration = this.expiryMap.get(value);
if (expiration && expiration <= now) {
this.set.delete(value);
this.expiryMap.delete(value);
}
});
}, 1000);
}
clear() {
this.set.clear();
this.expiryMap.clear();
if (this.interval) {
clearInterval(this.interval);
this.interval = null;
}
}
}
- 处理过期元素的移除
- 在
startAutoCleanup方法中，使用setInterval定时检查每个元素的过期时间。每次检查时，获取当前时间，遍历Set中的每个值，从expiryMap中获取其对应的过期时间，如果过期时间小于等于当前时间，则从Set和expiryMap中删除该值。
- 性能方面的考虑
- 定期检查频率：
setInterval的时间间隔设置为1秒，这个频率可以根据实际应用场景调整。如果频率过高，会增加性能开销；频率过低，可能导致过期元素不能及时移除。
- 数据量较大时：遍历
Set和Map的操作时间复杂度为O(n)，当数据量较大时，可能会影响性能。可以考虑优化数据结构，比如使用更高效的过期数据管理算法，或者将数据分区，减少每次检查的范围。同时，在添加和删除元素时，尽量保持数据结构的平衡，以减少哈希冲突带来的性能损耗。
