你认为最优美的数据结构是什么?

如题。
关注者
5950
被浏览
329724

前置技能:您需要确认自己知道trie是干什么的;

您需要确认自己会用vector或者之类的容器来实现trie。


我觉得最优美的数据结构是并查集和线段树。然而已经被别的答主说过了,我谈谈几年前看到的一个东西:哈希树(hashTree)。


以下讨论膜质数的hash方式。


hash的冲突

众所周知,hash是有冲突的。随着表中元素变多,冲突的概率快速增大。

(有个结论:取 \sqrt n[1,n] 中的随机数,就期望有一个值被取了多遍。因此,元素越来越多,冲突的概率增长得相当快。)

举个例子:假设我们的哈希函数是 h(x) = x \% 17 ,那么h(19)=2,h(36)也是2。我们称这种情况为冲突——假设我们加入了19,hash表里面存下了19的哈希值为2。后来,面对查询“36是否存在”的时候,hash表查到36的哈希值是2,就会毫不犹豫地回答“存在”——这样就出错了。


为了解决hash冲突的问题,我们一般使用两种方法:“拉链法”和“跳跃法”。


拉链法:简单粗暴,给每一个hash值开一个链表,存下真实值。空间是可保证的,具体开链表的方法参考邻接表(或者,“前向星”)。

这个方法的漏洞在于:时间复杂度将无法得到保证。还是刚刚的哈希函数,我们存下19,36,53,70……这样,时间复杂度直接被卡到 O(n) 每次查询

那么有没有办法解决上述问题呢?把链表改成跳表(或者其他平衡树,或者直接std::set),这样时间复杂度就稳定在 O(\log n) .但是需要付出较大的常数。


跳跃法:又称“线性探查法”。也是存下真实值,不同的是,我们求出hash值之后,如果发现那个hash值已经有元素了,我们就往后面跳k位……如此往复,直到出现空位为止。

这个算法的复杂度非常不靠谱,我也没想到解决办法。


综上:我们能做 时间复杂度稳定在 O(\log n) 的hash,但是需要付出很大的常数代价。


哈希树

哈希树的思想是:膜多个质数

也许您看到这么简单的思路,会D我:这就是你的垃圾解决方案?

然而事实是,简单的思想后面,隐藏着极为深刻的数学背景。


我们搞前几个质数出来,然后每插入一个元素,就对这些质数分别取模。

是不是要开高维数组呢?不。我们用trie的方式。(这也是“哈希树”名字的由来)


如图。假设我们只取前三个质数。我们拿到28,膜2为0,膜3为1,膜5为3。因此hash(28)=(0,1,3).我们把28存到上面的trie中去。

最后的效果:最底下那个“3”打上“此座已占”标记。


假设我们用了前k个质数,那么时间复杂度是显然的,只需要取膜k次,每次铁定 O(k) .

空间复杂度呢?由于我们是用trie来实现的,因此对于每一个元素,最多需要开 2+3+5+\cdots p_k 个节点的空间,当k取8的时候,这个值为77。

甚至我们可以开更少的空间——把trie用“兄弟-儿子存法”实现。这是后话。总之空间占用很低。


正确性呢?通过中国剩余定理知道,我们只需要取前8个质数,就能保证约一千万以内的数都不会出现冲突。更强的结论是,可以保证元素在连续9699690个数的值域内,不会产生碰撞。



算是令人拍案叫绝的数据结构吧。而且非常好写。