HASH 算法的缺陷

首先,我们所了解到的所有简单的复杂的 HASH 函数总会拥有一些薄弱点,即输入一些特殊的 key 会很容易返回相同 KEY 导致多条数据插入到同一个槽中,这直接影响了 HASH Table 的效率。特别是一些超高使用频率的哈希表,这将成为性能的最大缺陷与短板。

全域哈希

其实我们应该能想到其中一种解决方案,加入随机特性,即在一些 HASH 算法的集合中随机挑选一个作为 HASH 算法,这样就能很大程度上避免一组特殊的 key 导致彻底爆炸的问题。

但是,在算法导论里其实并没有讲到插入成功后如何去搜索他,我一想这都随机了你该如何去找到那个 HASH 函数呢,有网友说是随机出一个函数接下来插入,搜索用的都是这个,不会去随机出新的了,我觉得应该还是很正确的,因为一直随机其实很浪费算力,应该是一次随机,接下来都使用这个。

另外这数学证明太恐怖了,完全看不懂!

完全哈希 (Perfect Hash)

完全哈希其实就是全域哈希的增强版,他在全域哈希的基础之上增加了一种二次嵌套的哈希表结构,也就是说一个一级哈希表中的槽指向一个二级哈希表,而二级哈希表的长度通常是 n^2,也就是说二级哈希表通常是非常稀疏的,他的平均碰撞已经降到了 1 以下,虽然比较浪费空间,但是获得了最差情况 O(1)的效率,对于一些静态的哈希表,这是一种非常好的方法。