0

给定n 个整数 id，我希望将所有可能的最多 k个 id 的集合链接到一个常数值。我正在寻找一种将集合（例如 {1, 5}, {1, 3, 5} 和 {1, 2, 3, 4, 5, 6, 7}）转换为唯一值的方法。

保证：

  • n < 100 和 k < 10（同样：集合大小将在 [1, k] 范围内）。
  • id 的顺序无关紧要：{1, 5} == {5, 1}。
  • 所有组合都是可能的，但有些可能被排除在外。
  • 所有集合和值都是恒定的，并且只生成一次。没有删除或插入，没有值更新。
  • 一旦生成，唯一发生的操作将是查找。
  • 查找将是频繁且单向的（给定集合，查找值）。
  • 无需对值进行排序（或以其他方式组织） 。

此外，如果“相邻”集合（删除一个 id、添加一个 id、交换一个 id 等）以及“至少包括该集合的所有集合”很容易到达，那将是很好的（但不是强制性的）。

有任何想法吗？

4

3 回答 3

1

使用素数的乘积进行枚举。

  • 一个 -> 2
  • b -> 3
  • c -> 5
  • d -> 7
  • 等等

现在哈希（ab）：= 6，哈希（abc）：= 30

一个很好的副作用是，如果“ab”是“abc”的子集，那么：

hash(abc) % hash(ab) == 0

和

hash(abc) / hash(ab) == hash(c)

坏消息：您可能会遇到溢出，第 100 个素数可能在 1000 左右，而 64 位无法容纳 1000**10。这不会影响作为散列函数的功能；只有子集的东西将无法工作。相同的方法适用于字谜

另一个选项是 Zobrist 散列。它等效于素数方法，但不是素数，而是使用一组固定的（随机）数字，而不是乘法，而是使用 XOR。对于像您这样的固定小型（它需要 << ~70 位）设置，可以调整 zobrist 表以完全避免冲突（产生完美的哈希）。

最后（也是最简单的）方法是使用（100位）位图，并将其视为哈希值（可能在模表大小之后）

一个完全不相关的方法是在位图的位上构建一个决策树。（树的最大深度为 k）在位值上的相关 kD 树

于 2012-11-07T16:28:17.813 回答
0

可能不是最佳解决方案，但您可以执行以下操作：

  1. 使用简单的 IntegerComparator 将集合从最低到最高排序
  2. 将集合的每个项目添加到字符串

所以如果你有 {2,5,9,4} 第一步-> {2,4,5,9}; 第二->“2459”

这样，您将从唯一的集合中获得唯一的字符串。如果您确实需要将它们映射到整数值，则可以在此之后对字符串进行哈希处理。

我能想到的第二种方法是将它们存储在 java Set中，然后简单地将其映射到带有键的HashMapset

于 2012-11-07T16:12:21.090 回答
0

从每组 {1, 6, 87, 89} = {1,5,81,2,0,0,...} {1,2,3,4} = { 1,1, 1,1,0,0,0,0... };

然后使用可变长度编码对每个数字进行二进制编码并连接这些位。

很难比较这些集合（除了前几个相等的位），但是由于集合中不能有很多大的间隔，所有可能的值都可能适合 64 位。（至少 16 位的松弛...）

于 2012-11-07T16:58:55.313 回答