通过哈希函数将键映射到数组的索引,使用链表处理哈希冲突。提供近乎O(1)的查找、插入和删除操作。
哈希表(Hash Table)是一种高效的数据结构,能够实现快速的插入、查找和删除操作。链地址法(Chaining)是解决哈希冲突的一种常用方法,它通过为每个哈希桶维护一个链表,将具有相同哈希值的元素存储在同一链表中,从而有效处理冲突问题。
哈希表(Hash Table)是一种基于哈希函数直接访问元素的数据结构,理解它需要先掌握几个关键概念:
哈希函数(Hash Function):将输入数据(通常是无限范围)映射到有限范围(哈希表大小)的函数。一个好的哈希函数应该能够均匀分布元素,最小化冲突。
哈希值(Hash Value):哈希函数的输出结果,用作哈希表中的索引。
哈希桶(Bucket):哈希表中存储元素的位置,每个桶对应一个哈希值。
哈希冲突(Hash Collision):当两个不同的输入通过哈希函数产生相同的哈希值时发生冲突。由于哈希表空间有限而可能的输入数据无限,冲突不可避免。
链地址法(Chaining):解决哈希冲突的一种方法,其基本思想是:
哈希表的负载因子(Load Factor):表中元素数量与哈希表大小的比值。当负载因子增大时,链表长度可能增加,导致性能下降。
示例:
假设有一个大小为 7 的哈希表,使用简单的哈希函数 h(k) = k % 7,现在需要插入键值对:(10, "苹果")、(21, "香蕉")、(32, "橙子")、(17, "葡萄")。
计算哈希值:
最终哈希表结构为:
▼Plain复制代码0: → (21, "香蕉") → null 1: → null 2: → null 3: → (10, "苹果") → (17, "葡萄") → null 4: → (32, "橙子") → null 5: → null 6: → null
可以看到索引 3 处有两个元素,这是因为 10 和 17 发生了哈希冲突,它们通过链表连接在一起。
在大多数语言中都有哈希表的实现,比如 Java 中的 HashMap、Python 中的 dict 和 collections.defaultdict、JavaScript 中的 Object 和 Map、Go 中的 map 以及 C++ 中的 std::unordered_map,这些内置实现已经高度优化,能够有效处理哈希冲突并提供稳定的性能,所以这里不再提供自定义实现。
优点:
缺点:
传统链地址法使用普通链表存储冲突元素,但可以通过替换链表结构提升性能:
测验答案
- 负载因子为 2 表示哈希表中的元素数量是哈希表大小的两倍,平均每个桶包含 2 个元素。这意味着哈希冲突较多,查找时平均需要比较的元素变多。查找的期望时间复杂度为 O(1 + α),负载因子 α = 2 时仍是常数级,但比负载因子较小时慢,所以通常会在负载因子超过阈值时扩容。
- 哈希表结构如下:
- 桶 2: → (12, value) → (22, value) → (32, value) → (42, value) → (52, value) → null
- 其他桶 (0,1,3-9): → null
所有元素都被映射到索引 2 上,形成了一个长链表。- 最坏时间复杂度是 O(n),n 是哈希表中的元素总数。在最坏情况下,所有元素都被哈希到同一个桶中,形成一个长链表,需要遍历整个链表才能确定元素不存在。