不考虑字符位置的字符串哈希函数

Hash function for strings without respecting char's position

我的问题的标题是self-descriptive。 我需要散列三个 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));

Currently my cards are presented as bytes, but bits in two cards can overlap: A♣ = 0x11; 10♣=0x12; K♣=0x13 ... and so on.

您可以在计算哈希码时将此表示形式转换为上述表示形式,并避免以这种方式排序:

// 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));

另一种方法是计算每个字符出现的次数,然后对结果向量进行哈希处理(一个向量count,其中count[c]是一个字符出现的次数c)。我不会说它比排序好(字符数是固定的(而且可能很低)所以你可以使用基数排序)(但我也不能说它更糟)。两者的时间复杂度:使用基数排序和计算每个字符出现的次数是线性的(此外,基数排序和计算字符几乎是一回事),所以这两者之间应该没有太大区别。