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

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行业 的聚集地。"