如何确保HashPriorityQueue迭代时无修改？求实现优化建议

我实现了**HashPriorityQueue**类，它结合了HashMap（用于快速查找）和PriorityQueue（用于数据排序）。

我做的另一项改进是保证有序迭代。因为PriorityQueue无法保证这一点，JavaDocs明确说明：

iterator()方法返回的迭代器不保证按特定顺序遍历优先级队列的元素。

我还希望保证有序迭代，且该类能在多线程环境下工作。

为实现HashPriorityQueue类，我已完成以下步骤：

• 继承HashMap类。
• 添加private字段PriorityQueue。
• 重写所有会修改HashMap值的方法，以便在队列中添加或移除值。
• 添加队列相关方法：poll()和peek()。
• 为该新数据结构实现自定义Iterator，内部复制队列并在next()方法中使用poll()来维持有序迭代。

代码:

public class HashPriorityQueue<K, V> extends HashMap<K, V> implements Iterable<AbstractMap.SimpleEntry<K, V>>{
    private final PriorityQueue<K> queue;

    /* CONSTRUCTORS */

    public HashPriorityQueue(Comparator<K> comparator) {
        queue = new PriorityQueue(comparator);
    }

    public HashPriorityQueue() {
        queue = new PriorityQueue();
    }


    /* QUEUE METHODS */

    public AbstractMap.SimpleEntry<K, V> poll() {
        K key = queue.poll();
        V val = remove(key);
        return new AbstractMap.SimpleEntry<K, V>(key, val);
    }

    public AbstractMap.SimpleEntry<K, V> peek() {
        K key = queue.peek();
        V val = get(key);
        return new AbstractMap.SimpleEntry<K, V>(key, val);
    }

    @Override
    public V remove(Object key) {
        queue.remove(key);
        return super.remove(key);
    }

    public V remove(AbstractMap.SimpleEntry<V, K> entry) {
        return remove(entry.getKey());
    }


    @Override
    public V put(K key, V value) {
        queue.add(key);
        return super.put(key, value);
    }

    @Override
    public Iterator<AbstractMap.SimpleEntry<K, V>> iterator() {
        return new PriorityIterator();
    }



    private class PriorityIterator implements Iterator<AbstractMap.SimpleEntry<K, V>>{
        PriorityQueue<K> keys;
        K cursor;

        public PriorityIterator() {
            keys = new PriorityQueue<>(HashPriorityQueue.this.queue);
        }

        @Override
        public boolean hasNext() {
            return !keys.isEmpty();
        }

        @Override
        public AbstractMap.SimpleEntry<K, V> next() {
            cursor = keys.poll();
            V v = HashPriorityQueue.this.get(cursor);
            return new AbstractMap.SimpleEntry<>(cursor,v);
        }

        @Override
        public void remove() {
            HashPriorityQueue.this.remove(cursor);
        }
    }
}

当前，迭代器会创建队列的副本，通过从副本队列中poll()键来进行迭代，对应的value通过map的get()方法获取。该迭代器无法感知map的任何结构性或非结构性修改。

问题解答：如何确保集合迭代过程未被修改？ #

用boolean类型的isChanged标志是可行思路，但更标准的做法是参考Java集合框架的**快速失败（fail-fast）**机制，具体实现：

1. 添加volatile int modCount字段（多线程环境下保证可见性），每次对集合进行结构性修改（put、remove、clear等）时，将modCount自增。
2. 迭代器初始化时，记录当前modCount为expectedModCount。
3. 在迭代器的next()、hasNext()、remove()方法中，检查modCount是否等于expectedModCount，若不等直接抛出ConcurrentModificationException。

这种方式比单纯的isChanged标志更精确，能区分多次修改场景，也符合Java开发者的使用习惯。

其他优化建议 #

1. 多线程安全性增强：
   • 当前依赖的HashMap和PriorityQueue均非线程安全，即使加了modCount仍会出现数据不一致。可替换为ConcurrentHashMap+PriorityBlockingQueue，或在所有操作方法上添加synchronized锁保证原子性。
2. 迭代器健壮性提升：
   • next()方法中从map获取value可能返回null（键已被移除），需处理该情况，比如抛出NoSuchElementException或跳过无效键。
   • remove()方法需判断cursor是否为null，避免调用remove()前未执行next()导致空指针异常。
3. 改用组合而非继承：
   • 继承HashMap会暴露不必要的方法（如putAll、clear），未重写的修改方法会导致队列与map数据不一致。建议内部持有HashMap和PriorityQueue实例，仅暴露所需方法，更符合面向对象设计原则。
4. 处理重复键问题：
   • 当前put方法插入已存在的键时，queue.add(key)会重复添加该键，导致后续poll()多次返回同一键。需在put时判断：若键已存在，先从队列移除旧键再添加（或不添加，因键本身无变化）。
5. 泛型安全优化：
   • 带比较器的构造方法中，queue = new PriorityQueue(comparator);未指定泛型，应改为queue = new PriorityQueue<>(comparator);消除未检查警告。

内容的提问来源于stack exchange，提问作者Kfir Ettinger