java - 避免两者的惯用方法：内存泄漏和 ConcurrentModificationException

Question

我写了一个递归算法，基本上如下所示。我正在使用一个Map<Integer, Long>作为穷人的包/多组。为了避免ConcurrentModificationException我从不从地图中删除/添加键。它工作正常，并且在这种情况下，没有删除出现的事实元素键0无关紧要。

PS：我知道它无法扩展，这只是解决代码出现日 1 第 1 部分和第 2 部分的一种有趣/通用的方式。

Optional<Integer> solve(final Map<Integer, Long> intOccurrences, final int sum, final int addendsCount) {
    if (addendsCount < 1) return Optional.empty();
    if (addendsCount == 1) {
        return intOccurrences.getOrDefault(sum, 0L) > 0 ? Optional.of(sum) : Optional.empty();
    }

    for (val entry : intOccurrences.entrySet()) {
        if (entry.getValue() < 1) continue;
        val left = entry.getKey();
        val delta = sum - left;

        changeCountOf(intOccurrences, left, -1);

        val result = solve(intOccurrences, delta, addendsCount - 1);

        if (result.isPresent()) {
            return Optional.of(left * result.get());
        }

        changeCountOf(intOccurrences, left, 1);
    }

    return Optional.empty();

}

由于我已经好几年没有写过 java 了，所以我决定通过实现一个IntBag. 我已经IntBag使用Map<Integer, Count>实现Iterable<Occurrence>. 自定义迭代器由地图的entrySet迭代器支持并跳过0出现的值。

一切都很好，但是虽然我当前的IntBag实现可以很好地使用递归回溯算法，但它也会泄漏内存，因为0永远不会清理出现的条目。

问题

1. 是否有另一种方法来实现一个不会遭受此内存泄漏问题的包，同时避免 a CurrentModificationException（不涉及复制整个包）？

2. 如果我当前的实现有意义，那么清理条目的合适方法是什么？例如，我想过在某个阈值之后运行 GC 进程，但我不确定哪个阈值有意义，等等。

3. 我想在迭代期间将条目标记为删除，然后在所有迭代完成后进行清理，但我认为如果我实现Iterable. 如果我只实现，我可能会解决一些forEach问题，在最外面的forEach退出之后进行清理（在迭代期间仍然需要忽略 0 次出现的值）。

4. 以上都不能解决递归迭代时添加新值的问题。除了现在复制整个包之外，我想不出一种可行的方法吗？希望在迭代时添加项目不是很常见我猜......

目前的IntBag实现看起来像这样（没有实现添加/删除，因为它不是必需的）：

final class IntBag implements Iterable<IntBag.Occurrence> {
    private final Map<Integer, Count> occurrenceMap;

    private IntBag(final Map<Integer, Count> occurrenceMap) {
        this.occurrenceMap = occurrenceMap;
    }

    boolean contains(final int value) {
        return !occurrenceMap.getOrDefault(value, Count.ZERO).isZero();
    }

    @Override
    public Iterator<Occurrence> iterator() {
        return new IntBag.BagIterator(occurrenceMap.entrySet().iterator());
    }

    static IntBag of(final List<Integer> values) {
        return new IntBag(countInts(values));
    }

    private static Map<Integer, Count> countInts(final List<Integer> values) {
        return values.stream().collect(groupingBy(Function.identity(), reducing(Count.ZERO, e -> Count.ONE, Count::merge)));
    }

    private static final class BagIterator implements Iterator<Occurrence> {
        private final Iterator<Entry<Integer, Count>> entryIterator;
        private Entry<Integer, Count> nextEntry;

        BagIterator(@NonNull final Iterator<Entry<Integer, Count>> entryIterator) {
            this.entryIterator = entryIterator;
            initNext();
        }

        @Override
        public boolean hasNext() {
            return nextEntry != null;
        }

        @Override
        public Occurrence next() {
            if (!hasNext()) throw new NoSuchElementException();
            val currentEntry = nextEntry;
            initNext();
            return new Occurrence(currentEntry);
        }

        private void initNext() {
            while(entryIterator.hasNext()) {
                val maybeNext = entryIterator.next();
                if (maybeNext.getValue().isZero()) continue;
                nextEntry = maybeNext;
                return;
            }

            nextEntry = null;
        }
    }

    @RequiredArgsConstructor
    static final class Occurrence {
        private final Map.Entry<Integer, Count> entry;

        int value() {
            return entry.getKey();
        }

        long count() {
            return entry.getValue().value();
        }

        void merge(final long modifier) {
            entry.setValue(entry.getValue().merge(modifier));
        }
    }

    private static final class Count {
        private final long value;

        private Count(final long value) {
            this.value = Math.max(0L, value);
        }

        long value() {
            return value;
        }

        boolean isZero() {
            return value == 0L;
        }

        Count merge(@NonNull final Count modifier) {
            return merge(modifier.value());
        }

        Count merge(final long modifier) {
            return new Count(value + modifier);
        }

        static final Count ZERO = Count.of(0L);
        static final Count ONE = Count.of(1L);
        static Count of(final long value) {
            return new Count(value);
        }
    }
}

标签： javaiterator