Set集合

为什么需要Set？

在前端开发中，Set是一个非常实用的数据结构：

• 天然去重
• 高效的查找操作
• 方便的集合运算
• 良好的代码可读性

原生Set vs 自定义Set实现

1. 原生Set的使用

// 创建Set
const set = new Set([1, 2, 3, 3]); // Set(3) {1, 2, 3}

// 常用操作
set.add(4);           // 添加元素
set.has(1);          // 检查元素
set.delete(2);       // 删除元素
set.size;            // 获取大小
set.clear();         // 清空集合

// 集合运算
const set1 = new Set([1, 2, 3]);
const set2 = new Set([2, 3, 4]);

// 并集
const union = new Set([...set1, ...set2]);

// 交集
const intersection = new Set([...set1].filter(x => set2.has(x)));

// 差集
const difference = new Set([...set1].filter(x => !set2.has(x)));

2. 自定义Set实现

class CustomSet {
    constructor() {
        this.items = {};
    }
    
    // 添加元素
    add(value) {
        if (this.has(value)) return false;
        this.items[value] = value;
        return true;
    }
    
    // 检查元素
    has(value) {
        return Object.prototype.hasOwnProperty.call(this.items, value);
    }
    
    // 删除元素
    remove(value) {
        if (!this.has(value)) return false;
        delete this.items[value];
        return true;
    }
    
    // 获取所有值
    values() {
        return Object.values(this.items);
    }
    
    // 获取大小
    size() {
        return Object.keys(this.items).length;
    }
    
    // 清空集合
    clear() {
        this.items = {};
    }
    
    // 并集操作
    union(otherSet) {
        const unionSet = new CustomSet();
        this.values().forEach(value => unionSet.add(value));
        otherSet.values().forEach(value => unionSet.add(value));
        return unionSet;
    }
    
    // 交集操作
    intersection(otherSet) {
        const intersectionSet = new CustomSet();
        const values = this.values();
        values.forEach(value => {
            if (otherSet.has(value)) {
                intersectionSet.add(value);
            }
        });
        return intersectionSet;
    }
}

哈希表(Hash Table)

哈希表的重要性

哈希表在前端开发中的应用场景：

• 缓存管理
• 数据去重
• 快速查找
• 对象属性存储
• 性能优化

哈希表的核心概念

1. 基本原理

• 通过哈希函数将key转换为数组索引
• 处理哈希冲突
• 动态扩容

2. 实现示例

class HashMap {
    constructor(size = 53) {
        this.keyMap = new Array(size);
    }
    
    // 哈希函数
    _hash(key) {
        let total = 0;
        const WEIRD_PRIME = 31;
        for (let i = 0; i < Math.min(key.length, 100); i++) {
            const char = key[i];
            const value = char.charCodeAt(0) - 96;
            total = (total * WEIRD_PRIME + value) % this.keyMap.length;
        }
        return total;
    }
    
    // 设置键值对
    set(key, value) {
        const index = this._hash(key);
        if (!this.keyMap[index]) {
            this.keyMap[index] = [];
        }
        this.keyMap[index].push([key, value]);
    }
    
    // 获取值
    get(key) {
        const index = this._hash(key);
        if (this.keyMap[index]) {
            for (let i = 0; i < this.keyMap[index].length; i++) {
                if (this.keyMap[index][i][0] === key) {
                    return this.keyMap[index][i][1];
                }
            }
        }
        return undefined;
    }
}

实际应用示例

1. 简单的缓存实现

class Cache {
    constructor() {
        this.cache = new Map();
        this.maxSize = 100;
    }
    
    get(key) {
        return this.cache.get(key);
    }
    
    set(key, value) {
        if (this.cache.size >= this.maxSize) {
            // 删除最早添加的项
            const firstKey = this.cache.keys().next().value;
            this.cache.delete(firstKey);
        }
        this.cache.set(key, value);
    }
}

2. 数据去重

function uniqueElements(array) {
    return [...new Set(array)];
}

// 对象数组去重
function uniqueObjectsBy(array, key) {
    const seen = new Map();
    return array.filter(item => {
        const value = item[key];
        if (seen.has(value)) {
            return false;
        }
        seen.set(value, true);
        return true;
    });
}

性能对比

操作	Array	Object	Map	Set
查找	O(n)	O(1)	O(1)	O(1)
插入	O(1)	O(1)	O(1)	O(1)
删除	O(n)	O(1)	O(1)	O(1)

最佳实践

1. 使用Set进行去重操作
2. 需要键值对时使用Map
3. 频繁查找操作使用哈希表
4. 注意内存占用

常见面试题

1. Set和Map的区别？
2. 如何处理哈希冲突？
3. 什么时候使用WeakMap？

推荐练习

1. LeetCode 1: 两数之和
2. LeetCode 217: 存在重复元素
3. LeetCode 349: 两个数组的交集