js实现哈希

哈希表的基本实现

在JavaScript中，哈希表可以通过对象或Map类实现。对象是键值对的集合，键通常是字符串或Symbol；Map则支持任意类型的键，并提供更丰富的操作方法。

// 使用对象实现
const hashTable = {};
hashTable['key1'] = 'value1';
hashTable['key2'] = 'value2';
console.log(hashTable['key1']); // 输出: value1

// 使用Map实现
const map = new Map();
map.set('key1', 'value1');
map.set('key2', 'value2');
console.log(map.get('key1')); // 输出: value1

自定义哈希函数

若需自定义哈希函数，可将任意数据类型转换为固定长度的哈希值。以下是一个简单字符串哈希函数的实现：

function hashString(str) {
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
        hash = (hash << 5) - hash + str.charCodeAt(i);
        hash |= 0; // 转换为32位整数
    }
    return hash;
}
console.log(hashString('hello')); // 输出: 99162322

处理哈希冲突

哈希冲突可通过开放寻址法或链地址法解决。以下是链地址法的实现示例：

class HashTable {
    constructor(size = 32) {
        this.size = size;
        this.buckets = Array(size).fill(null).map(() => []);
    }

    _hash(key) {
        return hashString(key) % this.size;
    }

    set(key, value) {
        const index = this._hash(key);
        const bucket = this.buckets[index];
        const found = bucket.find(item => item.key === key);
        found ? found.value = value : bucket.push({ key, value });
    }

    get(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];
        const found = bucket.find(item => item.key === key);
        return found ? found.value : undefined;
    }
}

const table = new HashTable();
table.set('name', 'Alice');
console.log(table.get('name')); // 输出: Alice

实际应用示例

哈希表常用于缓存、频率统计等场景。以下是一个统计字符频率的示例：

function countChars(str) {
    const freq = {};
    for (const char of str) {
        freq[char] = (freq[char] || 0) + 1;
    }
    return freq;
}
console.log(countChars('javascript')); // 输出: { j:1, a:2, v:1, ... }

性能优化

为减少哈希冲突，可动态调整哈希表大小（再哈希）。当元素数量超过负载因子（如70%）时，扩容并重新分配所有键值对：

class DynamicHashTable extends HashTable {
    constructor() {
        super();
        this.count = 0;
        this.loadFactor = 0.7;
    }

    set(key, value) {
        super.set(key, value);
        this.count++;
        if (this.count / this.size > this.loadFactor) {
            this._resize();
        }
    }

    _resize() {
        const oldBuckets = this.buckets;
        this.size *= 2;
        this.buckets = Array(this.size).fill(null).map(() => []);
        this.count = 0;
        oldBuckets.forEach(bucket => {
            bucket.forEach(({ key, value }) => this.set(key, value));
        });
    }
}