哈希函数

哈希函数用于索引原始值或键，并在以后每次检索与该值或键关联的数据时使用。因此，哈希始终是单向操作。无需通过分析哈希值来“逆向工程”哈希函数。

良好哈希函数的特点

1. 哈希值完全由要哈希的数据决定。
2. 哈希函数使用所有输入数据。
3. 哈希函数在整个可能的哈希值集合中“均匀地”分布数据。
4. 哈希函数为相似的字符串生成复杂的哈希值。

一些流行的哈希函数是

1. 除法法

选择一个小于 k 中键的数量 n 的数字 m（数字 m 通常选择为素数或没有小除数的数字，因为这通常是最小的冲突数）。

哈希函数是

例如：如果哈希表的大小为 m = 12，键为 k = 100，则 h (k) = 4。由于它只需要单个除法运算，因此通过除法进行哈希非常快。

2. 乘法方法

用于创建哈希函数的乘法方法分两步进行。首先，我们将键 k 乘以范围 0 < A < 1 中的常数 A，并提取 kA 的小数部分。然后，我们将该值增加 m 并取结果的底数。

哈希函数是

其中“k A mod 1”表示 k A 的小数部分，即 k A -⌊k A⌋。

3. 平方取中法

键 k 平方。然后函数 H 定义为

其中 L 是通过从 k² 的两端删除数字获得的。我们强调必须对所有键使用 k² 的相同位置。

4. 折叠法

键 k 被划分为多个部分 k₁, k₂.... k_n，其中每个部分（可能除了最后一个部分）具有与所需地址相同数量的数字。

然后将这些部分加在一起，忽略最后的进位。

H (k) = k1+ k2+.....+kn

示例：公司有 68 名员工，每位员工都分配了一个唯一的四位数员工号码。假设 L 由 2 位地址组成：00、01 和 02....99。我们将上述哈希函数应用于以下每个员工号码

(a) 除法: 选择一个接近 99 的素数 m，例如 m =97，然后

即，将 3205 除以 17 得到余数 4，将 7148 除以 97 得到余数 67，将 2345 除以 97 得到余数 17。

(b) 平方取中法

k = 3205       7148       2345
k2= 10272025   51093904   5499025
h (k) = 72     93         99

请注意，从右侧开始计数，选择第四位和第五位作为哈希地址。

(c) 折叠法：将键 k 分成 2 部分，相加得到以下哈希地址