#本科生推翻姚期智40年前的猜想#
【本科生推翻姚期智40年前的猜想，提出全新哈希表算法突破搜索效率极限】
哈希表（hash table）是 #计算机科学# 中最基础也最重要的数据结构之一，它的历史可以追溯到 20 世纪 50 年代早期。哈希表的核心思想是通过一个哈希函数，将任意范围的键值映射到一个固定大小的数组空间中。
这种数据结构就像一个巨大的抽屉柜，每个数据都可以被迅速放入某个抽屉中，并在需要时快速取出。但当抽屉柜接近装满时，找到合适的空抽屉就变得越来越困难。
也就是说，当一个哈希表接近装满时（比如说已经占用了 99% 的空间），要在剩余空间中找到一个空位至少需要进行与填充率成正比的次数搜索。这就意味着，如果哈希表已经 99% 满了，那么在最坏情况下，需要大约 100 次尝试才能找到一个空位。
这个理论限制就像物理学中的光速极限一样，被认为是不可逾越的。1985 年， #图灵奖# 得主姚期智在其具有里程碑意义的论文 Uniform Hashing is Optimal 中提出在具有特定属性的哈希表中，随机选择抽屉的方法，即均匀探测（uniform probing）是最优的选择。
戳链接查看详情：
网页链接
哈希表（hash table）是 #计算机科学# 中最基础也最重要的数据结构之一，它的历史可以追溯到 20 世纪 50 年代早期。哈希表的核心思想是通过一个哈希函数，将任意范围的键值映射到一个固定大小的数组空间中。
这种数据结构就像一个巨大的抽屉柜，每个数据都可以被迅速放入某个抽屉中，并在需要时快速取出。但当抽屉柜接近装满时，找到合适的空抽屉就变得越来越困难。
也就是说，当一个哈希表接近装满时（比如说已经占用了 99% 的空间），要在剩余空间中找到一个空位至少需要进行与填充率成正比的次数搜索。这就意味着，如果哈希表已经 99% 满了，那么在最坏情况下，需要大约 100 次尝试才能找到一个空位。
这个理论限制就像物理学中的光速极限一样，被认为是不可逾越的。1985 年， #图灵奖# 得主姚期智在其具有里程碑意义的论文 Uniform Hashing is Optimal 中提出在具有特定属性的哈希表中，随机选择抽屉的方法，即均匀探测（uniform probing）是最优的选择。
戳链接查看详情：
网页链接
