保序最小完美哈希函数

Question

我想在C++中为字典中的单词实现一个OPMPH函数。我该如何做？

谢谢！

- SuperString

Answer 1

您看过这些论文吗？

• http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.4018&rep=rep1&type=pdf
• http://dx.doi.org/10.1016/0020-0190(92)90220-P（短链接，指向http://www.sciencedirect.com/的非常长的链接）
• http://eprints.cs.vt.edu/archive/00000248/01/TR-91-01.pdf

- wallyk

Answer 2

将单词长度限制在6个字母或更少，你可能能够使它工作。但这并不是非常实用。

- Hans Passant

Answer 3

如果您需要字母顺序，请使用Trie或DAWG（就像我在您上一个问题中推荐的那样）。对于除字母表顺序之外的顺序，我会使用二叉树（C++中的std::map通常使用红黑树实现）。

实现一个保持顺序的哈希容器听起来像是所有早期优化中最重要的一项。

- joshperry