Electronic Joint Business

Solution for E-Business

hash

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 中。这两个函数是:

>>> 阅读全文

 

, , ,

哈希算法

文章评分:

哈希(Hash)算法就是单向散列算法,它把某个较大的集合P映射到另一个较小的集合Q中,假如这个算法叫 H,那么就有 Q = H(P)。对于 P 中任何一个值 p 都有唯一确定的 q 与之对应,但是一个 q 可以对应多个 p。作为一个有用的 Hash 算法,H 还应该满足:H(p) 速度比较快;给出一个 q,很难算出一个 p 满足 q = H(p);给出一个 p1,很难算出一个不等于 p1 的 p2 使得 H(p1)=H(p2)。

数学原理听起来很抽象,这里我们举个有趣的例子。农场里有很多的小猪,每个的体重都不一样,假设体重分布比较平均,都在100到120公斤之间(我们考虑到公斤级别),我们按照体重区间来分,建了10个小猪圈。 1号圈圈养90-92公斤的小猪,2号圈圈养92-94公斤的小猪,以此类推…。然后把每个小猪,按照体重赶进各自的猪圈里,记录档案。

好了,如果我们要精确找到某个小猪怎么办呢?我们需要每个猪圈,每个小猪的比对吗? 当然不需要了。 我们先看看要找的这个小猪的体重,然后就找到了对应的猪圈了。 在这个猪圈里的小猪的数量就相对很少了。 我们在这个猪圈里就可以相对快的找到我们要找到的那个小猪了。

对应回 hash 算法:就是按照 hashcode 分配不同的猪圈,将 hashcode 相同的猪放到一个猪圈里。 查找的时候,先找到 hashcode 对应的猪圈,然后在逐个比较里面的小猪。

>>> 阅读全文