DBMS - 哈希(即散列)
对于一个庞大的数据库结构，几乎不可能通过其所有级别搜索所有索引值，然后到达目标数据块以检索所需数据。 哈希（也称为即列）是一种无需使用索引结构即可计算数据记录在磁盘上的直接位置的有效技术。
哈希使用带有搜索键的哈希函数作为参数来生成数据记录的地址。
哈希组织
哈希桶 − 哈希文件以桶格式存储数据。 桶被认为是一个存储单元。 一个桶通常存储一个完整的磁盘块，而磁盘块又可以存储一条或多条记录。
哈希函数 − 哈希函数 h, 是一个映射函数，它将所有搜索键集 K 映射到放置实际记录的地址。 是一个从搜索key到bucket地址的函数。
静态哈希
在静态哈希中，当提供搜索键值时，哈希函数总是计算相同的地址。 例如，如果使用 mod-4 哈希函数，那么它应该只生成 5 个值。 该函数的输出地址应始终相同。 提供的桶数始终保持不变。
操作
插入 − 当需要使用静态哈希输入记录时，哈希函数 h 计算搜索键 K 的存储桶地址，记录将存储在其中。
桶地址 = h(K)
搜索 − 当需要检索记录时，可以使用相同的哈希函数来检索存储数据的桶的地址。
删除 − 这只是一个搜索，然后是一个删除操作。
桶溢出
桶溢出的情况称为碰撞。 这对于任何静态哈希函数来说都是致命的。 在这种情况下，可以使用溢出链接。
溢出链接 − 当存储桶已满时，会为相同的哈希结果分配一个新存储桶，并在前一个存储桶之后链接。 这种机制称为封闭哈希。
线性探测 − 当哈希函数生成一个已经存储数据的地址时，下一个空闲桶被分配给它。 这种机制称为Open Hashing。
动态哈希
静态哈希的问题在于它不会随着数据库大小的增长或收缩而动态扩展或收缩。 动态哈希提供了一种机制，在该机制中，可以按需动态添加和删除数据桶。 动态哈希也称为扩展哈希。
哈希函数，在动态哈希中，是用来产生大量值的，最初只使用少数几个。
组织
将整个哈希值的前缀作为哈希索引。 只有一部分哈希值用于计算桶地址。 每个哈希索引都有一个深度值来表示用于计算哈希函数的位数。 这些位可以寻址 2n 个桶。 当所有这些位都被消耗掉时 也就是说，当所有的桶都满了 − 然后深度值线性增加，分配两倍的桶。
操作
查询 − 查看哈希索引的深度值并使用这些位来计算存储桶地址。
更新 − 执行上述查询并更新数据。
删除 − 执行查询以找到所需数据并删除。
插入 − 计算桶的地址
- 如果存储桶已满。
- 添加更多存储分区。
- 向哈希值添加额外的位。
- 重新计算哈希函数。
- Else
- 向存储桶添加数据，
- 如果所有存储桶都已满，请执行静态哈希补救措施。
- 如果存储桶已满。
当数据以某种顺序组织并且查询需要一定范围的数据时，哈希是不利的。 当数据离散且随机时，哈希表现最好。
哈希算法比索引具有更高的复杂性。 所有的哈希运算都是在恒定时间内完成的。
