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;
}
