数据库管理系统中有哪些不同的哈希方法？

哈希文件组织也称为直接文件组织。

在这种方法中，为了存储记录，会计算一个哈希函数，该函数提供存储记录的块地址。任何类型的数学函数都可以用作哈希函数。它可以很简单，也可以很复杂。

哈希函数应用于列或属性以获取块地址。记录是随机存储的。因此，它也称为直接或随机文件组织。

如果生成的哈希函数作用于被认为是键的列，则该列可以称为哈希键；如果生成的哈希函数作用于被认为是非键的列，则该列可以称为哈希列。

假设一个文件有n条记录，每条记录都有一个唯一确定该记录的键。设K为键，L为内存位置。哈希函数定义为H: K->L

示例

下面是一个哈希文件组织的示例：

0
1
2011 德里
3
4022 加尔各答
5
6033 金奈
7
8044 孟买
9

这里城市的区号是键。哈希函数通过简单地将键的数字相加，将这些键映射到地址2,4,6,8。

哈希函数的方法

哈希函数H(k)的方法解释如下：

  • 除法法

哈希函数H(k)=k (mod m)，其中m是一个大于键数量的素数。

示例

假设有76名学生，每个学生都有一个唯一的10位学号。这里的学号是键。

m=79（大于76）

L包含100个内存位置00,01,02,…,99

对于学号0148105102、0148105124、0148105405，H(k)如下所示：

H(0148105102) = 0148105102 % 79 = 10
H(0148105124) = 0148105124 % 79 = 32
H(0148105405) = 0148105405 % 79 = 76
  • 中间平方法

对键k进行平方，然后通过取中间数字来获得地址。

示例

假设有200名员工，每个员工都有一个唯一的3位员工ID。这里，员工ID是键。

H(k) = 2nd and 3rd digit of k2
K: 067 048 146
K2: 4489 2304 21316
H(k): 48 30 13
  • 折叠法

将键分成k1、k2、……kn几部分，然后将这些部分加在一起，忽略进位，即H(k) = k1+ k2+ ……..+ kn

示例

假设有2000名员工，每个员工都有一个唯一的4位员工ID。这里，员工ID是键。

H(1643) =16+43 =57
H(1999) =19+99 = 18 (The leading digit 1 is ignored)
H(1176) = 11 + 76 = 87
H( 1374) = 13+ 74 =87

当多个键引用同一个内存位置时，这个问题称为冲突。

更新于：2021年7月8日

319 次查看

启动您的职业生涯

完成课程获得认证

开始学习
广告