使用一组整数生成唯一键
Using a set of integers to generate unique key
现在我有一些整数集,比如说:
set1 = {int1, int2, int3};
set2 = {int2, int3, int1};
set3 = {int1, int4, int2};
不考虑顺序或数量,所以set1和set2是一样的,而set3不是另外两个。
现在我想为这些集合生成一个唯一的键来区分它们,这样,set1和set2应该生成相同的键。
我想了一会儿,我想到了总结整数的想法,但很容易被证明是错误的。对集合进行排序并执行
key = n1 + n2*2^16 + n3*2^32
可能是一种可行的方法,但我想知道是否可以更优雅地解决这个问题。
键可以是整数或字符串。
有人知道如何尽快解决这个问题吗?或者任何阅读 material 欢迎。
更多信息:
这些数字实际上是颜色,所以每个整数都小于 0xffffff
- 如果你的集合数量不是很大,我认为将每个集合散列成一个字符串可能是一个合适的解决方案。
- 然后他们是更大的,你可以通过 mod 功能或其他什么把它变成小的。这样一来,他们就可以用同样的方式处理了。
如果没有更好的主意,希望这对您的解决方案有所帮助。
我认为实际大小的键只能是哈希值 - 总会有几对输入哈希到同一个键,但您可以使这种情况不太可能发生。
我认为排序然后应用标准散列函数的想法很好,但我不喜欢你的散列乘法器。如果算术是 mod 2^32,那么乘以 2^32 就是乘以零。如果是mod2^64,那么乘以2^32会丢掉输入的前32位
我会使用像 Why chose 31 to do the multiplication in the hashcode() implementation ? 中描述的那样的散列函数,其中您保留 运行 总数,将散列值乘以某个奇数,然后再将下一项添加到其中。乘以一个奇数mod 2^n至少不会立即丢失信息。我建议使用 131,但 Java 有使用 31 的传统。
如果这些是小整数(例如都在范围 (0,63) 内),那么您可以将每个集合表示为位串(1 表示集合中存在的任何整数;0 表示不存在的任何整数)。对于大整数的稀疏集,就 storage/memory) 而言,这将非常昂贵。
想到的另一种方法是对集合进行排序并将键形成为每个数字的数字表示(由某个分隔符分隔)的串联。所以集合 {2,1,3} -> "1/2/3"(使用 "/" 作为分隔符)和 {30,1,2,4} => "1/2/4/30"
我想您也可以使用混合方法。所有 < 63 的元素都被编码为十六进制字符串,所有其他元素都被编码为所描述的字符串。然后,您最终生成的密钥由以下内容组成:HEXxA/B/c ...("x" 将小 int 十六进制字符串与集合中较大的 int 分开)。
现在我有一些整数集,比如说:
set1 = {int1, int2, int3};
set2 = {int2, int3, int1};
set3 = {int1, int4, int2};
不考虑顺序或数量,所以set1和set2是一样的,而set3不是另外两个。
现在我想为这些集合生成一个唯一的键来区分它们,这样,set1和set2应该生成相同的键。
我想了一会儿,我想到了总结整数的想法,但很容易被证明是错误的。对集合进行排序并执行
key = n1 + n2*2^16 + n3*2^32
可能是一种可行的方法,但我想知道是否可以更优雅地解决这个问题。 键可以是整数或字符串。
有人知道如何尽快解决这个问题吗?或者任何阅读 material 欢迎。
更多信息: 这些数字实际上是颜色,所以每个整数都小于 0xffffff
- 如果你的集合数量不是很大,我认为将每个集合散列成一个字符串可能是一个合适的解决方案。
- 然后他们是更大的,你可以通过 mod 功能或其他什么把它变成小的。这样一来,他们就可以用同样的方式处理了。
如果没有更好的主意,希望这对您的解决方案有所帮助。
我认为实际大小的键只能是哈希值 - 总会有几对输入哈希到同一个键,但您可以使这种情况不太可能发生。
我认为排序然后应用标准散列函数的想法很好,但我不喜欢你的散列乘法器。如果算术是 mod 2^32,那么乘以 2^32 就是乘以零。如果是mod2^64,那么乘以2^32会丢掉输入的前32位
我会使用像 Why chose 31 to do the multiplication in the hashcode() implementation ? 中描述的那样的散列函数,其中您保留 运行 总数,将散列值乘以某个奇数,然后再将下一项添加到其中。乘以一个奇数mod 2^n至少不会立即丢失信息。我建议使用 131,但 Java 有使用 31 的传统。
如果这些是小整数(例如都在范围 (0,63) 内),那么您可以将每个集合表示为位串(1 表示集合中存在的任何整数;0 表示不存在的任何整数)。对于大整数的稀疏集,就 storage/memory) 而言,这将非常昂贵。
想到的另一种方法是对集合进行排序并将键形成为每个数字的数字表示(由某个分隔符分隔)的串联。所以集合 {2,1,3} -> "1/2/3"(使用 "/" 作为分隔符)和 {30,1,2,4} => "1/2/4/30"
我想您也可以使用混合方法。所有 < 63 的元素都被编码为十六进制字符串,所有其他元素都被编码为所描述的字符串。然后,您最终生成的密钥由以下内容组成:HEXxA/B/c ...("x" 将小 int 十六进制字符串与集合中较大的 int 分开)。