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

Question

我想使用 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);
}

(playground)

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

Answer 1

首先要做的事情是：您的示例可以使用 .or_insert_with() 方法进行简化，该方法采用闭包 returns 在该键处插入的值。

条目模式不可能解决您的问题，因为您首先在条目中可变地借用缓存，然后在匹配（或闭包）中借用缓存。您可以尝试一下，如果您使用 RefCell（它只是将借用从编译时移动到运行时），它会引发恐慌。

要真正解决您的问题，您必须拆分获取和插入值，如下所示：

fn compute(cache: &mut HashMap<u32, u32>, input: u32) -> u32 {
    if let Some(entry) = cache.get(&input) {
        return *entry;
    }

    let res = if input > 2 {
        // Trivial placeholder for an expensive computation.
        compute(cache, input - 1) + compute(cache, input - 2)
    } else {
        0
    };
    cache.insert(input, res);
    res
}

（如果你在夜间使用 ![feature(nll)]，你可以省略 return 并在 if let 分支上使用 else 使它更干净一些。

Answer 2

如何获得工作代码，但我想更深入地了解为什么您的代码无法编译。

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

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 持有的引用无效，违反了 other参考规则。

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

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

How can I mutate other elements of a HashMap when using the entry pattern?

hashmap

rust

borrow-checker

borrowing