我正在尝试编写一个(完美)哈希表来压缩从unicode代码点名称到其代码点编号的映射(将第二列映射到第一列).正如你可以看到有,可能的输入都非常有限,实际上有一个在字母恰好38个字符:AB...YZ,0...9,-和空间.此外,还有大量的(子)的重复,DIGIT ZERO,DIGIT ONE,... LATIN CAPITAL LETTER A,LATIN CAPITAL LETTER B等等.
通过选择种子来计算完美的哈希表S,然后尝试构造一个完美的哈希表种子(以某种方式)播种S.如果无法创建表,则会使用新种子重试.有很多冲突通常需要更多的重试,因为算法更难以使一切都适合.
这样做的结果是我的输入域具有低熵,并且表创建需要使用像DJB2这样的简单散列函数进行大量重试; 像FNV这样的更好的编组器可以很好地工作,但是像SipHash这样的更复杂和更慢的功能似乎平均需要更少的重试.
由于这是完全静态和预先计算的,我不太为质量而担心质量(即运行时任意输入的安全性和概率分布无关紧要),但更高质量的功能减少了给定级别所需的预计算时间相反,压缩,允许我在一些固定的时间内实现更高的压缩.
问题:是否有高效的已发布哈希函数调整为输入域限制,如下所示？也就是说,是否存在利用额外结构来执行更少操作但仍能实现合理输出的哈希函数？
我搜索过像'字母数字哈希函数'之类的东西,但结果是无关的(大多只是生成一个字母数字字符串作为哈希函数的输出); 甚至一些关于正确行话的指导,以便我可以搜索论文会有所帮助.
(这个问题的动机是稍微有点难以解决,而不是实际需要.)
我正在尝试编写一个（完美的）哈希表......
如果你想要一个完美的哈希函数，我会用 CMPH 之类的东西生成它。这可能最终成为幕后的一些静态查找表。
或者，您可以使用基于非哈希的方法，例如使用 DAWG 或某种类似 Trie 的结构（以及顶部的一些 Aho-Corasick？）。
DAWG 可以提供相当紧凑的存储空间，并可以快速搜索字符串到数字。我的预感是它可能会击败哈希表来解决您的问题。
请参阅http://www.wutka.com/dawg.html了解一些介绍。有多种语言的实现。