JavaScript is required

2025-11-27-JavaScript 实现哈希表

哈希表（Hash Table，散列表）是一种通过键（Key）直接访问值（Value）的数据结构，通过哈希函数将键映射到表中的位置

算法#数据结构#哈希表#JavaScript

JavaScript 实现哈希表

哈希表（Hash Table，散列表）是一种通过键（Key）直接访问值（Value）的数据结构，通过哈希函数将键映射到表中的位置

哈希函数

ts
// 简单的哈希函数示例
function hashString(key, tableSize) {
  let hash = 17
  for (let i = 0; i < key.length; i++) {
    hash = (13 * hash * key.charCodeAt(i)) % tableSize
  }
  return hash
}

用 JavaScript 实现哈希表

自动扩容

支持任何类型键的通用哈希表

使用 JavaScript 内置结构

使用 Object

js
// 最简单的哈希表实现
const hashTable = {}
hashTable['key1'] = 'value1'
hashTable['key2'] = 'value2'

// 获取
const value = hashTable['key1']

// 删除
delete hashTable['key1']

使用 Map

js
// ES6 Map 是更好的哈希表实现
const map = new Map()

// 设置键值对
map.set('name', 'Alice')
map.set(42, 'The Answer')
map.set({ id: 1 }, 'Object Key')

// 获取
console.log(map.get('name')) // Alice

// 检查是否存在
console.log(map.has(42)) // true

// 删除
map.delete(42)

// 大小
console.log(map.size)

// 遍历
map.forEach((value, key) => {
  console.log(key, value)
})

// 清空
map.clear()

使用 Set（类似哈希集合）

js
// 用于存储唯一值
const set = new Set()

set.add(1)
set.add(2)
set.add(2) // 重复，不会被添加

console.log(set.has(1)) // true
console.log(set.size) // 2

set.delete(1)

性能优化

选择合适的哈希函数

js
// 更好的字符串哈希函数（djb2算法）
function hashDJB2(str, tableSize) {
  let hash = 5381
  for (let i = 0; i < str.length; i++) {
    hash = (hash * 33) ^ str.charCodeAt(i)
  }
  return Math.abs(hash) % tableSize
}

优化冲突处理

js
class OptimizedHashTable {
  constructor(size = 53) {
    this.table = new Array(size)
    this.deleted = Symbol('deleted') // 特殊标记删除
  }

  // 二次探测
  _probe(index, i, tableSize) {
    return (index + i * i) % tableSize
  }

  // 双重哈希
  _doubleHash(index, i, tableSize, key) {
    const hash2 = 1 + (this._hash2(key) % (tableSize - 1))
    return (index + i * hash2) % tableSize
  }
}

实际应用

频率计数器

js
function frequencyCounter(arr) {
  const frequency = new Map()

  for (const item of arr) {
    frequency.set(item, (frequency.get(item) || 0) + 1)
  }

  return frequency
}

// 使用
const arr = ['apple', 'banana', 'apple', 'orange', 'banana', 'banana']
const freq = frequencyCounter(arr)
console.log(freq.get('banana')) // 3

缓存实现（LRU Cache）

js
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.cache = new Map() // 哈希表 + 维护顺序
  }

  get(key) {
    if (!this.cache.has(key)) return -1

    const value = this.cache.get(key)
    this.cache.delete(key)
    this.cache.set(key, value) // 更新为最近使用

    return value
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key)
    } else if (this.cache.size >= this.capacity) {
      // 删除最久未使用的
      const oldestKey = this.cache.keys().next().value
      this.cache.delete(oldestKey)
    }

    this.cache.set(key, value)
  }
}

分组算法

js
function groupBy(array, keyFn) {
  const groups = new Map()

  for (const item of array) {
    const key = typeof keyFn === 'function' ? keyFn(item) : item[keyFn]

    if (!groups.has(key)) {
      groups.set(key, [])
    }

    groups.get(key).push(item)
  }

  return groups
}

// 使用
const people = [
  { name: 'Alice', age: 25 },
  { name: 'Bob', age: 30 },
  { name: 'Charlie', age: 25 },
]

const groupedByAge = groupBy(people, 'age')
console.log(groupedByAge.get(25))
// [{ name: 'Alice', age: 25 }, { name: 'Charlie', age: 25 }]

复杂度

操作ObjectMap自定义哈希表
插入O(1)O(1)O(1)-O(n)
查找O(1)O(1)O(1)-O(n)
删除O(1)O(1)O(1)-O(n)
遍历键O(n)O(n)O(n)

最坏情况（所有键冲突）会退化为 O(n)