【哈希冲突解决】线性探测再散列和二次探测再散列_线性探测再散列二次探测再散列

作者：小小林熬夜学编程 | 2024-06-03 09:06:10

踩

线性探测再散列二次探测再散列

定义

散列（Hashing）是计算机科学中一种对资料的处理方法，通过某种特定的函数/算法（称为散列函数/算法）将要检索的项与用来检索的索引（称为散列，或者散列值）关联起来，生成一种便于搜索的数据结构（称为散列表）。二次再散列法是指第一次散列产生哈希地址冲突，为了解决冲突，采用另外的散列函数或者对冲突结果进行处理的方法。

算法公式

线性探测法
f(key) = (f(key)+di) MOD m (di=1,2,3,......,m-1)
二次探测法
f(key) = (f(key)+di) MOD m (di = 1^2, -1^2, 2^2, -2^2,……, q^2, -q^2, q <= m/2)

实例

线性探测再散列

例如：哈希函数为： H（key） = key %11,key 为关键字，采用开放地址法中的线性探测再散列解决冲突，依次输入

9 个关键字，19，01，23，14，55，68，11，82，36，构造哈希表（表长=11）

散列地址	0	1	2	3	4	5

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/666574