我想创建一个哈希映射（或其他结构，如果您有任何建议）来存储键值对。这些键将在创建地图的同时一次性插入，但我不知道键是什么（任意长度的字符串），直到运行时，当我需要创建地图时。
我正在解析这样的查询字符串"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
使用相同的完美哈希函数来处理getHashMap 中的请求
EditNecrolis 在下面的评论中指出，参考实现在 C 源代码中输出完美的哈希函数，因此您需要修改它们以生成类似于 VM 的字节码之类的内容。您还可以使用解释性语言，例如嵌入式Scheme 或Lua。
有趣的是，当创建完美哈希函数的开销通过查找分摊时，这是否值得在简单（非完美）HashMap 上付出努力
另一种选择是布谷鸟哈希 http://en.wikipedia.org/wiki/Cuckoo_hashing其中也有 O(1) 查找
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
