存储整数集来检查是否已经提到某个集合

我遇到了一个有趣的问题，我很想得到一些输入。存储整数集来检查是否已经提到某个集合

我有一个程序，生成一组数字（基于一些预定义的条件）。每个集合最多包含6个数字，不必使用1到100之间的整数来唯一）。

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

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

什么我现在是这样的：

排序每组将其存储到字符串的一个HashSet之前。该字符串简单地说是每个有序分隔符集合中的数字。

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

谢谢！

来源

2012-07-14 Mick

如果你有记忆，HashSet是一个不错的选择。 – Starkey 2012-07-14 14:27:40

它可以包含重复项时不是一个集合。称它为multiset或包。 – 2012-07-14 14:48:51

谢谢菲利普，我不确定它的正确术语是什么。 – Mick 2012-07-14 14:54:43

，如果你打破它成片，在我看来那

创建一组（产生6号，排序，字符串化）运行在O（1）
检查，如果在HashSet中存在此字符串为O（1）
插入HashSet的是O（1）

你这样做了N次，它给你为O（n）。 这已经是最佳，你需要接触每个元素一旦反正:)

你威力碰上这取决于你的随机数的范围问题。例如假设你只产生1到1之间的数字，那么显然只有一个可能的结果（“1-1-1-1-1-1”），你将只有碰撞。然而，只要可能的序列数量远远大于您生成的元素数量，我就不会看到问题。

一个提示：如果你知道生成的元素的数量事先将是明智与正确数量的元素（IE的new HashSet<String>(100000));

PS现在与其他答案雨后春笋般冒出来，我想初始化的HashSet请注意，尽管在微观层面上可能有改进的空间（即使用语言特定的技巧），但您的整体方法无法改进。

来源

2012-07-14 14:44:40 kritzikratzi

谢谢Kritz，很高兴知道我在正确的轨道上。我一定会尝试一下，看看它的表现如何。我最担心的是排序，即使每组只有6个元素。 – Mick 2012-07-14 15:07:32

好吧，它只有六个数字，所以它应该非常快。但如果这真是一个麻烦制造者，你可以看看这个stackoverflow问题：http://stackoverflow.com/questions/1866031/generating-sorted-random-ints-without-the-sort-on。 – kritzikratzi 2012-07-14 15:18:33

创建一个类SetOfIntegers
实施，将产生相当独特的哈希一个hashCode（）方法值
使用HashMap来存储你的元素，如认沽（散列值，例如）
使用的containsKey（散列值）来检查相同的哈希值是否已经存在

这样你将避免排序和转换/格式化你的设置。

来源

2012-07-14 14:48:53 mazaneicha

感谢Mazaneicha，我将研究一下hashCode（），我从来没有真正重写过这个函数。你会有任何提示来定义一个基于我的问题范围的散列函数不会有冲突吗？ – Mick 2012-07-14 15:04:08

一如既往，StackOverflow是你的朋友:)看看这篇文章http://stackoverflow.com/questions/27581/overriding-equals-and-hashcode-in-java祝你好运！ – mazaneicha 2012-07-14 15:10:47

这是 - 非常好的资源，谢谢！ – Mick 2012-07-14 15:16:19

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

来源

2012-07-14 14:57:32

谢谢Christophe，这是一个非常有趣的解决方案。我快速浏览了BitSet的javadocs，我有一个问题。此方法是否可以解释重复值？这似乎是独特套装的绝佳解决方案。 – Mick 2012-07-14 15:02:16

是的，对不起，我完全错过了“那不必是唯一的”部分（并没有检查重复67的样本值），因此它不适用于您。然后使用'int []'数组，'java.util.Arrays.sort（array）'和'java.util.Arrays.equals（array1，array2）'静态方法，这是下一个最快/最容易做的事情。 – 2012-07-14 17:07:12

存储整数集来检查是否已经提到某个集合

回答

相关问题