如何基于Java Collections实现高效无冗余指针的MultiSet

现有方案优化 #

你当前自定义Element<E>类搭配Set<Element<E>>的方案可以直接简化为使用原生HashMap<E, Integer>存储元素与对应频次，无需自定义包装类，既符合Java Collections的使用规范，也能避免冗余封装，增删查操作均为O(1)时间复杂度，满足高效要求：

• 键存储去重后的元素本身，值存储对应频次
• 额外维护全局size变量统计总元素数，避免每次遍历求和
• 维护modCount（对应你代码里的numeroModifiche）实现迭代器的 fail-fast 机制

迭代器实现 #

你可以根据需求选择两种迭代器语义：

1. 遍历所有元素（重复元素按频次返回多次） #

迭代过程中逐个返回元素，某元素频次为N则连续返回N次，和普通List的迭代行为一致：

@Override
public Iterator<E> iterator() {
    return new Iterator<E>() {
        private final Iterator<Map.Entry<E, Integer>> entryIter = elements.entrySet().iterator();
        private Map.Entry<E, Integer> currentEntry;
        private int remainingCount;
        private int expectedModCount = modCount;

        @Override
        public boolean hasNext() {
            checkForComodification();
            if (remainingCount > 0) return true;
            while (entryIter.hasNext()) {
                currentEntry = entryIter.next();
                remainingCount = currentEntry.getValue();
                if (remainingCount > 0) return true;
            }
            return false;
        }

        @Override
        public E next() {
            checkForComodification();
            if (!hasNext()) throw new NoSuchElementException();
            remainingCount--;
            return currentEntry.getKey();
        }

        private void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    };
}

2. 遍历去重元素（仅返回每个元素一次，可单独获取频次） #

这种迭代器适合需要批量处理去重元素的场景，你可以自定义Multiset.Entry<E>类返回元素和对应频次，或者直接返回Map.Entry<E, Integer>即可。

完整核心实现示例 #

import java.util.*;

public class HashMultiSet<E> implements Iterable<E> {
    private final Map<E, Integer> elements = new HashMap<>();
    private int size = 0;
    private int modCount = 0;

    // 添加元素，可指定添加数量
    public boolean add(E e, int count) {
        if (e == null) throw new NullPointerException("元素不能为null");
        if (count < 0) throw new IllegalArgumentException("添加数量不能为负");
        if (count == 0) return false;
        if (size + count >= Integer.MAX_VALUE) throw new IllegalArgumentException("总元素数超出上限");

        elements.put(e, elements.getOrDefault(e, 0) + count);
        size += count;
        modCount++;
        return true;
    }

    // 移除元素，可指定移除数量
    public boolean remove(E e, int count) {
        if (e == null) throw new NullPointerException("元素不能为null");
        if (count < 0) throw new IllegalArgumentException("移除数量不能为负");
        if (count == 0 || !elements.containsKey(e)) return false;

        int current = elements.get(e);
        if (current <= count) {
            elements.remove(e);
            size -= current;
        } else {
            elements.put(e, current - count);
            size -= count;
        }
        modCount++;
        return true;
    }

    // 获取元素频次
    public int getFrequency(E e) {
        return elements.getOrDefault(e, 0);
    }

    // 获取总元素数
    public int size() {
        return size;
    }

    // 判空
    public boolean isEmpty() {
        return size == 0;
    }

    // 清空集合
    public void clear() {
        elements.clear();
        size = 0;
        modCount++;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private final Iterator<Map.Entry<E, Integer>> entryIter = elements.entrySet().iterator();
            private Map.Entry<E, Integer> currentEntry;
            private int remainingCount;
            private final int expectedModCount = modCount;

            @Override
            public boolean hasNext() {
                checkForComodification();
                if (remainingCount > 0) return true;
                while (entryIter.hasNext()) {
                    currentEntry = entryIter.next();
                    remainingCount = currentEntry.getValue();
                    if (remainingCount > 0) return true;
                }
                return false;
            }

            @Override
            public E next() {
                checkForComodification();
                if (!hasNext()) throw new NoSuchElementException();
                remainingCount--;
                return currentEntry.getKey();
            }

            private void checkForComodification() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
        };
    }
}

原有Set<Element<E>>方案适配说明 #

如果需要维持原有自定义Element的设计，只需要将迭代器中遍历Map.Entry的逻辑替换为遍历Set<Element<E>>即可，其他逻辑完全一致，取元素调用getItem()，取频次调用getFrequency()即可。

内容的提问来源于stack exchange，提问作者Leonardo Migliorelli