c++ - 有效地索引 "Hash"值集

Question

首先是免责声明；哈希对于我的目标来说是一个有点不准确的术语，请随意建议一个更好的标题。

无论如何，我目前正在尝试编写一个实时运行的复杂空间算法。为了节省周期，我决定生成一个包含所有 32,000 种可能性的查找表。

如果我按照惯例这样做，值(包括范围和字段计数)2x +0 -> +15 和 3x -2 -> +2 将分别映射到两个四位值和三个三位值，给我的查找表大小为 2 ^ (2*4 + 3*3) = 131,072 个条目，浪费了将近 410%。

鉴于算法的性质，冲突绝对会削弱其功能(因此除非我能保证与所有相关值不发生冲突，否则不会使用传统的哈希函数)。除此之外，我正在使用的结构相当大(即，我/真的/想避免分配超过我需要的 200%)。最后，由于这个表将被如此频繁地引用，我想避免传统哈希表在桶查找和过于复杂的哈希函数中的开销。

采用更传统的计算机科学方法后，我开始坚信解决方案在于一些我完​​全不知道的碱基转换数学。知道是否是这种情况吗？

Answer 1

您可以通过将每个元素相乘来计算索引，方法与计算最大组合数的方法相同。将每个元素从最重要到最不重要，加上一个常数，使其范围从 0 到 n-1，然后乘以剩余的组合数。

给定 a、b 的 0 到 15 值(范围 16)和 c、d、e 的 -2 到 +2 值(范围 5):

index = a * 16*5*5*5 + b * 5*5*5 + (c+2) * 5*5 + (d+2) * 5 + (e+2);