散列函数和散列函数的列表/类型
原文:https://www . geesforgeks . org/hash-functions-and-list-type-of-hash-functions/
散列是使用称为散列函数的数学函数从文本或数字列表中生成值的过程。
一个散列函数是一个将给定的数字或字母数字键转换成一个小的实际整数值的函数。映射的整数值用作哈希表中的索引。简单来说，哈希函数将一个有效数字或字符串映射到一个小整数，该小整数可以用作哈希表中的索引。
这两个键的形式是(键，值)，对于给定的键，可以使用某种将键映射到值的“函数”来找到值。给定对象的密钥可以使用称为哈希函数的函数来计算。例如，给定一个数组 A，如果 I 是键，那么我们可以通过简单地查找 A[i]来找到值。
哈希函数的类型
有许多使用数字键或字母数字键的散列函数。本文重点讨论不同的哈希函数:
- 除法。
- 中方格法。
- 折叠法。
- 乘法。
让我们开始详细讨论这些方法。
1。划分方法:
这是生成哈希值最简单、最容易的方法。散列函数将值 k 除以 M，然后使用得到的余数。
公式:
h(K) = k mod M
这里， k 是键值， M 是哈希表的大小。
最适合的是 M 是一个质数，这样可以保证按键分布更加均匀。散列函数依赖于除法的余数。
示例:
k = 12345 m = 95 h(12345)= 12345 mod 95 = 90
k = 1276 m = 11 h(1276)= 1276 mod 11
优点:
- 这种方法对 m 的任何值都相当好。
- 除法方法非常快，因为它只需要一次除法运算。
cons:t1]
- 由于连续键映射到哈希表中的连续哈希值，因此这种方法会导致较差的性能。
- 有时要格外注意选择 m 的值。
2。中方格法:T3
中间平方法是一种非常好的散列法。计算哈希值需要两个步骤
- 将密钥 k 的值平方，即 k 2
- 提取中间的 r 位作为哈希值。
公式:
h(K)= h(K×K)
这里， k 是关键值。
r 的值可以根据表格的大小来决定。
示例:
假设哈希表有 100 个内存位置。所以 r = 2，因为需要两位数来将密钥映射到内存位置。
k = 60 k x k = 60 x 60 = 3600 h(60)= 60
获得的哈希值是 60
优点:
- 该方法的性能很好，因为键值的大部分或所有数字都对结果有贡献。这是因为密钥中的所有数字都有助于生成平方结果的中间数字。
- 结果不受原始键值的顶部数字或底部数字的分布支配。
cons:t1]
- 密钥的大小是这种方法的限制之一，因为密钥的大小很大，那么它的平方将是位数的两倍。
- 另一个缺点是会有碰撞，但我们可以尝试减少碰撞。
3。数字折叠法:
该方法包括两个步骤:
- 将键值 k 分成若干部分，即 k1、k2、k3、…。，kn ，其中除了最后一个部分的位数比其他部分少之外，每个部分的位数相同。
- 添加单个零件。哈希值是通过忽略最后一个进位(如果有)获得的。
公式:
k = k1，k2，k3，k4，…..，kn T3】s = k1+k2+k3+k4+…。+knT5h(K)= s
这里 s 是通过添加钥匙 k 的零件获得的
示例:
k = 12345 k1 = 12，k2 = 34，k3 = 5 s = k1+k2+k3 = 12+34+5 = 51 h(K)= 51
注意: 每个部分的位数根据哈希表的大小而变化。例如，假设哈希表的大小为 100，那么除了最后一部分可以有较少的位数之外，每个部分都必须有两位数。
4。乘法
该方法包括以下步骤:
- 选择常数值 A，使 0 < A < 1。
- 将键值乘以 a。
- 提取 kA 的小数部分。
- 将上述步骤的结果乘以散列表的大小，即 m
- 得到的哈希值是通过取步骤 4 中得到的结果的地板而得到的。
公式:
h(K) =楼板(M (kA mod 1))
这里， M 就是哈希表的大小。 k 是关键值。 A 为常数值。
示例:
k = 12345 A = 0.357840 M = 100
h(12345) =楼层【100(12345 * 0.357840 mod 1)】 =楼层【100(4417.5348 mod 1)】 =楼层【100(0.5348)】 =楼层【53.48】 = 53
优点:
乘法的优点是，它可以处理 0 到 1 之间的任何值，尽管有些值往往比其他值给出更好的结果。
cons:t1]
当表的大小是 2 的幂时，乘法方法一般是适用的，那么使用乘法哈希的键计算索引的整个过程是非常快的。
版权属于：月萌API www.moonapi.com，转载请注明出处
