我想创建一个哈希映射(或其他结构,如果您有任何建议)来存储键值对。这些键将在创建地图的同时一次性插入,但我不知道键是什么(任意长度的字符串),直到运行时,当我需要创建地图时。
我正在解析这样的查询字符串"x=100&name=bob&color=red&y=150"
(但是字符串可以有无限数量的变量,并且变量可以有任意长度的名称)。
我想解析一次并创建一个哈希映射,最好是最小的并且具有完美的哈希函数以满足线性存储要求。创建映射后,值将不会被修改或删除,也不会再向映射添加更多键值对,因此整个映射实际上是一个常量。我假设一个变量不会在字符串中出现两次(IE."x=1&x=2"
无效)。
我正在编码C
,目前有一个我可以使用的功能,例如get("x")
这将返回字符串"100"
,但它每次都会解析查询字符串,这需要O(n)
时间。我想在第一次加载时解析它一次,因为它是一个非常大的查询字符串,并且每个值都会被读取多次。即使我正在使用C
,我不需要代码C
作为答案。伪代码,或者任何建议都很棒!
尝试 GPL 许可gperf http://www.gnu.org/software/gperf/, or Bob Jenkins 在 C 中的公共域实现 http://burtleburtle.net/bob/hash/perfect.html
程序:
接收查询字符串并通过枚举键列表来识别完美哈希函数的域
将这些键和列表大小(范围为 1..size)提供给从上述参考实现派生的完美哈希生成函数
使用生成的完美哈希函数创建HashMap
使用相同的完美哈希函数来处理get
HashMap 中的请求
EditNecrolis 在下面的评论中指出,参考实现在 C 源代码中输出完美的哈希函数,因此您需要修改它们以生成类似于 VM 的字节码之类的内容。您还可以使用解释性语言,例如嵌入式Scheme 或Lua。
有趣的是,当创建完美哈希函数的开销通过查找分摊时,这是否值得在简单(非完美)HashMap 上付出努力
另一种选择是布谷鸟哈希 http://en.wikipedia.org/wiki/Cuckoo_hashing其中也有 O(1) 查找
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)