线性探测再散列法是什么？

Question

如题所述

Answer 1

当di值可能为1,2,3,...m-1，称线性探测再散列。

具体如下：

开放地址法有一个公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1）。

其中，m为哈希表的表长。di是产生冲突的时候的增量序列。如果di值可能为1,2,3,...m-1，称线性探测再散列。

如果di取1，则每次冲突之后，向后移动1个位置。如果di取值可能为1,-1,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2），称二次探测再散列，如果di取值可能为伪随机数列。称伪随机探测再散列。

散列表（Hash table，也叫哈希表），是根据关键码值（Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希（Hash)函数。