Namaran

Code daily. Without assist.

2026-09-05

ttl_cache.rs

use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};

struct Cache {
    map: HashMap<&'static str, (i32, u64)>,
    expiry: BinaryHeap<Reverse<(u64, &'static str)>>,
}

impl Cache {
    fn put(&mut self, key: &'static str, value: i32, expires: u64) {
        self.map.insert(key, (value, expires));
        self.expiry.push(Reverse((expires, key)));
    }

    fn purge(&mut self, now: u64) {
        while self.expiry.peek().is_some_and(|Reverse((e, _))| *e <= now) {
            let Reverse((_, key)) = self.expiry.pop().unwrap();
            self.map.remove(key);
        }
    }
}

有効期限つきのキャッシュ Cache です。put は値と期限を入れ、purge(now) は期限が now 以下の値を消します。期限の早い順に取り出せるよう、期限とキーの組を BinaryHeap にも積んでいます。空の Cache に put("a", 1, 10)、put("b", 2, 12)、put("a", 3, 20) の順に入れて purge(11) を呼び、"a" と "b" の値を {:?} で出すと、いまは None Some(2) です。本来は Some(3) Some(2) です。

Answer

Wrong

let Reverse((_, key)) = self.expiry.pop().unwrap();
self.map.remove(key);

BinaryHeap は大きい値から取り出すヒープですが、Reverse で包んでいるので、期限の小さい組から順に出てきます。purge(11) が最初に取り出すのは (10, "a") で、期限 10 は 11 以下なので、map.remove("a") を呼びます。次の (12, "b") は 11 より後なので、そこで止まります。ここまでは <= の境界も Reverse の向きも正しく働いています。

食い違いは put("a", 3, 20) で生まれています。map.insert は "a" の値を (3, 20) に上書きしますが、ヒープには古い (10, "a") を残したまま (20, "a") を足します。purge はこの古い組をキーだけで信じて消すので、実際に消えるのは期限を 20 に延ばした新しい値 3 です。BinaryHeap から先頭以外の組を消すには retain でヒープ全体をなめ直すしかなく、put のたびにそうするとヒープで期限を管理する意味が薄れます。

Right

let Reverse((expires, key)) = self.expiry.pop().unwrap();
if self.map.get(key).is_some_and(|&(_, e)| e == expires) {
    self.map.remove(key);
}

ヒープから出した組の期限が、map にある今の期限と同じときだけ消します。(10, "a") は map の期限 20 と一致しないので読み捨てられ、"a" は残ります。(20, "a") は、時刻 20 以降の purge で取り出されたときに一致して、そこで消えます。ヒープの組は期限を書き換えるたびに古くなりうる控えなので、消す前に map と照らし合わせる必要があります1。

  1. 消せない要素をヒープに残しておき、取り出したときに古ければ捨てるやり方は、遅延削除(lazy deletion)と呼ばれます。ダイクストラ法で同じ頂点を何度も BinaryHeap に積み、取り出した距離が古ければ飛ばす書き方も同じ形です。