hashmap - 使用入口模式时如何改变 HashMap 的其他元素？

Question

我想使用 HashMap 来缓存依赖于 map 中其他条目的昂贵计算。条目模式仅提供对匹配值的可变引用，但不提供对 HashMap 其余部分的引用。我非常感谢有关解决这个(不正确的)玩具示例的更好方法的反馈:

use std::collections::HashMap;
use std::collections::hash_map::Entry::{Occupied, Vacant};

fn compute(cache: &mut HashMap<u32, u32>, input: u32) -> u32 {
    match cache.entry(input) {
        Vacant(entry) => if input > 2 {
            // Trivial placeholder for an expensive computation.
            *entry.insert(compute(&mut cache, input - 1) +
                          compute(&mut cache, input - 2))
        } else {
            0
        },
        Occupied(entry) => *entry.get(),
    }
}

fn main() {
    let mut cache = HashMap::<u32, u32>::new();
    let foo = compute(&mut cache, 12);
    println!("{}", foo);
}

( playground )

上面代码片段的问题是 cache.entry 不可变地借用了 cache，但我也想更新 cache。

Answer 1

hellow has shown如何获得工作代码，但我想更深入地探讨为什么您的代码无法编译。

您提出的代码不能被静态验证为内存安全的。您的递归调用完全有可能尝试访问相同的索引。查看此简化代码以了解一种可能性:

use std::collections::{hash_map::Entry, HashMap};

fn compute(cache: &mut HashMap<u32, u32>) {
    if let Entry::Vacant(_entry) = cache.entry(42) {
        let _aliased_mutable_reference = cache.get_mut(&42).unwrap();
    }
}

这现在有两个指向同一个值的可变引用，违反了the rules of references .

此外，如果内部调用使用了 entry 而它不存在怎么办？

use std::collections::{hash_map::Entry, HashMap};

fn compute(cache: &mut HashMap<u32, u32>) {
    if let Entry::Vacant(entry1) = cache.entry(42) {
        if let Entry::Vacant(entry2) = cache.entry(41) {
            entry2.insert(2);
            entry1.insert(1);
        }
    }
}

现在，当您通过 entry2 将值插入映射时，映射可能会重新分配底层内存，使 entry1 持有的引用无效，违反 其他引用规则。

Rust 阻止了您在程序中引入两种可能的内存不安全类型；就像它的设计目的一样。