PerfectHash
所属分类:数据结构
开发工具:Visual C++
文件大小:2522KB
下载次数:26
上传日期:2009-10-15 00:18:25
上 传 者:
no name
说明: 向大家推荐一个Perfect hash算法
它能对一个静态的keys数组生成1-1的hash函数
id = hash(key)
id 在 (0,n-1)之间
n为key的总数
这个函数的构造时间是O(n),查询时间是常数
占用的内存是每个key使用2.7bits
提供了不同的算法供选择。
(O (n), query time is constant, the memory occupied by the use of each key provides a different 2.7bits algorithms available.)
文件列表:
PerfectHash\libcmph.lib (667062, 2009-04-30)
PerfectHash\cmph.h (3969, 2009-04-30)
PerfectHash\CMPH - C Minimal Perfect Hashing Library.mht (16836, 2009-04-30)
PerfectHash\mphf.txt.bak (622, 2009-04-30)
PerfectHash\mphf.txt (1698, 2009-04-30)
PerfectHash\CMPH - Examples.mht (6455, 2009-04-30)
PerfectHash\cmph_types.h (1181, 2009-04-30)
PerfectHash\example.suo (9728, 2009-04-30)
PerfectHash\example.cpp (933, 2009-04-30)
PerfectHash\cmph-0.8.rar (2460783, 2009-04-30)
PerfectHash\example.opt (48640, 2009-04-30)
PerfectHash (0, 2009-04-30)
CMPH - C Minimal Perfect Hashing Library.mht (22029, 2009-10-15)
CMPH - Examples.mht (6455, 2009-09-07)
cmph.txt (639, 2009-09-07)
id = hash(key)
id 在 (0,n-1)之间
n为key的总数
这个函数的构造时间是O(n)
查询时间是常数
占用的内存是每个key使用2.7bits
使用方法:如果原始数据顺序不需要保持,则根据生成的id调整位置
这样根据hash函数直接得到key所在元素的偏移
当查询一个不在静态key数组内的key,有2种可能
1:返回的id不在(0,n-1)范围 说明该key不在数组内
2:返回一个有效地ID 这是需要进一步根据ID取得Key值与生成id的key作比较 如果相同,该key在数组内 不同,则不再数组内
近期下载者:
相关文件:
收藏者: