哈希表

哈希表通过使用哈希函数将键映射到数组位置来实现字典，当冲突得到良好管理时，支持预期的常数时间插入、删除和查找。

Definition

哈希表是一种数据结构，它使用哈希函数将每个键计算为数组索引，并采用冲突解决机制来处理哈希到相同索引的不同键，从而在数组中存储键值对。

Scope

本主题涵盖基于哈希的字典：哈希函数及其理想属性、冲突解决策略（独立链表法和开放寻址法）、负载因子和重新调整大小、提供可证明保证的通用哈希和完美哈希框架，以及相关的概率结构，如布隆过滤器。它不包括有序字典结构，这些结构在搜索树中介绍。

Core questions

• 什么使哈希函数表现良好，以及如何选择它以均匀分布键？
• 如何通过链表法或开放寻址法解决冲突，以及它们如何影响成本？
• 负载因子如何控制预期的操作时间并触发重新调整大小？
• 通用哈希和完美哈希如何提供可证明的性能保证？
• 在什么情况下，像布隆过滤器这样节省空间的概率结构优于精确表？

Key concepts

• 哈希函数
• 独立链表法
• 开放寻址法
• 负载因子
• 重新哈希和调整大小
• 通用哈希
• 完美哈希
• 布隆过滤器

Key theories

通用哈希

通过从精心设计的（通用）族中随机选择哈希函数，可以保证任何固定键集的预期冲突数量较低，从而使最坏情况的对抗性输入变得不太可能。

冲突解决和负载因子

独立链表法将冲突的键存储在每个槽的列表中，而开放寻址法探测备用槽；预期的操作时间由负载因子（每个槽的条目数）决定，并且表会调整大小以使其保持在限定范围内。

Clinical relevance

哈希表是计算机中最常用的数据结构之一：它们在标准库中实现字典和集合，为数据库索引和内存缓存提供支持，在编译器中支持符号表，并作为去重和成员测试的基础。布隆过滤器在数据库和网络中扩展成员查询，在这些场景中精确存储是不可行的。

History

哈希技术起源于20世纪50年代，其工作归功于IBM的汉斯·彼得·卢恩（Hans Peter Luhn）。伯顿·布隆（Burton Bloom）于1970年引入了节省空间的布隆过滤器。卡特（Carter）和韦格曼（Wegman）在20世纪70年代末和80年代初形式化了通用哈希，后来又提出了强通用哈希，为哈希技术奠定了严谨的理论基础。

Key figures

• Hans Peter Luhn
• J. Lawrence Carter
• Mark Wegman
• Burton H. Bloom

Seminal works

• bloom1970
• carter1981
• cormen2009

Frequently asked questions

为什么哈希表操作被描述为预期O(1)而不是保证O(1)？

如果许多键发生冲突，操作可能会退化到O(n)。在良好的哈希函数和有界负载因子下，常数时间是预期的；通用哈希使不良情况不太可能发生，但最坏情况的保证需要完美哈希或其他技术。

什么是布隆过滤器，它与哈希表有何不同？

布隆过滤器是一种紧凑的概率结构，它使用多个哈希函数在位数组上测试集合成员资格。它可能产生假阳性但从不产生假阴性，并且不存储任何键，与哈希表相比，它以牺牲精确性换取了巨大的空间节省。