手机浏览 RSS 2.0 订阅 膘叔的简单人生 , 腾讯云RDS购买 | 超便宜的Vultr , 注册 | 登陆

最小完美哈希函数

首页 > PHP >

不好意思,这是一个标题党,主要是这个词语太让人震惊,但现在它又将变的地了。所以我先记录一下。

什么是完美哈希函数?
這一段內容來自:(http://www.kuqin.com/algorithm/20111108/314569.html)
最小完美哈希函数是什么,要从定义说起,这个名字很长,一步步解释。

  1. 哈希函数 任意函数h(x)都可以说哈希函数,一般来说,一个良好的哈希函数可以尽量避免重复。x的集合是参数域,h(x)的集合是值域。
  2. 完美哈希函数  完美哈希函数,就是完全不会冲突的哈希函数,这要求函数的值域至少比参数域要大
  3. 最小完美哈希函数 最小完美哈希函数,就是指函数的值域和参数域的大小完全相等,一个也不多
  4. 保序最小完美哈希函数 保序的意思就是指这个哈希之后顺序是不变的,同时还能满足其他两个条件。
这个函数的优点就是形式上很完美,就像给一个排好序的文档编上的序号一般紧凑可靠。但是这个函数有两个缺点,一是必须事前必须知道原数据集,二 是需要花一定的CPU来生成这个函数。我认为,对于数据仓库类的线下搜索应用,这个算法是有用武之地的。但对于强调实时的数据业务,这个算法是不适合的。
----------
這裏還有一個點評:(http://liulixiang.info/blog/tag/%E6%9C%80%E5%B0%8F%E5%AE%8C%E7%BE%8E%E5%93%88%E5%B8%8C%E5%87%BD%E6%95%B0/)

点评:(by liulixiang)

“最小完美哈希函数”从概念上很完美,生成的思想也很不错,不过实际运用中并不是那么常见:应用中已知数据集再做哈希的情况不是特别多,对时空的复杂度要求也没有过于苛刻,普通的方法即可承受。另外一般数据集很大,生成该函数的开销也太大。

---------
參考文檔:

最小完美哈希函数方法来自于Czech, Havas, Majewski等的论文:

An optimal algorithm for generating minimal perfect hash functions(Czech等1991)

Graphs, hypergraphs and hashing(Havas等1993)

A family of perfect hashing methods(Majeki等1996)

本文大部分转述或摘抄自《深入搜索引擎——海量信息的压缩、索引和查询》(该书豆瓣链接) 一书(Page 173~181),该书由梁斌翻译(原版即大名鼎鼎的MG——“Managing Gigabytes: Compressing and Indexing Documents and Image, Second Edition” 由Ian H. Witten, Alistair Moffat, Timothy C.Bell合著)(MG网站




本站采用创作共享版权协议, 要求署名、非商业和保持一致. 本站欢迎任何非商业应用的转载, 但须注明出自"易栈网-膘叔", 保留原始链接, 此外还必须标注原文标题和链接.

« 上一篇 | 下一篇 »

1条记录访客评论

imya

Post by tes on 2012, July 23, 8:52 AM 引用此文发表评论 #1


发表评论

评论内容 (必填):