type
status
date
slug
summary
tags
category
icon
password
Sub-item
Last edited time
Oct 28, 2023 10:43 AM
Parent item
领域
传统的 Hashmap 总会有分支预测开销与内存对比，最差时间复杂度是 O(n)，有那么一种 Hash 函数：完美 Hash 函数（ Perfect Hash Function，PHF），它可以在最坏情况下取得 O(1) 的时间复杂度。当然鱼和熊掌不可兼得，完美 Hash 要求有一个静态的输入集合，查找的 Key 必须存在于静态输入集合中，导致使用场景受限。它有几个特点：
- 完美 Hash 大部分都要求输入 Key 的集合是已知的，用于提前构建数据结构；
- 构造算法复杂，大部分情况下需要比较大的内存，特别是时间复杂度高，需要很长的时间建立索引，构建海量 key 的完美 Hash 可能会失败；
- 完美 Hash 在实现上并不是只有一个 Hash 函数，而是多个普通 Hash 函数与数据结构算法上的组合，这意味着需要额外空间存储 Hash 冲突信息。
尽管它有一些缺点，但是在一些场景如汉字拼音映射，词典，以及程序中预定义的映射关系都有它的应用。