如何实现set()、get()、setAll()均为O(1)时间复杂度的数据结构

我尝试编写一个能够在**O(1)**时间复杂度内完成所有值setAll操作的数据结构。
我的实现代码如下：

public class myData {
    boolean setAllStatus = false;
    HashMap<Integer, Integer> hasMap = new HashMap<>();
    int setAllValue = 0;
    int count = 0;
    public void set(int key, int value) {
        hasMap.put(key, value);
    }
    public int get(int key) {
        if (setAllStatus) {
            if (hasMap.get(key) != null) {
                if (count == hasMap.size()) {
                    return setAllValue;
                } else {
                    // do something
                }
            } else {
                throw new NullPointerException();
            }
        } else {
            if (hasMap.get(key) == null) {
                throw new NullPointerException();
            } else {
                return hasMap.get(key);
            }
        }
    }
    public void setAll(int value) {
        setAllStatus = true;
        setAllValue = value;
        count = hasMap.size();
    }
    public static void main(String[] args) {
        myData m = new myData();
        m.set(1, 4);
        m.set(4, 5);
        System.out.println(m.get(4)); // 5
        m.setAll(6);
        System.out.println(m.get(4)); // 6
        m.set(8, 7);
        System.out.println(m.get(8)); // 7
    }
}

当前代码在首次设置键值对、调用setAll将所有值设为指定值时可正常运行，但在执行setAll操作后插入新的键值对时，无法确定对应的处理逻辑。

原有方案的缺陷 #

靠count和哈希表size比对的判断逻辑存在根本问题：setAll操作执行后，如果对哈希表做新增、删除键的操作，size的变化无法准确区分「哪些键是setAll之前写入的、应该返回setAll的全局值」和「哪些键是setAll之后写入的、应该返回实际存储值」。比如setAll时表内有2个键，之后删除1个旧键再新增1个新键，表size还是2，原有判断逻辑会直接返回全局值，把新写入的键值判断错误。

正确实现方案 #

用全局版本戳的思路实现，所有操作时间复杂度均为O(1)，不需要遍历哈希表，也不会受新增、删除操作的干扰：

• 废弃原有setAllStatus、count标记，新增两个全局变量：
  • globalVersion：全局版本号，初始值为0，每次调用setAll时自增1
  • globalValue：存储setAll设置的全局值
• 哈希表不直接存储Integer类型的值，而是存储带版本标记的条目，每个条目包含两个属性：实际存储的业务值value、写入该键时的全局版本号version
• 各方法逻辑调整为：
  • set(key, value)：写入键值对时，条目的version设置为当前的globalVersion，value设置为传入的参数值
  • setAll(value)：仅需将globalVersion自增1，同时将globalValue赋值为传入的参数即可，不需要操作哈希表内的已有数据
  • get(key)：如果key不存在直接抛出空指针；如果key存在，对比条目的version和当前globalVersion：两者相等说明该键是最后一次setAll之后写入的，返回条目自身存储的value；两者不相等说明该键是最后一次setAll之前写入的，直接返回globalValue

修正后的可运行代码如下：

public class MyData {
    // 存储条目的内部类
    private static class Entry {
        int value;
        int version;
        public Entry(int value, int version) {
            this.value = value;
            this.version = version;
        }
    }

    private final HashMap<Integer, Entry> hashMap = new HashMap<>();
    private int globalVersion = 0;
    private int globalValue = 0;

    public void set(int key, int value) {
        hashMap.put(key, new Entry(value, globalVersion));
    }

    public int get(int key) {
        Entry entry = hashMap.get(key);
        if (entry == null) {
            throw new NullPointerException();
        }
        if (entry.version == globalVersion) {
            return entry.value;
        }
        return globalValue;
    }

    public void setAll(int value) {
        globalVersion++;
        globalValue = value;
    }

    public static void main(String[] args) {
        MyData m = new MyData();
        m.set(1, 4);
        m.set(4, 5);
        System.out.println(m.get(4)); // 输出5
        m.setAll(6);
        System.out.println(m.get(4)); // 输出6
        m.set(8, 7);
        System.out.println(m.get(8)); // 输出7
        m.set(1, 10);
        System.out.println(m.get(1)); // 输出10
        System.out.println(m.get(4)); // 输出6
    }
}

这个方案无论多少次调用setAll、中间穿插多少次新增、修改、删除操作，判断逻辑都不会出错，所有操作的时间复杂度都保持O(1)。

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