java - 存储整数集以检查某个集合是否已被提及

Question

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

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

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

在这种情况下，速度是一个优先事项，因为在程序停止之前可能会存储多达 100k 个集合(可能更多，但大多数时候可能更少)!关于我应该使用什么数据结构以及我应该如何解决这个问题，有人有什么建议吗？

我目前拥有的是:

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

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

谢谢!

Answer 1

如果你把它分成几 block ，在我看来

• 创建一个集合(生成 6 个数字、排序、字符串化)在 O(1) 中运行
• 检查这个字符串是否存在于哈希集中是 O(1)
• 插入哈希集的时间复杂度为 O(1)

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

您可能会遇到问题，具体取决于随机数的范围。例如假设您只生成 1 和 1 之间的数字，那么显然只有一种可能的结果(“1-1-1-1-1-1”)，从那以后您只会发生碰撞。但是，只要可能序列的数量远大于您生成的元素数量，我就看不出问题。

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

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