js实现hash

JavaScript 实现哈希表

哈希表是一种通过键值对存储数据的数据结构，JavaScript 中可以通过对象或 Map 实现。

使用对象实现哈希表

对象是 JavaScript 中最简单的哈希表实现方式，键值对存储直接使用对象的属性和值。

const hashTable = {};

// 添加键值对
hashTable['key1'] = 'value1';
hashTable['key2'] = 'value2';

// 获取值
console.log(hashTable['key1']); // 输出: value1

// 删除键值对
delete hashTable['key1'];

// 检查键是否存在
console.log('key1' in hashTable); // 输出: false

使用 Map 实现哈希表

Map 是 ES6 引入的更专业的哈希表实现，支持任意类型的键，并提供更多操作方法。

const hashMap = new Map();

// 添加键值对
hashMap.set('key1', 'value1');
hashMap.set('key2', 'value2');

// 获取值
console.log(hashMap.get('key1')); // 输出: value1

// 删除键值对
hashMap.delete('key1');

// 检查键是否存在
console.log(hashMap.has('key1')); // 输出: false

// 获取大小
console.log(hashMap.size); // 输出: 1

自定义哈希函数

如果需要更复杂的哈希逻辑，可以自定义哈希函数。

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

const size = 100;
const key = 'example';
console.log(customHash(key, size)); // 输出哈希值

处理哈希冲突

哈希冲突可以通过链地址法（数组+链表）或开放寻址法解决。

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

  _hash(key) {
    let hash = 0;
    for (let char of key) {
      hash = (hash << 5) - hash + char.charCodeAt(0);
      hash |= 0;
    }
    return Math.abs(hash) % this.size;
  }

  set(key, value) {
    const index = this._hash(key);
    const bucket = this.table[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.table[index];
    const item = bucket.find(item => item.key === key);
    return item ? item.value : undefined;
  }

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

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

性能优化

哈希表的性能取决于哈希函数的质量和冲突处理方式。好的哈希函数应均匀分布键，减少冲突。

// 优化哈希函数示例
function optimizedHash(key, size) {
  let hash = 5381;
  for (let i = 0; i < key.length; i++) {
    hash = (hash * 33) ^ key.charCodeAt(i);
  }
  return Math.abs(hash) % size;
}