Electronic Joint Business

Solution for E-Business

gperf

GPerf 和完美哈希函数

GNU Gperf 工具用来生成一种 “完美的” 散列函数(perfect hash function),可以将用户提供的一组特定字符串生成散列表、散列函数和查找函数的 C/C++ 代码。 所谓完美散列函数或完美 Hash 函数,指存在这样一个 hash 函数 F,可以将一个含有 n 元素的用户特定关键字集合 N 到集合 W, N 的关键字被唯一映射到 W 的 0..k-1 范围,其中 k>=n。如果 k=n 那么 F 就是“最小化完美 hash 函数”。

最小化完美 hash 函数具有两个特性:

  • 只需要执行一次查找就能完成静态搜索结构中的关键字识别,即所谓的“完美”。
  • 为保存关键字所分配的内存刚刚可以容纳关键字集合,不会多余。即“最小化”。

Gperf 被普遍地用在多种商业编译器、研究型编译器、语言处理工具的词法分析器上,用来生成关键字识别器,包括:GNU C, GNU C++, GNU Pascal, GNU Modula 3 和 GNU indent 等等。Gperf 将从用户提供的文件中(即关键字文件,通常使用 .gperf 作为扩展名,但不做强制要求)生成 C/C++ 源代码。所有代码被定向到标准输出,然后必须重定向到类似下面的文件:

gperf  -L C++ keyfile.gperf > perfecthash.hpp

注意: -L 选项将指示 gperf 生成 C++ 代码。

Gperf 会生成一个 0..K 元素的静态查找结构和一对 C 函数的源代码。利用这些函数只需要一次查找,就可以判断给定的字符串 S 是否在集合 W 中。这两个函数是:

>>> 阅读全文

 

, , ,