哈希表与哈希函数：《算法导论》课件解析

"《算法导论》原版英文课件7——哈希与哈希函数" 这组课件是关于计算机科学中一个重要的主题——哈希（Hashing）及其相关概念，出自《算法导论》这本经典教材。在Lecture 7中，主要讨论了直接访问表、碰撞解决策略、哈希函数的选择以及开放寻址法。 1. 直接访问表（Direct-access table） 直接访问表是一种基于数组的数据结构，用于实现符号表（Symbol table），其中每个元素都有一个唯一的键（key）。如果键值范围是{0, 1, ..., m-1}，且所有键都是不同的，那么可以创建一个大小为m的数组T，其中T[k]存储对应键值为k的记录x。这样，对表中的操作如插入、删除和查找都可以在常数时间复杂度O(1)内完成。然而，实际问题在于，键的取值范围可能非常大，例如64位数字或字符串，这使得直接使用数组变得不切实际。 2. 碰撞解决：链接法（Chaining） 为了处理键值冲突（即多个记录映射到同一个数组位置），可以采用链接法。这种方法是在每个数组位置上存储一个链表，所有映射到该位置的记录都添加到这个链表中。虽然单个查找操作仍然可以在平均情况下接近O(1)，但最坏情况下时间复杂度会增加到O(n)，其中n是链表的长度。 3. 哈希函数（Hash Function） 哈希函数是将任意大小的输入（如字符串或整数）映射到固定大小的输出（通常较小的整数）的函数。选择一个好的哈希函数至关重要，因为它直接影响到哈希表的性能。好的哈希函数应尽量减少冲突，并使输出分布均匀。设计哈希函数时，需要考虑数据的特点和预期的键值分布。 4. 开放寻址法（Open Addressing） 当发生碰撞时，开放寻址法不是使用链表，而是通过某种探测序列在数组中寻找下一个可用的位置。常见的探测方法有线性探测、二次探测和双哈希探测等。这种方法的优点是空间效率高，因为不需要额外的链表存储，但查找效率可能不如链接法，尤其是在哈希表填充率较高时。 这些内容构成了哈希技术的基础，它们广泛应用于数据库系统、编程语言的字典类型、缓存系统以及各种需要高效查找操作的场景。理解并掌握哈希原理对于优化算法性能和设计高效数据结构至关重要。