当前位置：首页 > JavaScript

js实现哈希

2026-02-02 10:40:33JavaScript

哈希表的基本实现

在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 + key.charCodeAt(i) * (i + 1)) % size;
    }
    return hash;
}

console.log(hashString('hello', 100)); // 输出一个0-99的哈希值

处理哈希冲突

常见冲突解决方法包括链地址法（用数组或链表存储冲突项）和开放寻址法（线性探测、二次探测等）。以下是链地址法的实现：

class HashTable {
    constructor(size = 10) {
        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 existing = bucket.find(item => item.key === key);
        if (existing) {
            existing.value = value;
        } else {
            bucket.push({ key, value });
        }
    }

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

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

性能优化建议

扩容机制：当元素数量超过容量的一定比例（如70%）时，动态扩容并重新哈希。
优质哈希函数：减少冲突概率，确保分布均匀（如使用质数模数）。
选择数据结构：高频操作场景下，Map比普通对象性能更优。

实际应用示例

// 统计词频
const text = "hello world hello";
const frequency = new Map();
text.split(' ').forEach(word => {
    frequency.set(word, (frequency.get(word) || 0) + 1);
});
console.log(frequency.get('hello')); // 输出: 2

标签: js