Java:整数数组的内存高效存储

Question

前提：这个问题可能已经知道了，我可能使用了错误的措辞，如果是这种情况，请在其他地方咨询我。

快速问题概述：为了避免重复，我必须存储大量整数数组。我正在做以下事情：

LinkedList<int[]> ArraysAlreadyUsed;

使用数组后，我会将其添加到列表中。在使用数组之前，我会查看它是否在列表中。由于我需要使用许多高维数组，我遇到了内存问题。

问题：为了最大限度地减少占用的内存量，什么是最好的方法？有没有一种方法可以用散列字符串来表示这样的数组？这样会更好吗？

Answer 1

创建一个实现equals和hashcode的包装器可能是有意义的，这样您就可以将数组放置在O（1）contains/add的Set中。类似于：

public class IntArray {
  private final int[] array;
  private final int hash;
  public IntArray(int[] array) {
    this.array = array;
    this.hash = Arrays.hashCode(this.array); //cache hashcode for better performance
  }
  @Override
  public int hashCode() {
    return hash;
  }
  @Override
  public boolean equals(Object obj) {
    if (obj == null) return false;
    if (getClass() != obj.getClass()) return false;
    final IntArray other = (IntArray) obj;
    return Arrays.equals(this.array, other.array);
  }
}

然后你可以简单地使用一个集合：

Set<IntArray> arrays = new HashSet<> ();

这将产生较小的开销（每个包装器的估计值小于20字节），但性能将比LinkedList好得多。

如果记忆是你唯一关心的，那么你可以选择int[][]，但那会更痛苦。。。

Answer 2

如果需要检查数据结构中元素的存在，最好的解决方案是使用Map。所以使用HashMap。

元素的检索发生在O（1）中。在列表（LinkedList或ArrayList）中，搜索发生在O（n）中。

就记忆占用而言，链表也是一个糟糕的选择。事实上，对于每个元素，都有一个对上一个元素的引用和一个对下一个图元的引用。

就内存占用而言，最好的解决方案是使用一个int数组（而不是ArrayList），并引用最后插入的id。

Answer 3

使用BitSet代替int[]可能会减少内存占用。