hash - 低熵字母数字字符串的高效散列函数

Question

我正在尝试编写一个(完美的)哈希表来压缩来自 unicode codepoint names to their codepoint number 的映射(将第二列映射到第一列)。正如您在那里看到的，可能的输入非常有限，实际上字母表中正好有 38 个字符:AB...YZ , 0...9 , -和空间。此外，还有很多(子串)重复，DIGIT ZERO , DIGIT ONE , ..., LATIN CAPITAL LETTER A , LATIN CAPITAL LETTER B等等。

完美哈希表是通过选择一个种子 S 来计算的。 ，然后尝试通过 S 构建一个完美的哈希表种子(以某种方式)散列器.如果无法创建表，则使用新种子重试。有很多冲突通常需要更多的重试，因为算法更难让一切都适合。

这样做的结果是我的输入域具有低熵，并且表创建需要使用 DJB2 之类的简单哈希函数进行大量重试；像 FNV 这样更好的散列器可以很好地工作，但是像 SipHash 这样更复杂和更慢的函数似乎平均需要更少的重试。

由于这完全是静态的和预先计算的，我不太担心质量问题(即运行时任意输入的安全性和概率分布无关紧要)，但更高质量的函数减少了给定级别所需的预计算时间相反，压缩允许我在某个固定时间内实现更高的压缩。

问题 :是否有有效的已发布哈希函数调整为具有这样的域约束的输入？也就是说，是否有散列函数利用额外的结构来执行更少的操作，但仍能获得合理的输出？

我搜索过诸如“字母数字哈希函数”之类的东西，但结果是不相关的(主要是生成一个字母数字字符串作为哈希函数的输出)；即使是关于正确行话的一些指导，以便我可以搜索论文也会有所帮助。

(这个问题的动机是解决有点有趣，实际上没有必要。)

Answer 1

I'm trying to write a (perfect) hash table ...

如果你想要一个完美的散列函数，我会用像 CMPH 这样的东西来生成它。这可能最终成为幕后的一些静态查找表。

或者，您可以使用基于非哈希的方法，例如使用 DAWG 或一些类似 Trie 的结构(以及一些 Aho-Corasick 在上面？)。

DAWG 将提供相当紧凑的存储和快速搜索字符串到数字。
我的预感是，它可能会因您的问题而击败哈希表。

见 http://www.wutka.com/dawg.html一些介绍。有多种语言的实现。