TimeMap 时间键值存储为什么用二分？同一个 key 如何按时间查历史值？

简化版

TimeMap 用哈希表把 key 映射到按 timestamp 递增的列表，每次 set(key,value,timestamp) 追加记录；get(key,timestamp) 要找该 key 下“不超过 timestamp 的最大时间戳”，这是右边界问题，用二分查找最后一个 time <= timestamp 的记录。若不存在这样的记录，返回空字符串。

详细版

数据结构是 Map<String, List<Pair<timestamp,value>>>。题目通常保证同一个 key 的 set 时间戳严格递增，所以列表天然有序，不需要每次排序。查询时在该列表里二分，找到最右侧 time <= target 的位置。

class TimeMap {
    Map<String, List<Node>> map = new HashMap<>();

    void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(new Node(timestamp, value));
    }

    String get(String key, int timestamp) {
        List<Node> list = map.get(key);
        if (list == null) return "";
        int lo = 0, hi = list.size(); // 找第一个 > timestamp
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (list.get(mid).time <= timestamp) lo = mid + 1;
            else hi = mid;
        }
        return lo == 0 ? "" : list.get(lo - 1).value;
    }
}

set 是 O(1) 追加，get 是 O(log m)，m 是该 key 的历史版本数。核心坑是要找“不超过目标时间”的历史值，不是必须等于目标时间。

完整版教学

一、TimeMap 查询的是历史快照

TimeMap 的语义不是普通哈希表的覆盖写。普通 Map 只保留最新值，而 TimeMap 要能回答“某个时间点看到的值是什么”。因此同一个 key 需要保存多个版本，每个版本带一个 timestamp。查询时找的是目标时间之前最近的一次写入。

例如依次执行 set("foo","bar",1)、set("foo","bar2",4)。get("foo",3) 应返回 "bar"，因为时间 3 时还没有 "bar2"；get("foo",4) 和 get("foo",5) 返回 "bar2"。这就是“最大的不超过目标时间”的边界查找。

查询	历史版本	返回
get(foo, 0)	无 `time<=0`	""
get(foo, 3)	time=1	bar
get(foo, 5)	time=4	bar2

二、为什么 Map 后面还要接 List

key 的数量可能很多，先用哈希表按 key 定位，可以把问题缩小到单个 key 的版本列表。每个 key 的版本按 timestamp 递增存放，这样查询这个 key 时只在自己的历史记录里二分，不会被其他 key 的记录干扰。

如果把所有记录放进一个全局列表，查询某个 key 时还要过滤 key，复杂度和实现都会变差。Map<key, List<version>> 的分层非常自然：哈希表负责按 key 分桶，二分负责在桶内按时间找边界。

foo -> [(1,bar), (4,bar2), (9,bar3)]
abc -> [(2,x),   (7,y)]

记忆钩子：TimeMap 是“哈希定位 key，二分定位时间”。

三、为什么列表天然有序

题目通常保证对同一个 key 的 set 调用 timestamp 严格递增。这样每次 set 只需要 append 到列表末尾，列表就保持有序。如果没有这个保证，就必须插入时保持有序，或者写入后排序，复杂度会变高。

这个保证是 set O(1) 的来源。比如 foo 的写入时间依次是 1、4、9，append 后自然是升序。查询 6 时，二分最后一个 <=6，得到时间 4 的值。若时间无序，二分的前提就失效。

前提	set 成本	get 成本
同 key 时间递增	O(1) 追加	O(log m)
时间可能乱序	插入 O(m) 或后排序	排好后 O(log m)

四、二分要找的是 upper_bound 再减一

查询 timestamp=t 时，我们需要最大 time <= t。一种稳定写法是先找第一个 time > t 的位置，也就是 upper_bound，然后返回它前一个元素。若 upper_bound 是 0，说明所有时间都大于 t，没有可用历史值。

例如版本时间 [1,4,9]，查询 t=4，第一个 >4 的位置是 2，返回位置 1；查询 t=8，第一个 >8 仍是位置 2，返回位置 1；查询 t=0，第一个 >0 是位置 0，返回空。

times = [1, 4, 9]
t=8 -> upper_bound=2 -> answer index=1 -> time=4
t=0 -> upper_bound=0 -> no answer

五、为什么不是找等于 timestamp

如果只找等于 timestamp，会漏掉大量合法查询。TimeMap 的语义是“在这个时间点之前最后一次写入的值”，不是“这个时间点恰好写入的值”。这和数据库 MVCC 读快照、配置中心历史版本查询很像：读某个版本号时，要找到不超过该版本号的最新记录。

例如只在时间 1 和 4 写入，查询时间 3 没有精确匹配，但答案应该是时间 1 的值。精确查找会返回空，违反题意。把它理解成右边界问题，代码就不会写偏。

// 错误方向：只判断 == timestamp
// 正确方向：找最后一个 <= timestamp

六、复杂度和扩展设计

set 平均 O(1)，因为哈希定位后 append；get 是 O(log m)，m 是该 key 的版本数。总空间是所有写入版本数之和。若历史版本非常多，可以加 TTL、按时间分段、冷热分层，或者压缩连续相同 value。

如果查询非常频繁且 timestamp 单调递增，还可以用游标缓存优化局部查询；但通用面试答案优先保证正确性。不要为了优化把数据结构改成只存最新值，那会丢失历史查询能力。

操作	复杂度	说明
set	O(1) 平均	append 到对应 key 的列表
get	O(log m)	m 为该 key 的版本数
空间	O(total set)	每次写入都保留版本

七、常见误区与追问

误区：用普通 HashMap 覆盖旧值即可。 覆盖会丢失历史版本，无法回答过去时间点的查询。
误区：get 只找 timestamp 相等。 题目要找不超过目标时间的最新值，属于右边界查询。
误区：所有 key 的记录放一起二分。 不同 key 的时间线互相独立，应先按 key 分桶。
追问：为什么 set 可以 O(1)？ 题目保证同 key timestamp 递增，append 后列表仍有序。
追问：如果 timestamp 乱序怎么办？ 要插入到有序位置、使用 TreeMap，或批量排序后再查询。
追问：如何支持删除历史？ 可按 key 的版本列表做过期清理，但要明确删除后历史查询语义会改变。

八、加强记忆

TimeMap 的模型是“每个 key 一条时间线”。哈希表先定位时间线，列表保存递增版本，查询时二分找 <= timestamp 的最后一条记录。实现上常写成找第一个 > timestamp，再取前一个。只要记住它查的是历史快照，不是精确时间等值匹配，边界就会清晰很多。

简化版

详细版