当前位置：首页 > JavaScript

js实现哈希

2026-04-07 04:11:58JavaScript

哈希表的基本实现

在JavaScript中，哈希表可以通过对象或Map实现。对象是键值对的集合，键必须是字符串或Symbol；Map的键可以是任意类型。

js实现哈希

// 使用对象实现
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

自定义哈希函数

如果需要自定义哈希函数，可以使用以下方法。这里假设键是字符串类型。

js实现哈希

function hashString(key, size) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
        hash = (hash << 5) + hash + key.charCodeAt(i);
        hash = hash & hash; // 转换为32位整数
        hash = Math.abs(hash);
    }
    return hash % size;
}

// 示例
const hash = hashString('hello', 100);
console.log(hash); // 输出一个0到99之间的整数

处理哈希冲突

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

class HashTable {
    constructor(size = 10) {
        this.size = size;
        this.table = new Array(size).fill(null).map(() => []);
    }

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

    set(key, value) {
        const index = this._hash(key);
        const bucket = this.table[index];
        const found = bucket.find(item => item.key === key);
        if (found) {
            found.value = value;
        } else {
            bucket.push({ key, value });
        }
    }

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

    delete(key) {
        const index = this._hash(key);
        const bucket = this.table[index];
        const itemIndex = bucket.findIndex(item => item.key === key);
        if (itemIndex !== -1) {
            bucket.splice(itemIndex, 1);
            return true;
        }
        return false;
    }
}

// 示例
const ht = new HashTable();
ht.set('name', 'Alice');
ht.set('age', 25);
console.log(ht.get('name')); // 输出: Alice
ht.delete('age');
console.log(ht.get('age')); // 输出: undefined

性能优化

哈希表的性能依赖于哈希函数的质量和负载因子。负载因子是表中已存储元素数与总槽数的比值。通常，当负载因子超过0.7时，需要扩容。

class OptimizedHashTable extends HashTable {
    constructor(size = 10) {
        super(size);
        this.count = 0;
    }

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

    delete(key) {
        const deleted = super.delete(key);
        if (deleted) {
            this.count--;
        }
        return deleted;
    }

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

// 示例
const oht = new OptimizedHashTable(5);
oht.set('a', 1);
oht.set('b', 2);
oht.set('c', 3);
oht.set('d', 4);
console.log(oht.size); // 输出: 10 (扩容后)