在数据结构中，哈希是一种使用称为哈希函数的特殊函数将大量数据项映射到较小表的技术，以实现更快的访问。有时数据结构非常庞大，几乎不可能通过所有级别搜索所有索引值来访问最终的数据块。这就是散列的用武之地。它所做的是直接计算数据记录在磁盘上的位置，而不使用索引结构。每个记录的地址是使用哈希算法确定的，该算法将主键值转换为记录地址。因此，有两类可用的索引使用哈希函数-动态哈希和静态哈希。

什么是静态哈希(static hashing)？

静态哈希是一种哈希方法，其中为文件分配固定数量的bucket来存储记录。存储桶的数量是预先分配的，因此当提供搜索键值时，哈希函数总是计算相同的地址。一个文件的页面可以被看作是一个bucket集合，包含一个主页面和额外的溢出页面。对于静态哈希，定位机制是哈希函数，不涉及数据结构。在这里，索引项是随机的，每个bucket中的索引项的数量大致相同。然而，这项计划也有某些缺点。如果bucket的初始数目太小，文件会增长，那么性能会因为bucket溢出而下降。另一方面，如果规模过大，则会为预期增长分配大量空间，并浪费大量空间。

什么是动态哈希(dynamic hashing)？

另一方面，动态哈希是一种用于克服静态哈希（如桶溢出）限制的技术。与静态哈希不同，它允许桶的数量动态变化，以适应数据库文件的增长或收缩。它允许根据需要修改hash函数，这对于大小不断增长和缩小的数据库是很好的。在添加和删除行时，它会相应地更改bucket的数量，以最小化bucket的溢出。它将溢出记录的处理动态地嵌入到主地址空间中，以避免溢出存储桶的句柄管理。动态哈希的两种常用形式是线性哈希和可扩展哈希。可扩展哈希是一种流行的技术，它通过将一个bucket一分为二来处理bucket溢出，在新旧bucket之间分发记录。线性哈希是另一种流行的动态哈希形式，它允许哈希文件通过分配新的存储桶来动态地增长或收缩。

动态和静态散列的区别

技术

–静态哈希是一种哈希方法，其中为文件分配固定数量的存储桶以存储记录，这意味着文件使用的哈希函数中存储桶地址的数量是固定的。在这里，索引项是随机的，每个bucket中的索引项的数量大致相同。另一方面，动态哈希允许存储桶的数量动态变化，以适应数据库文件的增长或收缩。

演出

–如果bucket的初始数目太小并且文件增长，那么性能会因为bucket溢出而下降。另一方面，如果规模过大，则会为预期增长分配大量空间，并浪费大量空间。另一方面，动态散列允许动态修改散列函数，这有利于数据库大小的增长和收缩。在添加和删除行时，它会相应地更改bucket的数量，以最小化bucket的溢出。

实施

–静态哈希使用固定的哈希函数将所有可能的搜索键值集划分为子集，然后将每个子集映射到一个bucket。另一方面，动态哈希使用映射的第二阶段来确定与某个搜索键值相关联的bucket。可扩展散列和线性散列的映射方式非常不同。

动态与静态散列：比较图

总结

静态哈希中存储桶的数量是固定的，具有不同搜索关键字值的记录指向同一个存储桶，在这种情况下可能会发生冲突。如果需要在具有多个键的bucket中查找特定记录，则必须按顺序搜索整个bucket。有时候，一个bucket包含的记录比它能包含的要多。因此，在这种情况下，必须调用一些溢出处理技术。在这种情况下，将使用动态哈希，它使用一个动态更改的函数，该函数允许分配的bucket数随着行的添加和删除而在大小上增长和收缩。它通过将溢出记录动态嵌入主地址来显式处理bucket的溢出。