12.2

设计有setAll功能的哈希表

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

思路

setAll是把所有数据设置为同一个值,但是时间复杂度是 O(1)

• 普通做法
  遍历hashMap然后把值都修改成同一个值
  这样的时间复杂度一定不是O(1)

• O(1)做法
  因此提出时间戳的概念，就是setAll变为单独一个部分，加上一个时间戳，普通数据也加上一个时间戳
  取数据的时候要判断是从setAll取还是从普通数据取，这个取决于对应的时间戳

在普通的hashMap中value就是一个普通的值，
而这里把普通数据value设置为一个带有时间戳的value，即一个新的数据结构，包含时间戳和value
每次对于添加value都要更新时间戳

代码

//value值是带有时间戳的
public static class MyValue<V>{
	private V value;
	private long time;
	public MyValue(V value, long time){
		this.time = time;
		this.value = value;
	}
	public V getValue(){
		return this.value;
	}
	public long getTime(){
		return this.time;
	}
}


public static class MyHashMap<K, V>{
	//hashMap的value是带有时间戳的value
	private HashMap<K, MyValue<V>> baseMap;
	private long time;
	//setAll变为单独的区域
	private MyValue<V> setAll;
	//初始化
	public MyHashMap(){
		this.baseMap = new HashMap<K, MyValue<V>>();
		this.time = 0;
		this.setAll = new MyValue<V>(null, -1);
	}
	
	//普通的containsKey
	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++));
	}
	
	//将setAll单独设置成为一个区域，而不是改变所有的值
	public void setAll(V value){
		this.setAll = new MyValue<V>(value, time++);
	}
	
	//取值时，要根据时间戳来判断取出setAll还是myValue
	public V get(K key){
		if(this.containsKey(key)){
			if(this.baseMap.get(key).time > this.setAll.time){
				return this.baseMap.get(key).getValue();
			}else{
				return this.setAll.getValue();
			}
		}else{
			return null;
		}
		
	}
}