Perfect Hashing

定义 Definition

Perfect hashing（完美哈希）指一种哈希方法：在给定的一组固定不变的键（static set）上构造哈希函数，使得这些键在哈希表中不发生冲突（collision）。常见目标是实现查找的高效性（通常可做到接近或达到常数时间），并在一些方案中避免查找时的额外探测/链表开销。该术语在算法与数据结构（尤其是静态字典/集合查找）中常见。

发音 Pronunciation

/ˈpɜːrfɪkt ˈhæʃɪŋ/

例句 Examples

Perfect hashing lets us build a lookup table with no collisions for a fixed list of keys.
完美哈希可以让我们为一组固定的键构建一个没有冲突的查找表。

In a compiler, perfect hashing can speed up keyword recognition because the set of keywords is static.
在编译器中，完美哈希可以加速关键字识别，因为关键字集合是静态不变的。

词源 Etymology

perfect来自拉丁语 perfectus（“完成的、完善的”），在这里强调“理想状态”：对指定键集合而言冲突为零。
hashing源自 hash（原义与“切碎、混杂”相关），在计算机科学中指把数据通过哈希函数映射到表中位置的过程；perfect hashing就是“把映射做得足够好，以至于对这组键不会相互‘混到一起’（冲突）”。

相关词 Related Words

• Hash Function
• Collision
• Hash Table
• Static Set
• Dictionary
• Lookup
• Universal Hashing
• Minimal Perfect Hashing

文学/经典著作中的用例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）：在哈希相关章节中讨论完美哈希/静态集合查找思想。
• The Art of Computer Programming, Volume 3: Sorting and Searching（Donald E. Knuth）：在查找与散列主题中涉及完美哈希等相关概念与技术。
• Algorithms（Robert Sedgewick & Kevin Wayne）：在散列表与符号表内容中常提及完美哈希/相关变体与应用场景。