我的题目是自我描述。
我需要散列一个由三个64位变量组成的结构(我将把它们转换成一串字符),每个变量都包含一个纸牌游戏应用程序,因此交换这些变量中的一些字符应该会产生相同的散列。
一种方法是对结果字符串进行排序有更好的解决办法吗?
最佳答案
如果一只手的表示类似于一个位集,那么它已经无序了。例如,如果使用位掩码的组合来表示卡的组合,例如
A♠ - 0x00000001
2♠ - 0x00000002
3♠ - 0x00000004
4♠ - 0x00000008
...
K♠ - 0x00001000
A♥ - 0x00002000
2♥ - 0x00004000
...
然后可以使用位组合表示手,如下所示:
A♠ 4♠ 2♥ - 0x00004009
此表示与位置无关,即手
4♠ A♠ 2♥
和2♥ 4♠ A♠
的表示与A♠ 4♠ 2♥
完全相同。您可以根据需要将此表示转换为字符串,方法是迭代各个位,并在每次发现设置为1的位时向字符串表示添加一张卡。这样的表示可以通过将表示的上32位与下32位进行异或运算来计算32位哈希代码:
uint64_t hand = ... // A representation of hand similar to what's described above
uint32_t hash = (uint32_t)(hand ^ (hand >> 32));
目前,我的卡片以字节的形式显示,但两张卡片中的位可以重叠:
A♣ = 0x11; 10♣=0x12; K♣=0x13
等等。在计算哈希代码时,可以将此表示转换为上述表示,并避免按此方式排序:
// Each card is a number from 1 to 53, inclusive
uint8_t hand[HAND_SIZE] = ...; // The hand
uint64_t set = 0;
for (int i = 0 ; i != HAND_SIZE ; i++) {
set |= (1LL << hand[i]);
}
uint32_t hash = (uint32_t)(set ^ (set >> 32));