设计空间高效的Snapshot Set：面试题解决方案及多迭代器处理问询

核心思路是通过版本号追踪元素的生命周期，避免在创建迭代器时复制整个元素列表，用时间换空间：给每个元素记录添加版本和删除版本，迭代器仅保存创建时的快照版本，遍历底层哈希表时过滤出快照时刻存在的元素。

一、单迭代器场景实现 #

设计思路 #

1. 底层用哈希表存储元素，每个元素绑定addedVersion（添加时的全局版本号）和deletedVersion（删除时的全局版本号，初始为无穷大）。
2. 维护全局递增的currentVersion，每次增删操作都会推进版本号。
3. 创建迭代器时，记录当前的currentVersion作为快照版本，同时限制同一时间只能存在一个活跃迭代器。
4. 迭代时遍历哈希表，仅返回addedVersion ≤ 快照版本且deletedVersion > 快照版本的元素（即快照时刻存在的元素）。

代码实现（Java） #

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;

public class SnapshotSet {
    private static class Entry {
        int addedVersion;
        int deletedVersion;

        Entry(int added) {
            this.addedVersion = added;
            this.deletedVersion = Integer.MAX_VALUE;
        }
    }

    private Map<Integer, Entry> map = new HashMap<>();
    private int currentVersion = 0;
    private Integer activeSnapshotVersion = null; // 单迭代器场景：记录当前活跃迭代器的快照版本

    public void add(int num) {
        currentVersion++;
        Entry entry = map.get(num);
        if (entry == null) {
            map.put(num, new Entry(currentVersion));
        } else {
            // 恢复已删除的元素
            if (entry.deletedVersion <= currentVersion) {
                entry.deletedVersion = Integer.MAX_VALUE;
            }
        }
    }

    public void remove(int num) {
        currentVersion++;
        Entry entry = map.get(num);
        if (entry != null && entry.deletedVersion > currentVersion) {
            entry.deletedVersion = currentVersion;
        }
    }

    public boolean contains(int num) {
        Entry entry = map.get(num);
        return entry != null && entry.deletedVersion > currentVersion;
    }

    public Iterator<Integer> iterator() {
        if (activeSnapshotVersion != null) {
            throw new IllegalStateException("Only one iterator is allowed in single-iterator mode");
        }
        currentVersion++;
        int snapshotVersion = currentVersion;
        activeSnapshotVersion = snapshotVersion;

        return new Iterator<Integer>() {
            private Iterator<Map.Entry<Integer, Entry>> mapIterator = map.entrySet().iterator();
            private Integer nextElement = null;

            @Override
            public boolean hasNext() {
                if (nextElement != null) {
                    return true;
                }
                while (mapIterator.hasNext()) {
                    Map.Entry<Integer, Entry> entry = mapIterator.next();
                    Entry e = entry.getValue();
                    if (e.addedVersion <= snapshotVersion && e.deletedVersion > snapshotVersion) {
                        nextElement = entry.getKey();
                        return true;
                    }
                }
                // 迭代结束，清除活跃迭代器标记
                activeSnapshotVersion = null;
                return false;
            }

            @Override
            public Integer next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                Integer res = nextElement;
                nextElement = null;
                return res;
            }
        };
    }
}

二、多迭代器场景扩展 #

设计思路 #

1. 取消单迭代器的限制，改用集合activeSnapshots记录所有活跃迭代器的快照版本。
2. 当迭代器遍历完成（或被GC回收）时，从activeSnapshots中移除对应的版本号。
3. 添加cleanUpDeletedElements方法：定期清理那些所有活跃迭代器都已“错过”的已删除元素（即元素的deletedVersion ≤ 所有活跃快照的最小版本），避免内存泄漏。

代码实现（Java） #

import java.util.*;
import java.util.NoSuchElementException;

public class MultiSnapshotSet {
    private static class Entry {
        int addedVersion;
        int deletedVersion;

        Entry(int added) {
            this.addedVersion = added;
            this.deletedVersion = Integer.MAX_VALUE;
        }
    }

    private Map<Integer, Entry> map = new HashMap<>();
    private int currentVersion = 0;
    private Set<Integer> activeSnapshots = new HashSet<>();

    public void add(int num) {
        currentVersion++;
        Entry entry = map.get(num);
        if (entry == null) {
            map.put(num, new Entry(currentVersion));
        } else {
            if (entry.deletedVersion <= currentVersion) {
                entry.deletedVersion = Integer.MAX_VALUE;
            }
        }
    }

    public void remove(int num) {
        currentVersion++;
        Entry entry = map.get(num);
        if (entry != null && entry.deletedVersion > currentVersion) {
            entry.deletedVersion = currentVersion;
        }
    }

    public boolean contains(int num) {
        Entry entry = map.get(num);
        return entry != null && entry.deletedVersion > currentVersion;
    }

    public Iterator<Integer> iterator() {
        currentVersion++;
        int snapshotVersion = currentVersion;
        activeSnapshots.add(snapshotVersion);

        return new Iterator<Integer>() {
            private Iterator<Map.Entry<Integer, Entry>> mapIterator = map.entrySet().iterator();
            private Integer nextElement = null;
            private boolean finished = false;

            @Override
            public boolean hasNext() {
                if (finished) {
                    return false;
                }
                if (nextElement != null) {
                    return true;
                }
                while (mapIterator.hasNext()) {
                    Map.Entry<Integer, Entry> entry = mapIterator.next();
                    Entry e = entry.getValue();
                    if (e.addedVersion <= snapshotVersion && e.deletedVersion > snapshotVersion) {
                        nextElement = entry.getKey();
                        return true;
                    }
                }
                // 迭代结束，清理快照版本并触发元素清理
                finished = true;
                activeSnapshots.remove(snapshotVersion);
                cleanUpDeletedElements();
                return false;
            }

            @Override
            public Integer next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                Integer res = nextElement;
                nextElement = null;
                return res;
            }

            // 防止迭代器未遍历完就被GC，导致快照版本残留
            @Override
            protected void finalize() throws Throwable {
                if (!finished) {
                    activeSnapshots.remove(snapshotVersion);
                    cleanUpDeletedElements();
                }
                super.finalize();
            }
        };
    }

    // 清理所有活跃迭代器都已无法访问的已删除元素
    private void cleanUpDeletedElements() {
        if (activeSnapshots.isEmpty()) {
            // 无活跃迭代器，直接清空所有已删除元素
            map.entrySet().removeIf(entry -> entry.getValue().deletedVersion != Integer.MAX_VALUE);
        } else {
            int minActiveVersion = Collections.min(activeSnapshots);
            // 移除所有删除版本早于等于最小活跃快照的元素
            map.entrySet().removeIf(entry -> entry.getValue().deletedVersion <= minActiveVersion);
        }
    }
}

关键优势 #

• 空间效率：创建迭代器时无需复制元素列表，仅维护版本号和少量元数据，空间复杂度为O(m + k)（m为元素数量，k为活跃迭代器数量），远优于O(n)的复制方案。
• 正确性：严格保证迭代器仅返回快照时刻存在的元素，后续增删操作不影响已有迭代器的遍历结果。
• 内存可控：多迭代器场景下通过定期清理机制，避免已删除元素长期占用内存。

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