哈希表
概述
哈希表（Hash Table） 是一种基于键值对（key-value）存储的高效数据结构，通过哈希函数将键映射到存储位置， 实现平均时间复杂度 的插入、删除和查找操作。
以 key-value 形式存储数据，是指任意的键值 key 都唯一对应到内存中的某个位置。 只需要输入查找的键值，就可以快速地找到其对应的 value。 可以把哈希表理解为一种高级的数组，这种数组的下标可以是很大的整数，浮点数，字符串甚至结构体。
核心特性
哈希函数 (Hash Function)
将任意大小的数据（键）映射到固定大小的值（哈希值）。
要让键值对应到内存中的位置，就要为键值计算索引，也就是计算这个数据应该放到哪里。 这个根据键值计算索引的函数就叫做哈希函数，也称散列函数。
举个例子，如果键值是一个人的身份证号码，哈希函数就可以是号码的后四位，当然也可以是号码的前四位。 生活中常用的「手机尾号」也是一种哈希函数。 在实际的应用中，键值可能是更复杂的东西，比如浮点数、字符串、结构体等，这时候就要根据具体情况设计合适的哈希函数。 哈希函数应当易于计算，并且尽量使计算出来的索引均匀分布。
对于 哈希函数，应该满足以下要求：
- 一致性：相同的键总是产生相同的哈希值。
- 高效性：计算速度快。
- 均匀性：尽可能均匀地分布哈希值，以减少冲突。
冲突解决 (Collision Resolution)
如果对于任意的键值，哈希函数计算出来的索引都不相同，那只用根据索引把 放到对应的位置就行了。 但实际上，常常会出现两个不同的键值，他们用哈希函数计算出来的索引是相同的。这时候就需要一些方法来处理冲突。
常见的冲突解决方法包括:
开散列法（Open hashing）：也称 拉链法，在每个存放数据的地方开一个链表，如果有多个键值索引到同一个地方， 只用把他们都放到那个位置的链表里就行了。 查询的时候需要把对应位置的链表整个扫一遍，对其中的每个数据比较其键值与查询的键值是否一致。
如果索引的范围是 ，哈希表的大小为 ，那么一次 插入/查询 需要进行期望 次比较。
闭散列法（Closed hashing）：把所有记录直接存储在散列表中，如果发生冲突则根据某种方式继续进行探查。
比如线性探查法：如果在
d处发生冲突，就依次检查d + 1，d + 2……
动态扩容 (Rehashing)
当负载因子（元素数/桶数）超过阈值（如 0.75）时，扩容并重新哈希所有元素。
哈希表的实现
type Bucket<K, V> = Array<[K, V]> // 桶结构：存储键值对元组的数组
class HashTable<K, V> {
private buckets: Array<Bucket<K, V>>
private capacity: number
private size: number
private loadFactor: number = 0.75
constructor(initialCapacity: number = 16) {
this.capacity = initialCapacity
this.size = 0
this.buckets = Array.from({ length: initialCapacity }, () => [])
}
// 哈希函数（简化版，实际需更健壮）
private hash(key: K): number {
const keyString = String(key)
let hash = 0
for (let i = 0; i < keyString.length; i++) {
hash = (hash << 5) + keyString.charCodeAt(i)
hash = hash & hash // 转为32位整数
hash = Math.abs(hash)
}
return hash % this.capacity
}
// 插入/更新键值对
put(key: K, value: V): void {
const index = this.hash(key)
const bucket = this.buckets[index]
// 检查是否已存在相同key
for (const pair of bucket) {
if (pair[0] === key) {
pair[1] = value // 更新值
return
}
}
// 新增键值对
bucket.push([key, value])
this.size++
// 检查扩容
if (this.size / this.capacity > this.loadFactor) {
this.resize()
}
}
// 获取值
get(key: K): V | undefined {
const index = this.hash(key)
const bucket = this.buckets[index]
for (const [k, v] of bucket) {
if (k === key)
return v
}
return undefined
}
// 删除键值对
remove(key: K): boolean {
const index = this.hash(key)
const bucket = this.buckets[index]
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket.splice(i, 1)
this.size--
return true
}
}
return false
}
// 动态扩容
private resize(): void {
const oldBuckets = this.buckets
this.capacity *= 2
this.buckets = Array.from({ length: this.capacity }, () => [])
this.size = 0
// 重新哈希所有元素
for (const bucket of oldBuckets) {
for (const [key, value] of bucket) {
this.put(key, value) // 插入到新桶
}
}
}
// 当前元素数量
getSize(): number {
return this.size
}
}时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| put() | 平均 ，最坏 | 哈希计算 + 桶内线性扫描 |
| get() | 平均 ，最坏 | 桶内线性查找 |
| remove() | 平均 ，最坏 | 桶内查找后删除 |
| resize() | 所有元素重新哈希 |
适用场景
- 高频插入/删除且需快速查找
- 缓存实现（如 LRU Cache）
- 数据库索引
- 字典类应用（词频统计）