哈希表 - O(1)的魔法让查找无需比较072开放寻址哈希表即时查找的魔法 5W1H 发明者故事Who何人- 发明者是谁发明者汉斯·彼得·卢恩Hans Peter Luhn1896-1964IBM研究工程师背景卢恩是德裔美国人他更广为人知的发明是信用卡校验码Luhn算法1954年至今每次你刷卡都在用他的算法。他在IBM工作期间于1953年提出了将数据键映射到内存地址的哈希思想——当时他称之为计算寻址computed addressing。其他独立发明者阿诺德·达姆Arnold Dumey1956年发表了第一篇学术论文韦斯利·彼得森Wesley Peterson1957年研究了开放寻址和线性探测克努斯在TAOCP中系统化了整个理论当时的处境1953年计算机存储昂贵IBM的大型机用磁鼓drum存储数据。每次查找都要按顺序检索既慢又占用处理器时间。卢恩的洞察是与其搜索不如直接计算出目标在哪里。When何时- 什么时候发明的时间1953年卢恩的内部备忘录1957年彼得森学术论文详细分析线性探测时代背景IBM 7011952年和7041954年商用大型机投入使用内存很贵每个字节都宝贵减少查找时间是硬需求汇编语言时代程序员直接操作内存地址Where何地- 在哪里发明的地点IBM 圣何塞研究实验室San Jose Research Laboratory环境战后美国工业界的黄金时期IBM几乎垄断计算机市场研究投入充裕。What何事- 发明了什么数据结构哈希表Hash Table核心思想哈希函数将键key映射到数组下标index hash(key) % capacity直接存取通过计算出的下标直接存储/访问数据无需比较冲突处理多个键映射到同一下标时的解决方案链式法/开放寻址哈希名字的由来hash在英语中意为切碎混合——就像把键打碎成一个数字下标。两种主要冲突解决方案链式法Chaining同一下标的元素用链表连接开放寻址Open Addressing冲突时探测下一个空槽线性探测、二次探测、双重哈希Why何因- 为什么发明问题二分查找需要O(log n)数据库查找需要O(1)。洞察如果我们知道一本词典的目标词在哪一页就可以直接翻到那页——不需要逐页翻。哈希函数就是直接计算出目标在哪里的魔法。代价需要额外空间负载因子1且哈希冲突增加了复杂性。How何果- 如何实现有什么影响负载因子Load Factor n/mn为元素数m为槽数 0.5冲突少快但浪费空间0.7-0.8工程上常用的平衡点0.9冲突急剧增多性能劣化历史影响Python的dict字典是哈希表是语言核心Java的HashMapGo的mapC的unordered_map数据库的索引结构哈希索引编译器的符号表缓存系统Redis, Memcached的核心数据结构克努斦在TAOCP第三卷6.4节提供了完整的数学分析 自然语言需求定义需求名称实现开放寻址哈希表线性探测惰性删除支持整数键值对功能需求创建指定初始容量内部取下一个质数分配内存插入/更新hash(key)定位线性探测找空槽已存在则更新值查找同样的探测序列遇EMPTY停止遇DELETED继续删除惰性删除标记DELETED不物理移除防止断开探测链负载因子监控超过0.7时发出警告约束条件容量用质数减少哈希冲突三种槽状态EMPTY从未用、OCCUPIED有数据、DELETED已删除惰性删除物理删除会断开线性探测链导致查找失败验收标准编号测试场景预期结果验证方式1插入(10,100),(20,200),(30,300)大小为3size检查2查找存在的键返回对应值三个键全部查找3查找不存在的键(99)返回false检查返回值4更新已有键(10, 999)值变为999大小不变查找验证5删除key20后查找返回false惰性删除6删除后插入DELETED槽复用成功插入查找新键7哈希碰撞3个键mod capacity相同全部可查三键查找 C语言实现文件对应文件:hash_table.c编译运行:gcc-ohash_table_test hash_table.c ./hash_table_test核心函数:ht_create(capacity)- 创建哈希表ht_insert(ht, key, value)- 插入/更新ht_get(ht, key, value)- 查找ht_delete(ht, key)- 惰性删除ht_free(ht)- 释放内存