是否有从输入生成单词的伪哈希函数？

Question

我正在尝试寻找或想出一种算法，该算法对输入执行哈希以生成两个或三个单词的输出。

例如：

• "ABCD" -> "tree blue"

• "WXYZ" -> "curious acorn"

  算法需要

  1. 始终对相同的输入产生相同的结果
  2. 碰撞概率低，但不需要像"real"散列那样严格
  3. 重新创建输入的难度适中，但不需要像 "real" 哈希那样严格

我有一个想法是使用普通的散列函数创建一个散列值，然后使用前几个字符到select个单词：

• "ABCD" -> "2fd4e1c..." -> {"2fd": "tree", "4e1": "blue"}

但我不确定什么是好的查找算法（用于在我的表中对所有单词进行统一分布）以及这是否满足我的上述要求。

Answer 1

对于小于 2^-k 的碰撞概率，您需要大约 2^2k 位熵由于 birthday paradox。这使您可以粗略估计给定数量的单词在字典中需要多少个单词，反之亦然。

您建议的方法看起来很合理：使用良好的标准哈希函数，然后，对于大小为 n 的字典，只需使用第一个 log₂(n) 第一个单词的散列位，下一个 log₂(n) 第二位等