动态散列

引言

在本文中，我们将借助各种示例详细阐述动态哈希的概念。

什么是动态哈希？

• 动态哈希方法用于克服静态哈希的问题，如桶溢出。
• 在这种方法中，数据桶会随着记录的增加或减少而增长或收缩。这种方法也称为可扩展哈希方法。
• 这种方法使哈希动态化，即允许插入或删除，而不会导致性能下降。

如何搜索键

• 首先，计算键的哈希地址。
• 检查在目录中使用了多少位，这些位称为 i。
• 取哈希地址的最低 i 位。这给出了目录的索引。
• 现在使用索引，转到目录并找到可能存在记录的桶地址。

如何插入新记录

• 首先，您必须遵循与检索相同的过程，最终进入某个桶。
• 如果该桶中仍有空间，则将记录放入其中。
• 如果桶已满，则我们将拆分桶并重新分配记录。

例如

考虑根据哈希地址的前缀将键分组到桶中

2 和 4 的最后两位是 00。因此，它将进入桶 B0。 5 和 6 的最后两位是 01，因此它将进入桶 B1。 1 和 3 的最后两位是 10，因此它将进入桶 B2。 7 的最后两位是 11，因此它将进入 B3。

将键 9（哈希地址为 10001）插入到上述结构中

• 由于键 9 的哈希地址是 10001，因此它必须进入第一个桶。 但是桶 B1 已满，因此它将被拆分。
• 拆分将 5、9 与 6 分开，因为 5 和 9 的最后三位是 001，所以它将进入桶 B1，6 的最后三位是 101，所以它将进入桶 B5。
• 键 2 和 4 仍然在 B0 中。 B0 中的记录由 000 和 100 条目指向，因为这两个条目的最后两位都是 00。
• 键 1 和 3 仍然在 B2 中。 B2 中的记录由 010 和 110 条目指向，因为这两个条目的最后两位都是 10。
• 键 7 仍然在 B3 中。 B3 中的记录由 111 和 011 条目指向，因为这两个条目的最后两位都是 11。

动态哈希的优点

• 在这种方法中，性能不会随着系统中的数据增长而降低。 它只是增加内存的大小以容纳数据。
• 在这种方法中，内存得到了很好的利用，因为它会随着数据的增长和收缩而增长和收缩。 不会有任何未使用的内存闲置。
• 这种方法适用于数据经常增长和收缩的动态数据库。

动态哈希的缺点

• 在这种方法中，如果数据大小增加，则桶大小也会增加。 这些数据地址将保存在桶地址表中。 这是因为数据地址将随着桶的增长和收缩而不断变化。 如果数据量急剧增加，维护桶地址表将变得繁琐。
• 在这种情况下，桶溢出情况也会发生。 但到达这种情况可能比静态哈希需要更少的时间。

DBMS 中有关动态哈希的一些常见问题列表

1. 列出动态哈希执行的各种操作？

答案： 以下是动态哈希执行的各种操作

• 删除
• 插入
• 查询
• 更新

2. 列出动态哈希的一些特性？

答案： 以下是动态哈希的特性列表

• 可扩展哈希表。
• 桶分裂
• 目录扩展

3. 动态哈希如何处理数据集增长？

答案： 它通过拆分桶和增加目录大小来自动修改哈希表的大小，因为元素的数量增加了。