【搞定算法】哈希表增加 setAll 功能

清疚 2021-11-23 09:22 187阅读 0赞

> 博主秋招提前批已拿百度、字节跳动、拼多多、顺丰等公司的offer，可加微信：**pcwl\_Java** 一起交流秋招面试经验，可获得博主的秋招简历和复习笔记。

> `题目：哈希表常见的三个操作是 put、get 和 containsKey，而且这三个操作的时间复杂度为 O(1)。现在想加一个 setAll 功能，就是把所有记录的 value 都设成统一的值。请设计并实现这种有 setAll 功能的哈希表，并且 put、get、containsKey 和 setAll 四个操作的时间复杂度都为 O(1)。`

** 分析：**

设置一个 setAll 和时间戳，如果查出来的 value 的时间戳比 setAll  的时间戳早，则以 setAll  为准，否则以 value 为准。

因为时间复杂度是 O(1)，所以肯定不能每次都去更新，那就利用时间戳，在每次获取的时候去对比 key 的当前时间和 setAll 时间哪个更薪就取哪个。

public class SetAllHashMap {
    
        public static class MyValue<V>{
            private V value;
            private long time;  // 时间戳
    
            public MyValue(V value, long time){
                this.value = value;
                this.time = time;
            }
    
            public V getValue(){
                return this.value;
            }
    
            public long getTime(){
                return this.time;
            }
        }
    
        public static class MyHashMap<K, V>{
            private HashMap<K, MyValue<V>> baseMap;
            private long time;
            private MyValue<V> setAll;
    
            public MyHashMap(){
                this.baseMap = new HashMap<K, MyValue<V>>();
                this.time = 0;
                this.setAll = new MyValue<V>(null, - 1);
            }
    
            public boolean containsKey(K key){
                return this.baseMap.containsKey(key);
            }
    
            public void put(K key, V value){
                this.baseMap.put(key, new MyValue<V>(value, this.time++));
            }
    
            public void setAll(V value){
                this.setAll = new MyValue<V>(value, this.time++);
            }
    
            public V get(K key){
                if(this.containsKey(key)){
                    if(this.baseMap.get(key).getTime() > this.setAll.getTime()){
                        // 以自身值为最新
                        return this.baseMap.get(key).getValue();
                    }else{
                        // 以setAll为最新
                        return this.setAll.getValue();
                    }
                }else{
                    return null;
                }
            }
        }
    }