Minimal Perfect Hashing

Definition 定义

minimal perfect hashing（最小完美哈希）是一种构造哈希函数的方法：对一个已知且固定的键集合（n 个 key），生成一个哈希函数，把每个键无冲突地映射到 0 到 n−1 的整数范围，并且不浪费槽位（每个位置都被恰好一个键占用）。常用于只读字典、编译器符号表、词表索引等需要高速查找且空间紧凑的场景。

Pronunciation 发音

/ˈmɪnɪməl ˈpɝːfɪkt ˈhæʃɪŋ/

Examples 例句

We use minimal perfect hashing to map each keyword to a unique ID.
我们用最小完美哈希把每个关键字映射到一个唯一的编号。

In a static dataset, minimal perfect hashing can provide O(1) lookups with very low memory overhead, but rebuilding is required when keys change.
在静态数据集中，最小完美哈希能以很低的内存开销提供 O(1) 查询，但一旦键集合变化就需要重新构建。

Etymology 词源

该术语由三部分组成：minimal（“最小的”）强调输出范围正好是 n 个槽位、不多不少；perfect（“完美的”）指对给定键集合零碰撞；hashing（“哈希/散列”）源于把数据“切碎并分配到桶”的思想（hash 在英语里有“剁碎、混杂”的历史含义），在计算机领域引申为用函数将键映射到整数位置的技术。合起来即“为固定键集合构造零碰撞且不浪费空间的哈希”。

Related Words 相关词

• Perfect Hashing
• Hash Function
• Hash Table
• Collision
• Key
• Lookup
• Dictionary
• Indexing
• Bloom Filter
• Cuckoo Hashing

Literary Works 出处（作品/文献）

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein），在“Perfect Hashing（完美哈希）”相关章节讨论静态集合的哈希设计思想，与最小完美哈希密切相关。
• Algorithms（Robert Sedgewick & Kevin Wayne），在散列表与符号表相关内容中涉及完美哈希/静态查找结构的背景知识。
• Botelho, Pagh, Ziviani 等人的论文与技术报告（如关于 Fast and Compact Minimal Perfect Hash Functions 的系列工作），直接以最小完美哈希函数（MPHF）为主题。