javascript 数据结构系列 (六) 哈希表

哈希表（Hash Table）是一种高效的数据结构，通过键值对存储数据，利用哈希函数将键映射到存储位置，实现快速的数据插入、删除和查找。

核心实现解析1. 构造函数constructor(hashTableSize = defaultHashTableSize) { this.buckets = Array(hashTableSize).fill(null).map(() => new LinkedList()); this.keys = {};}

buckets：使用数组存储链表，每个链表对应一个哈希桶，解决哈希冲突（通过链地址法）。
keys：对象用于快速记录所有实际存在的键，辅助判断键是否存在。

2. 哈希函数hash(key) { const hash = Array.from(key).reduce( (acc, char) => acc + char.charCodeAt(0), 0 ); return hash % this.buckets.length;}

功能：将字符串键转换为哈希值。
实现：
计算键的字符编码总和（简单方法，易冲突）。
通过取模运算将哈希值映射到桶的索引范围。
优化建议：使用更复杂的哈希算法（如多项式滚动哈希）减少冲突。

3. 核心方法set(key, value)set(key, value) { const keyHash = this.hash(key); this.keys[key] = keyHash; // 记录键 const bucket = this.buckets[keyHash]; const node = bucket.find({ callback: (node) => node.key === key }); if (!node) { bucket.append({ key, value }); // 插入新节点 } else { node.value.value = value; // 更新现有节点 }}

流程：
计算键的哈希值，定位到桶。
若键不存在，插入新节点；否则更新值。

get(key)get(key) { const bucket = this.buckets[this.hash(key)]; const node = bucket.find({ callback: (node) => node.key === key }); return node ? node.value.value : undefined;}

流程：
定位到桶后查找键对应的节点。
返回节点的值或undefined（键不存在）。

delete(key)delete(key) { const keyHash = this.hash(key); delete this.keys[key]; // 移除键记录 const bucket = this.buckets[keyHash]; const node = bucket.find({ callback: (node) => node.key === key }); return node ? bucket.delete(node.value) : null;}

流程：
从keys中删除键记录。
定位到桶后删除对应节点，返回删除的值或null。

has(key)has(key) { return Object.hasOwnProperty.call(this.keys, key);}

功能：检查键是否存在，直接查询keys对象。

getKeys()getKeys() { return Object.keys(this.keys);}

功能：返回所有键的数组，基于keys对象。

关键点总结

冲突处理：采用链地址法（每个桶是链表），避免哈希冲突导致数据覆盖。
性能优化：
哈希函数：简单求和易冲突，实际应用中需改进。
快速键查询：通过keys对象实现O(1)时间复杂度的存在性检查。
时间复杂度：
理想情况：O(1)（哈希函数均匀分布）。
最坏情况：O(n)（所有键冲突到同一桶，链表退化为线性查找）。

扩展建议

动态扩容：当负载因子（元素数/桶数）超过阈值时，重新哈希并扩大桶数组。
更优哈希算法：如MurmurHash、FNV等，减少冲突概率。
迭代器支持：实现values()、entries()等方法，增强实用性。

通过上述实现，哈希表在大多数场景下能高效处理键值对操作，适合需要快速查找的场景（如缓存、字典等）。

您可能感兴趣问答

Collapsible

热门标签

热点问答