（6）设计一个TimeMap

一、描述

• 设计一个TimeMap，基于key value的
• 支持两类操作set(string key, string value, int timestamp)，get(string key, int timestamp)
• 在get(string key, int timestamp)方法中，返回一个值，满足set(string key, int timestamp_prev)  timestamp_prev <= timestamp，其中timestamp_prev为最大的timestamp_prev。

 

二、思路

要借助TreeMap。

TreeMap大概描述

• 根据key排序的map
• 有firstkey()接口，就是排在第一的key
• 有floorEntry()接口，其实就是largerest key。

 

三、code

package algorithm;

import java.util.HashMap;
import java.util.TreeMap;

/**
 * Created by adrian.wu on 2019/2/18.
 */
public class TimeMap {
    private HashMap<String, TreeMap<Integer, String>> map = new HashMap<>();

    private static final String ES = "";

    public void set(String key, String value, int ts) {
        TreeMap<Integer, String> tm = map.get(key) == null ? new TreeMap<>() : map.get(key);
        tm.put(ts, value);
        map.put(key, tm);
    }

    public String get(String key, int ts){
        if(map.get(key) == null) return ES;
        TreeMap<Integer, String> tm = new TreeMap<>();
        if (tm.firstKey() > ts) return ES;
        return tm.floorEntry(ts).getValue();
    }
}