关于再散列和双散列
为什么会产生对再散列和双散列的混淆嘞?
来看10年408真题:
此处的 “线性探测再散列法” 指的是什么?
依据答案,“线性探测再散列法”主要指的是“线性探测法(linear probing)”,后面的“再散列法”可能就是字面意思,即 “第一次散列因发生冲突而再次散列”。确实略有不严谨,不过也不必太钻牛角尖。
那么“再散列”和“双散列”是一个东西吗?
当然不是,王道数据结构单科书22版曾混淆了再散列和双散列,不过在23版数据结构单科书中已订正。(下图左侧为22版右侧为23版)
双散列(double hashing)指的是有两个散列函数,定义见下图:
而再散列指的是建立另外一个大约两倍大的表(使用一个相关的新散列函数),扫描整个原始散列表,计算每个元素的新散列值并将其插入到新表中。(此处参考https://blog.csdn.net/PacosonSWJTU/article/details/49454757)
ps:以上图片除真题与王道单科书外均来自《算法导论 原书第三版》
标签:双散列,再散,单科,列法,关于,线性,散列 From: https://www.cnblogs.com/AncilunKiang/p/17036712.html