Java

Question

问题

我正在开发一款需要最小化内存分配和 GC activity 的游戏。为此，我需要一个具有非重复值的集合，以最大限度地减少访问操作期间的内存分配。我准备通过稍微降低性能来弥补改进"garbage generation".

考虑过的方案（包括废弃的供参考）

扩展 ArrayList 以包括对 add(E e) 的重复检查，如果值存在则不执行任何操作。（这也可能包括其他方法）
使用 HashSet（废弃） - 元素的迭代导致新迭代器的实例化，这违反了访问期间最小内存分配的要求。
将 HashSet 转换为 ArrayList（废弃） - 创建比 HashSet 迭代更多的内存分配。

问题

扩展 ArrayList 以防止重复值是一种以最少的内存分配实现非重复集合的明智方法吗？我应该考虑其他方法吗？

备注

我见过的消除 ArrayList 中重复项的最受推荐的解决方案是指使用 HashSet 或其他对象实例化，它们违反了我的最小内存分配要求。我能想到的唯一实现是 ArrayList 的基本 "for iteration" 检查每个现有元素的附加值是否相等。

Class NonDuplicateList extends ArrayList{
    @Override
    boolean add(E e){
        for(int i = 0; i < this.size(); i++){
            if(this.get(i).equals(e)
                return false;
        }
        return super.add(e);
    }
}

Answer 1

你这里的不是 List: List.add，根据合同，必须 return true:

Returns:

true (as specified by Collection.add(E))

你可以抛出一个 IllegalArgumentException 来代替：

Throws:

IllegalArgumentException - if some property of this element prevents it from being added to this list

但是必须处理异常是很恶心的。

此外，扩展 ArrayList 很少是正确的做法：在这种情况下，ArrayLists 允许您将任何元素添加到末尾（前提是有足够的内存），所以你的 class 不会是 Liskov-substitutable.

另外，当然，您必须覆盖所有其他允许您向列表添加元素的方法：add（其他重载）、addAll、set, subList 和 listIterator 等上的所有方法。这很难正确执行。

而是使用组合:

class NonDuplicateList<E> {
    private final List<E> delegate = new ArrayList<>();

    boolean add(E e){
        // contains is easier! ArrayList.contains does not use an iterator.
        if (delegate.contains(e)) return false;
        return delegate.add(e);
    }

    // Other methods you may require
}

通过像这样定义您自己的class，您不需要遵守任何不是您自己设计的契约；并且您可以公开一组更小的方法，从而大大减少维护列表的无重复项属性的工作量。

Java - 没有迭代器分配的无重复集合

Java - no-duplicate collection without iterator allocation

memory-management

game-engine