JS如何实现哈希集合？哈希冲突处理

Map

Map

Map

HashSet

class MyHashSet {
    // 内部使用Map来存储元素。
    // 对于简单类型（字符串、数字、布尔值），Map的键已经足够作为哈希值。
    // 对于复杂对象，我们需要额外的哈希函数和冲突处理。
    constructor() {
        this.data = new Map();
    }

    /**
     * 添加一个元素到集合中。
     * @param {*} value 要添加的元素。
     * @returns {boolean} 如果元素是新添加的，返回true；否则返回false。
     */
    add(value) {
        // 这里的关键是：如何将value转换为Map能识别的“唯一键”。
        // 对于简单类型，value本身就是键。
        // 对于复杂对象，我们需要一个哈希函数。
        const key = this._getHashKey(value);
        if (this.data.has(key)) {
            // 如果Map中已经存在这个哈希键，那可能是真正的重复，也可能是哈希冲突。
            // 针对冲突，我们需要在对应的“桶”里检查value的实际内容。
            // 默认情况下，如果_getHashKey已经处理了冲突（比如返回一个唯一标识），
            // 那么这里直接判断即可。
            // 否则，如果key是哈希值，value是桶（数组），则需要遍历桶。

            // 假设_getHashKey已经足够“唯一”，或者我们正在处理简单类型。
            // 对于复杂对象，我们通常会用链表法，key对应一个数组或Set。
            let bucket = this.data.get(key);
            if (!bucket) { // 第一次遇到这个哈希值
                bucket = [];
                this.data.set(key, bucket);
            }
            // 检查桶中是否已存在该元素（基于内容比较）
            if (!bucket.some(item => this._isEqual(item, value))) {
                bucket.push(value);
                return true;
            }
            return false;
        } else {
            // 新的哈希键，直接创建桶并添加
            this.data.set(key, [value]);
            return true;
        }
    }

    /**
     * 检查集合中是否包含某个元素。
     * @param {*} value 要检查的元素。
     * @returns {boolean} 如果集合包含该元素，返回true；否则返回false。
     */
    has(value) {
        const key = this._getHashKey(value);
        const bucket = this.data.get(key);
        if (!bucket) {
            return false;
        }
        // 遍历桶，进行内容比较
        return bucket.some(item => this._isEqual(item, value));
    }

    /**
     * 从集合中删除一个元素。
     * @param {*} value 要删除的元素。
     * @returns {boolean} 如果元素被成功删除，返回true；否则返回false。
     */
    delete(value) {
        const key = this._getHashKey(value);
        let bucket = this.data.get(key);
        if (!bucket) {
            return false;
        }
        const initialLength = bucket.length;
        // 过滤掉要删除的元素
        bucket = bucket.filter(item => !this._isEqual(item, value));
        if (bucket.length === 0) {
            this.data.delete(key); // 如果桶空了，就删除这个哈希键
        } else if (bucket.length < initialLength) {
            this.data.set(key, bucket); // 更新桶
        }
        return bucket.length < initialLength;
    }

    /**
     * 返回集合中元素的数量。
     * @returns {number} 集合的大小。
     */
    get size() {
        let count = 0;
        for (const bucket of this.data.values()) {
            count += bucket.length;
        }
        return count;
    }

    /**
     * 内部方法：生成元素的哈希键。
     * 这是哈希冲突处理的关键点。
     * @param {*} value
     * @returns {string | number} 用于Map的键。
     */
    _getHashKey(value) {
        // 简单类型直接返回自身
        if (typeof value !== 'object' || value === null) {
            return value;
        }
        // 对于复杂对象，这里需要一个自定义的哈希函数。
        // 最简单粗暴（但有缺陷）的方式是JSON.stringify。
        // 后面会详细讨论如何写更健壮的哈希函数。
        try {
            return JSON.stringify(value);
        } catch (e) {
            // 处理循环引用等JSON.stringify无法处理的情况
            // 实际应用中需要更复杂的策略，比如为每个对象生成一个内部ID
            // 或者使用更高级的哈希算法库
            console.warn("无法对对象进行JSON.stringify，可能存在循环引用或非JSON兼容数据:", value);
            // 这是一个兜底方案，但会导致不同对象被视为相同，需要警惕
            return String(value); // 比如 "[object Object]"
        }
    }

    /**
     * 内部方法：判断两个值是否相等（深比较）。
     * @param {*} a
     * @param {*} b
     * @returns {boolean}
     */
    _isEqual(a, b) {
        // 对于简单类型，直接比较
        if (typeof a !== 'object' || a === null || typeof b !== 'object' || b === null) {
            return a === b;
        }
        // 简单对象浅比较（如果需要深比较，这里会很复杂）
        // 在哈希集合语境下，如果_getHashKey已经足够好，这里可能只需要浅比较
        // 否则，就需要一个递归的深比较函数
        const aKeys = Object.keys(a);
        const bKeys = Object.keys(b);

        if (aKeys.length !== bKeys.length) {
            return false;
        }

        for (const key of aKeys) {
            if (!b.hasOwnProperty(key) || a[key] !== b[key]) {
                return false;
            }
        }
        return true;
    }
}

// 示例用法
const mySet = new MyHashSet();
mySet.add(1);
mySet.add("hello");
mySet.add({a: 1, b: 2});
mySet.add({b: 2, a: 1}); // 期望被视为重复，如果_getHashKey和_isEqual处理得当
mySet.add({c: 3});

console.log("集合大小:", mySet.size); // 期望是 4 (1, "hello", {a:1, b:2}, {c:3})

console.log("是否包含 1:", mySet.has(1));
console.log("是否包含 {a:1, b:2}:", mySet.has({a:1, b:2}));
console.log("是否包含 {c:4}:", mySet.has({c:4}));

mySet.delete({a:1, b:2});
console.log("删除 {a:1, b:2} 后大小:", mySet.size);
console.log("删除后是否包含 {a:1, b:2}:", mySet.has({a:1, b:2}));

HashSet

Object

Map

Set

Set

undefined

null

Set

Set

Set

Map

Object

Map

Set

Map

Object

MyHashSet

Map

Set

MyHashSet

this.data

_getHashKey

this.data.get(key)

add

has

delete

{a: 1}

{a: 1}

_getHashKey

_isEqual

JSON.stringify