散列概念


介绍

哈希文件组织方法是一种将数据存储在其地址是通过使用哈希函数生成的数据块中的方法。 这些记录的存储位置称为数据块或数据桶。 此数据存储区能够存储一个或多个记录。

哈希函数可以使用任何列值来生成地址。 大多数时候,哈希函数使用主键生成哈希索引-数据块的地址。 哈希函数可以是简单的数学函数,也可以是任何复杂的数学函数。 我们甚至可以将主键本身视为数据块的地址。 这意味着每一行将存储在地址与主​​键相同的数据块中。 这意味着哈希函数在数据库中可以多么简单。

上图描述了与主键值相同的数据块地址。 该哈希函数也可以是简单的数学函数,例如mod,sin,cos,指数等。想象一下,我们将哈希函数作为mod(5)来确定数据块的地址。 那么上述情况会怎样呢? 它在主键上应用mod(5)并分别生成3,3,1,4、2、XNUMX、XNUMX和XNUMX,并将记录存储在这些数据块地址中。

现在,从上面的两个图表中,可以清楚地了解哈希函数是如何工作的。

哈希文件组织有两种类型– 静止 以及 动态 散列。

静态散列

在这种散列方法中,结果数据存储区地址将始终相同。 这意味着,如果我们想使用mod(103)哈希函数生成EMP_ID = 5的地址,则它始终会导致相同的存储区地址3。此处的存储区地址不会有任何更改。 因此,用于该静态散列的存储器中的数据桶的数量始终保持恒定。 在我们的示例中,我们将在用于存储数据的内存中有五个数据桶。

搜索记录

使用哈希函数,将为哈希密钥生成数据存储区地址。 然后从该位置检索记录。 IE; 如果我们要检索ID 104的整个记录​​,并且如果ID上的哈希函数是mod(5),则生成的地址将是4。然后我们将直接到达地址4并检索ID 104的整个记录​​。充当哈希键。

插入记录

当需要将新记录插入表中时,我们将基于其哈希键为新记录生成一个地址。 地址生成后,记录将存储在该位置。

删除记录

使用哈希函数,我们将首先获取应该删除的记录。 然后,我们将删除该地址在内存中的记录。

更新记录

标记为更新的数据记录将使用静态哈希函数进行搜索,然后更新该地址中的记录。

 

假设我们必须在文件中插入一些记录。 但是哈希函数生成的数据存储区地址已满,或者该地址中已经存在数据。 我们如何插入数据? 静态哈希中的这种情况称为 桶溢出。 这是该方法的关键情况/缺点之一。 在这种情况下,我们将数据保存在哪里? 我们不会丢失数据。 有多种方法可以克服这种情况。 下面列出了最常用的方法:

封闭式散列

在这种方法中,我们引入了一个具有相同地址的新数据桶,并将其链接到完整的数据桶之后。 这些克服存储桶溢出的方法称为封闭哈希或 溢出链。

考虑我们必须在表中插入一个新记录R2。 静态哈希函数将数据存储区地址生成为“ AACDBF”。 但是此存储桶已满,可以存储新数据。 在这种情况下,要做的是在“ AACDBF”数据存储区的末尾添加一个新的数据存储区并链接到该数据存储区。 然后,将新记录R2插入到新存储桶中。 因此,它维护了静态哈希地址。 装满后,它可以添加任意数量的新数据桶。

公开哈希

在这种方法中,下一个可用的数据块用于输入新记录,而不是覆盖旧记录。 此方法称为“开放哈希”或 线性探测.

在下面的示例中,R2是需要插入的新记录。 但是哈希函数生成的地址为237。但是它已经满了。 因此,系统搜索下一个可用的数据桶238,并将R2分配给它。

在线性探测中,旧存储桶与新存储桶之间的差异通常是固定的,大多数情况下为1。

二次探测

这类似于线性探测。 但是在这里,新旧存储桶之间的差异是线性的。 我们使用二次函数来确定新的存储区地址。

双重散列

这也是线性探测的另一种方法。 这里的差异是固定的,就像在线性探测中一样,但是这个固定的差异是通过使用另一个哈希函数计算的。 因此,名称为双哈希。

动态散列

这种哈希方法用于克服静态哈希的问题-桶溢出。 在这种哈希方法中,数据桶随着记录的增加或减少而增长或收缩。 这种哈希方法也称为可扩展哈希方法。 让我们看一个例子来理解这种方法。

考虑表中有三个记录R1,R2和R4。 这些记录分别生成地址100100、010110和110110。 这种存储方法仅考虑该地址的一部分,尤其是仅用于存储数据的第一个位。 因此,它尝试将其中三个加载到地址0和1。

R3在这里会发生什么? R3没有存储桶空间。 存储桶必须动态增长才能容纳R3。 因此,它将地址更改为2位而不是1位,然后将现有数据更新为2位地址。 然后,它尝试容纳R3。

现在我们可以看到R1和R2的地址已更改以反映新地址,并且还插入了R3。 随着数据大小的增加,它会尝试插入现有的存储桶中。 如果没有可用的存储桶,则增加位数以考虑更大的地址,从而增加存储桶。 如果我们删除任何记录,并且数据可以用较小的存储桶存储,则会缩小存储桶的大小。 它的作用与我们上面所看到的相反。 这就是动态哈希的工作方式。 最初,仅将哈希函数生成的部分索引/地址视为存储数据。 随着数据数量的增加以及对更多存储桶的需求,考虑将更大一部分索引用于存储数据。

动态哈希的优点

  • 随着系统中数据的增长,性能不会下降。 它只是增加了内存大小以容纳数据。
  • 由于它随数据增长和收缩,因此可以很好地利用内存。 不会有任何未使用的内存在说谎。
  • 适用于数据频繁增长和收缩的动态数据库。

 

动态哈希的缺点

  • 随着数据大小的增加,存储桶的大小也会增加。 这些地址将保存在存储区地址表中。 这是因为,随着存储桶的增加和减少,数据的地址将不断变化。 当数据大量增加时,维护此存储区地址表将变得很繁琐。
  • 在这种情况下也会发生存储桶溢出的情况。 但是,与静态散列相比,达到这种状态可能需要很少的时间。

有序索引和散列的比较

有序索引

哈希

存储器中的地址按键值排序。 该键值可以是主键或表中的任何其他列。地址是使用键值上的哈希函数生成的。 该键值可以是主键或表中的任何其他列。
随着文件中数据的增加,此方法的性能下降。 因为它以排序形式存储数据,所以当执行插入/删除/更新操作时,需要付出额外的努力来对记录进行排序。 这会降低其性能。当频繁添加和删除数据时,动态哈希的性能会很好。 但是,如果数据库非常庞大,则维护成本会更高。

对于以前已知记录大小ID的小型数据库,静态哈希将非常有用。 如果数据增长,则会导致严重的问题,例如存储桶溢出。

由于删除/更新操作,将有未使用的数据块。 这些数据块不会被释放以供重复使用。 因此,需要定期维护存储器。 否则,内存被浪费了,性能也会下降。 同样,维护内存也将产生开销。在静态散列和动态散列中,都对内存进行了良好的管理。 在静态哈希中还可以更好地处理存储桶溢出。 数据块旨在在动态哈希中缩小和增长。

但是,当数据库增长迅猛时,在动态哈希中维护存储区地址表会产生开销。

首选用于数据范围检索-这意味着当存在特定范围的数据检索时,此方法最适合。此方法适用于根据搜索关键字检索特定记录。 但是,如果哈希函数不在搜索键上,它的性能将不会更好。