12

关于小型集合（例如 1-100 个元素）上各种 Java 集合实现的性能是否有任何好的参考，或者有人可以告诉我更多信息？O(1) vs O(log n) 的故事对于这些大小几乎无关紧要，但由于我需要处理数百万个这样的小集合，所以性能确实很重要。我发现的大多数参考资料都没有提到太多。

我需要对这些集合执行以下操作（通常每组只执行几次）：

  • 初始化一个新集合和/或硬拷贝一个旧集合
  • 添加/删除元素
  • 迭代集合
  • 计算hashCode()整个集合的

我认为这些是比较可行的选择（假设比较/散列 T 几乎是免费的）：

  • HashSet<T>：似乎不擅长迭代（因此在hashCode()）
  • TreeSet<T>：似乎有高得离谱的开销
  • LinkedHashSet<T>：完全没有这方面的经验，它有很高的开销吗？
  • ArrayList<T>：本身很快，但不是一组，所以需要丑陋的技巧Collections.sort()......

一般首选以上哪一项？还是我应该写自己的SmallSet<T>课？

4

2 回答 2

4

如果您真的在寻找性能，那么您可以通过自己的测试来帮助您：

  • 您是否经常为它们分配新的？如果是这样，垃圾收集可能比其他情况更相关
  • 您是否只分配一次并需要快速访问？Hashcollisions 将对此产生影响
  • 你经常改变它们吗？

您需要设置一个与您的实际使用类似的测试用例 - 测试足够长的时间以使 GC 启动并在那里看到效果。

如果您检测到它们之间的关键差异，请在每次更新 JVM 后重新运行测试，因为实现可能会发生变化。

在你完成这样的性能测试之前，我会给出我的标准建议：选择可读性最好的选项，并且只有在使用可读性较低的选项有明显的好处时才更改它。代码维护者（可能是未来的你）会为此感谢你。

于 2012-09-10T06:54:23.747 回答
1

这是一个作为数组的小型 Set 实现：

它很容易满足您的需求:)

来源： https ://highlyscalable.wordpress.com/2011/12/29/ultimate-sets-and-maps-for-java-p1/

public class ArraySet {
    private int[] array;
    private int size = 0;

    public ArraySet(int capacity) {
        array = new int[capacity];
        Arrays.fill(array, -1);
    }

    public boolean add(int key) {
        int index = Arrays.binarySearch(array, 0, size, key);
        if (index < 0) {
            int insertIndex = -index-1;

            if(size < array.length - 1) {
                if(insertIndex < size) {
                    System.arraycopy(array, insertIndex, array, insertIndex + 1, size - insertIndex);
                }
                array[insertIndex] = key;
            } else {
                int[] newArray = new int[array.length + 1];
                System.arraycopy(array, 0, newArray, 0, insertIndex);
                System.arraycopy(array, insertIndex, newArray, insertIndex + 1, array.length - insertIndex);
                newArray[insertIndex] = key;
                array = newArray;
            }

            size++;
            return true;
        }
        return false;
    }

    public int get(int position) {
        return array[position];
    }

    public int size() {
        return size;
    }

    public boolean contains(int key) {
        return Arrays.binarySearch(array, key) >= 0;
    }
}
于 2014-12-08T21:37:14.597 回答