设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。
实现 TimeMap 类：
TimeMap()初始化数据结构对象void set(String key, String value, int timestamp)存储键key、值value，以及给定的时间戳timestamp。String get(String key, int timestamp)- 返回先前调用
set(key, value, timestamp_prev)所存储的值，其中timestamp_prev <= timestamp。 - 如果有多个这样的值，则返回对应最大的
timestamp_prev的那个值。 - 如果没有值，则返回空字符串（
""）。
- 返回先前调用
示例：
输入：
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
输出：
[null, null, "bar", "bar", null, "bar2", "bar2"]
解释：
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1); // 存储键 "foo" 和值 "bar" ，时间戳 timestamp = 1
timeMap.get("foo", 1); // 返回 "bar"
timeMap.get("foo", 3); // 返回 "bar", 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，所以唯一的值位于时间戳 1 处（即 "bar"） 。
timeMap.set("foo", "bar2", 4); // 存储键 "foo" 和值 "bar2" ，时间戳 timestamp = 4
timeMap.get("foo", 4); // 返回 "bar2"
timeMap.get("foo", 5); // 返回 "bar2"
提示：
1 <= key.length, value.length <= 100key和value由小写英文字母和数字组成1 <= timestamp <= 107set操作中的时间戳timestamp都是严格递增的- 最多调用
set和get操作2 * 105次
Related Topics
题解
HashMap配合List的二分查找来找到指定的值。当然也可以用HashMap配合BST二叉搜索树来实现，或者更进一步AVL树，树的搜索表现应当比二分法来得更好些。
不过其实我对这题有点点疑问
- 看了下timestamp一定是递增的嘛？感觉不应该是恒定递增的，常见的在业务中，并发条件下时间12345和时间12346发起的两个请求，因为网络或者硬件等因素可能是12346的请求先到服务器的，并不能预先假设这个时间一定是递增的。
- 题目中要求“如果有多个这样的值，则返回对应最大的 timestamp_prev 的那个值”，题目中感觉说的模棱两可，并没有明确说明是对应当前key下的前一个时间的值，还是不限定当前key下的前一个时间的值
先放个二分法查找的在这，配合二叉树的写法回头加上
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
//leetcode submit region begin(Prohibit modification and deletion)
class TimeMap {
class Node {
String val;
int timestamp;
public Node(String val, int timestamp) {
this.val = val;
this.timestamp = timestamp;
}
}
HashMap<String, List<Node>> map;
/** Initialize your data structure here. */
public TimeMap() {
map = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
Node node = new Node(value,timestamp);
if (map.containsKey(key)){
map.get(key).add(node);
}else{
List<Node> list = new ArrayList<>();
list.add(node);
map.put(key,list);
}
}
public String get(String key, int timestamp) {
if (!map.containsKey(key)){
return "";
}
String val = "";
// for (int i = 0; i < map.get(key).size(); i++) {
// if (map.get(key).get(i).timestamp <= timestamp){
// val = map.get(key).get(i).val;
// }
// if (map.get(key).get(i).timestamp > timestamp){
// break;
// }
// }//直接遍历查找超时了，放弃
int left = 0, right = map.get(key).size()-1;
while (left <= right){
int mid = (left + right) >> 1;
if (map.get(key).get(mid).timestamp <= timestamp){
left = mid + 1;
val = map.get(key).get(mid).val;
}else{
right = mid-1;
}
}
return val;
}
}
