用于映射 5 到 7 张卡的组合的哈希函数

参考原问题：优化扑克蒙特卡洛模拟的手牌评估算法 https://stackoverflow.com/questions/22412698/optimizing-hand-evaluation-algorithm-for-poker-monte-carlo-simulation

我有一个包含 5 到 7 张卡的列表，想要将它们的值存储在哈希表中，该哈希表应该是 32 位整数的数组，并且可以通过哈希函数值作为索引直接访问。 对于 52 张牌中可能存在的大量组合，我不想浪费太多内存。

Numbers:

• 7张卡组合：133784560
• 6 张卡组合：20358520
• 5 张牌组合：2598960
• 总计：156.742.040 种可能的组合

存储 1.57 亿个 32 位整数值大约需要 580MB。因此，我想通过在数组中为不需要的值保留内存来避免增加这个数字。

所以问题是：哈希函数如何将每个可能的、非重复的卡片组合映射到 0 到 156.742.040 之间的连续值或至少接近它？

Paul Senzee 在这方面有一篇很棒的文章，包含 7 张卡片（已删除链接，因为它已损坏，现在指向 NSFW 网站）。

他的代码基本上是一堆预先计算的表，然后是一个函数来查找给定的 7 张牌手牌的数组索引（表示为 64 位数字，其中最低 52 位表示牌）：

inline unsigned index52c7(unsigned __int64 x)
{
    const unsigned short *a = (const unsigned short *)&x;
    unsigned A    = a[3],                B    = a[2],                        C    = a[1],            D   = a[0],
             bcA  = _bitcount[A],        bcB  = _bitcount[B],                bcC  = _bitcount[C],    bcD = _bitcount[D],
             mulA = _choose48x[7 - bcA], mulB = _choose32x[7 - (bcA + bcB)], mulC = _choose16x[bcD];
    return _offsets52c[bcA]                      + _table4[A] * mulA + 
           _offsets48c[ (bcA << 4)        + bcB] + _table [B] * mulB +
           _offsets32c[((bcA + bcB) << 4) + bcC] + _table [C] * mulC + 
                                                   _table [D];
}

简而言之，它是由基于完美散列的预先计算的查找表提供支持的一堆查找和按位运算。

如果你回去看看这个网站 http://burtleburtle.net/bob/hash/perfect.html，您可以获得 Senzee 用于创建 7 卡哈希的完美哈希代码，并对 5 卡和 6 卡表重复该过程（本质上是创建一个新的index52c7.h对于每个）。你也许可以将所有 3 个都粉碎到一张桌子上，但我还没有尝试过。

总而言之，应该是 ~628 MB（4 字节 * 157 M 条目）。或者，如果您想将其拆分，您可以将其映射到 16 位数字（因为我相信大多数扑克手牌评估器只需要 7,462 个独特的手牌分数），然后从这 7,462 个手牌分数到您想要的任何手牌类别都有一个单独的映射。想。那将是 314 MB。