js hasmap实现

HashMap 实现原理

HashMap 是基于哈希表的 Map 接口实现，允许使用 null 键和 null 值。它通过键的哈希码来存储数据，具有快速的访问速度。

核心组成部分

哈希函数 将键转换为数组索引的过程，通常使用键的 hashCode() 方法并结合扰动函数减少哈希冲突。

function hash(key) {
    let hashCode = 0;
    for (let i = 0; i < key.length; i++) {
        hashCode = (hashCode << 5) - hashCode + key.charCodeAt(i);
        hashCode |= 0; // Convert to 32-bit integer
    }
    return hashCode;
}

数组+链表/红黑树 哈希表底层是数组结构，每个数组元素称为桶(bucket)。当发生哈希冲突时，采用链表法解决冲突，当链表长度超过阈值时会转为红黑树。

基本操作实现

put 方法实现 计算键的哈希值确定存储位置，处理哈希冲突后插入键值对。

class HashMap {
    constructor(initialCapacity = 16, loadFactor = 0.75) {
        this.buckets = new Array(initialCapacity);
        this.loadFactor = loadFactor;
        this.size = 0;
    }

    put(key, value) {
        const index = this._getIndex(key);
        if (!this.buckets[index]) {
            this.buckets[index] = [];
        }

        const bucket = this.buckets[index];
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i].key === key) {
                bucket[i].value = value;
                return;
            }
        }

        bucket.push({ key, value });
        this.size++;

        if (this.size > this.buckets.length * this.loadFactor) {
            this._resize();
        }
    }
}

get 方法实现 通过哈希函数定位到对应桶，然后在链表或树中查找。

get(key) {
    const index = this._getIndex(key);
    const bucket = this.buckets[index];
    if (!bucket) return undefined;

    for (const entry of bucket) {
        if (entry.key === key) {
            return entry.value;
        }
    }
    return undefined;
}

扩容机制

当元素数量超过容量与负载因子的乘积时，进行扩容操作，通常扩大为原来的2倍。

_resize() {
    const newCapacity = this.buckets.length * 2;
    const newBuckets = new Array(newCapacity);

    for (const bucket of this.buckets) {
        if (!bucket) continue;
        for (const entry of bucket) {
            const newIndex = this._getIndex(entry.key, newCapacity);
            if (!newBuckets[newIndex]) {
                newBuckets[newIndex] = [];
            }
            newBuckets[newIndex].push(entry);
        }
    }

    this.buckets = newBuckets;
}

完整实现示例

class HashMap {
    constructor(initialCapacity = 16, loadFactor = 0.75) {
        this.buckets = new Array(initialCapacity);
        this.loadFactor = loadFactor;
        this.size = 0;
    }

    _hash(key) {
        let hashCode = 0;
        for (let i = 0; i < key.length; i++) {
            hashCode = (hashCode << 5) - hashCode + key.charCodeAt(i);
            hashCode |= 0;
        }
        return hashCode;
    }

    _getIndex(key, capacity = this.buckets.length) {
        return Math.abs(this._hash(key)) % capacity;
    }

    put(key, value) {
        const index = this._getIndex(key);
        if (!this.buckets[index]) {
            this.buckets[index] = [];
        }

        const bucket = this.buckets[index];
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i].key === key) {
                bucket[i].value = value;
                return;
            }
        }

        bucket.push({ key, value });
        this.size++;

        if (this.size > this.buckets.length * this.loadFactor) {
            this._resize();
        }
    }

    get(key) {
        const index = this._getIndex(key);
        const bucket = this.buckets[index];
        if (!bucket) return undefined;

        for (const entry of bucket) {
            if (entry.key === key) {
                return entry.value;
            }
        }
        return undefined;
    }

    _resize() {
        const newCapacity = this.buckets.length * 2;
        const newBuckets = new Array(newCapacity);

        for (const bucket of this.buckets) {
            if (!bucket) continue;
            for (const entry of bucket) {
                const newIndex = this._getIndex(entry.key, newCapacity);
                if (!newBuckets[newIndex]) {
                    newBuckets[newIndex] = [];
                }
                newBuckets[newIndex].push(entry);
            }
        }

        this.buckets = newBuckets;
    }
}

性能优化考虑

哈希冲突处理 当链表长度超过8时，可以考虑转换为红黑树，将查找时间复杂度从O(n)降为O(log n)。

哈希函数优化 使用更好的扰动函数减少哈希冲突，如Java HashMap中的高位运算：

_hash(key) {
    let h = 0;
    for (let i = 0; i < key.length; i++) {
        h = (h << 5) - h + key.charCodeAt(i);
        h ^= (h >>> 16); // 高位扰动
        h |= 0;
    }
    return h;
}

容量选择 初始容量最好选择2的幂次方，这样可以使用位运算代替取模运算提高效率：

_getIndex(key, capacity = this.buckets.length) {
    return this._hash(key) & (capacity - 1);
}