在使用条目模式时,如何改变HashMap的其他元素？

Question

我想用a HashMap来缓存一个依赖于地图中其他条目的昂贵计算.条目模式仅提供对匹配值的可变引用,但不提供对其余的引用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);
}

(游乐场)

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

Answer 1

hellow已经展示了如何获取工作代码,但我想更深入地了解一下代码无法编译的原因.

您提出的代码无法进行静态验证,以确保内存安全.您的递归调用完全有可能尝试访问相同的索引.查看这个简化代码的一种可能性:

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();
    }
}

现在有两个可变引用指向相同的值,违反了引用规则.

另外,如果使用内部调用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阻止您在程序中引入两种可能类型的内存不安全; 就像它的设计目的一样.