math - 如何为两个可互换的整数创建唯一键？

Question

我正在尝试为 Euclid 查找两个数字的 GCD 的方法编写一个简单的缓存机制：

gcd(a,0) = a
gcd(a,b) = gcd(b, a % b)

请注意gcd(a,b) == gcd(b,a).

对于缓存，我需要为给定的(a,b)or找到一个键(b,a)，使用0 < a < 20and 0 < b < 20。

当然，我可以使用key = a*20 + b, 或key = a + b*20，但它们是不对称的 - for 的密钥与 for(1,5)不同(5,1)。

我怎么能实现这个？

Answer 1

首先，对数字进行排序。

key = a > b ? b*20 + a : a*20 + b;

Answer 2

令 c 为 min(a,b)，d 为 max(a,b)。然后，您的哈希函数 c*20 + d 关于 a 和 b 是对称的。