Lec06_哈希表1

哈希表是一种高效的数据结构，常用于数据库管理系统(DBMS)中的访问方法，目的是为了能够快速地定位和访问数据。在本讲座中，我们将探讨哈希表的设计、哈希函数的选择以及处理哈希冲突的策略。 哈希表的数据结构通常是数组与哈希函数的结合。哈希函数的作用是将输入的键(Key)转换为数组的索引，从而在内存中找到对应的位置存储或查找键值对。理想的哈希函数应具备快速计算和低冲突率的特点。DBMS中的哈希函数不同于加密用的哈希函数，后者强调不可逆性和高计算复杂度，而DBMS需要的是能快速计算且冲突少的函数。 面对哈希冲突，有多种静态和动态的解决方案。静态哈希策略包括线性探测哈希（Linear Probe Hashing）。在这种方法中，如果发生冲突，数据会存储在冲突位置的下一个槽中。但删除数据时需注意，简单删除可能导致后续查询错误。为此，可以采用“墓碑”标记或数据移动的方式来处理。 线性探测哈希的改进策略是Robin Hood Hashing，它记录每个槽位的“偏移量”，当发生冲突时，会比较槽位的偏移量并调整，使得槽位间的偏移量差异减小，类似于“劫富济贫”。 另外一种静态策略是Cuckoo Hashing，它使用多个哈希表和哈希函数。当插入数据时，寻找不会引发冲突的哈希表。若所有表都冲突，则执行类似于匈牙利算法的操作，直至找到无冲突的位置。 然而，静态哈希策略存在限制，因为哈希槽的数量固定，导致存储容量受限。因此，出现了动态哈希策略，如链式哈希(Chained Hashing)，它允许哈希桶数量随着数据量增加而动态扩展，例如Go语言的哈希表就采用了这种方式。另一种动态策略是可扩展哈希(Extendible Hashing)，通过改变哈希函数的结构，使哈希表在冲突增多时仍能保持较高的效率，避免链表退化。 哈希表的设计和优化是数据库性能的关键因素之一。选择合适的哈希函数和处理冲突的策略，可以极大地提高数据访问速度和系统的并发处理能力。在实际应用中，根据系统的需求和预期数据量，灵活选择和设计哈希表结构至关重要。