java - Java 整数数组的高性能集合类数据结构

Question

我正在寻找一种高性能的数据结构，其行为类似于集合，并且其中的元素始终是整数数组。数据结构只需要实现这个接口(interface)即可:

trait SetX {
  def size:Int
  def add(element:Array[Int])
  def toArray:Array[Array[Int]]
}

集合不应包含重复项，这可以使用 Arrays.equals(int[] a, int[] a2) 来实现 - 即数组的值不能相同。

在创建它之前，我大致了解将有多少元素，但需要调整行为大小，以防元素数量超出最初的想法。元素的长度始终相同，我在创建时就知道它是什么。

当然，我可以使用 Java HashSet(当然包装数组)，但是这是在紧密循环中使用的，而且速度太慢。我研究过 Trove，它工作得很好(通过使用数组但提供 TObjectHashingStrategy)，但我希望由于我的要求如此具体，因此可能有一种更快/更有效的方法来做到这一点。

有没有人遇到过这个或者知道我如何实现这个目标？

上面的特征是 Scala，但我对 Java 库或代码非常满意。

<小时/>

我真的应该说出我在做什么。我基本上是在一个紧密的循环中生成大量的 int 数组，最后我只想看到唯一的数组。我从来不需要从集合或其他任何东西中删除元素。只需向集合中添加大量 int 数组，最后取出唯一的数组即可。

Answer 1

看看prefix trees 。您可以在数组生成期间立即跟踪树结构。在生成结束时，如果生成的数组已存在于集合中，您将得到答案。前缀树比普通的哈希集消耗更少的内存。

如果您正在生成数组并且它们等价的机会不是很小，我怀疑您只是从非常有限的范围内获取数字。它也将简化前缀树的实现。

我确信正确的实现会比使用任何 set 实现来保存实体数组更快。

这种解决方案的缺点是你需要自己实现数据结构，因为它会与代码逻辑深度集成。