尚学堂,代码之美,这些最优美的数据结构,让你爱上编程

hash的冲突

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

拉链法:简单粗暴,给每一个hash值开一个链表,存下真实值。空间是可保证的,具体开链表的方法参考邻接表(或者,“前向星”)。这个方法的漏洞在于:时间复杂度将无法得到保证。还是刚刚的哈希函数,我们存下19,36,53,70……这样,时间复杂度直接被卡到 每次查询。那么有没有办法解决上述问题呢?把链表改成跳表(或者其他平衡树,或者直接std::set),这样时间复杂度就稳定在 .但是需要付出较大的常数。

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

并查集一段让人心跳加速的描述:"一般采取树形结构来存储并查集,并利用一个rank数组来存储集合的深度下界,在查找操作时进行路径压缩使后续的查找操作加速。这样优化实现的并查集,空间复杂度为O(N),建立一个集合的时间复杂度为O(1),N次合并M查找的时间复杂度为O(M Alpha(N)),这里Alpha是Ackerman函数的某个反函数,在很大的范围内(人类目前观测到的宇宙范围估算有10的80次方个原子,这小于前面所说的范围)这个函数的值可以看成是不大于4的,所以并查集的操作可以看作是线性的"

更多科技一手咨询,欢迎关注!

“我们相信人人都可以成为一个IT大神,现在开始,选择一条阳光大道,助你入门,学习的路上不再迷茫。这里是北京尚学堂,初学者转行到IT行业 的聚集地。"

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190819A0727L00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券