1

我遇到了一个有趣的问题，我很想得到一些意见。

我有一个程序可以生成一组数字（基于一些预定义的条件）。每个集合最多包含 6 个数字，这些数字不必是唯一的，整数范围从 1 到 100）。

我想以某种方式存储创建的每个集合，以便我可以快速检查以前是否生成了具有完全相同数字（顺序无关紧要）的某个集合。

在这种情况下，速度是一个优先事项，因为在程序停止之前可能存储了多达 100k 组（可能更多，但大多数时间可能更少）！有人对我应该使用什么数据结构以及我应该如何解决这个问题有任何建议吗？

我目前拥有的是这样的：

在将每个集合存储到字符串的 HashSet 之前对其进行排序。字符串只是排序集中的每个数字，带有一些分隔符。

例如，集合 {4, 23, 67, 67, 71} 将被编码为字符串“4-23-67-67-71”并存储到 HashSet 中。然后对于生成的每个新集合，对其进行排序、编码并检查它是否存在于 HashSet 中。

谢谢！

4

3 回答 3

2

只需为每个集合使用java.util.BitSet，使用 set(int bitIndex) 方法将整数添加到集合中，您无需对任何内容进行排序，并在向其添加新 BitSet 之前检查 HashMap 是否已存在 BitSet ，真的会非常快。如果速度很重要，请不要为此目的使用 value 和 toString 的排序。

于 2012-07-14T14:57:32.887 回答
2

如果你把它拆成碎片，在我看来

  • 创建一个集合（生成 6 个数字、排序、字符串化）在 O(1) 中运行
  • 检查此字符串是否存在于哈希集中是 O(1)
  • 插入哈希集是 O(1)

你这样做 n 次，这给了你 O(n)。 这已经是最佳选择，因为无论如何您都必须触摸每个元素一次:)

根据随机数的范围，您可能会遇到问题。例如，假设您只生成 1 和 1 之间的数字，那么显然只有一种可能的结果（“1-1-1-1-1-1”），并且从那里开始只会发生碰撞。但是，只要可能的序列数量远大于您生成的元素数量，我就没有问题。

一个提示：如果您事先知道生成元素的数量，那么使用正确数量的元素初始化散列集是明智的（即new HashSet<String>( 100000 ) );

ps 现在出现了其他答案，我想指出，虽然在微观层面上可能有改进的空间（即使用特定于语言的技巧），但您的整体方法无法改进。

于 2012-07-14T14:44:40.680 回答
2
  1. 创建一个类 SetOfIntegers
  2. 实现一个 hashCode() 方法，该方法将生成合理唯一的哈希值
  3. 使用 HashMap 存储您的元素，例如 put(hashValue,instance)
  4. 使用 containsKey(hashValue) 检查相同的 hashValue 是否已经存在

这样，您将避免对集合进行排序和转换/格式化。

于 2012-07-14T14:48:53.240 回答