完美哈希：从理论到 gperf 实践
编译器怎么在 O(1) 时间内判断一个标识符是不是关键字？用哈希表？但普通哈希表有冲突，最坏情况退化成链表。完美哈希给出了确定性答案：对已知的 n 个键，构造一个完全无冲突的哈希函数，查找时间严格 O(1)，空间 O(n)。这是静态字典问题的终极解法。
gperf 标签归档
共 1 篇文章 · 返回首页
发布来自土法炼钢兴趣小组的知识、笔记、进展和应用。主题包括数据结构和算法、编程语言、网络安全、密码学等。
共 1 篇文章 · 返回首页
编译器怎么在 O(1) 时间内判断一个标识符是不是关键字？用哈希表？但普通哈希表有冲突，最坏情况退化成链表。完美哈希给出了确定性答案：对已知的 n 个键，构造一个完全无冲突的哈希函数，查找时间严格 O(1)，空间 O(n)。这是静态字典问题的终极解法。