3

我正在尝试在 Rust 中实现一个简单的分桶哈希表（仅供练习）。哈希表结构定义为：

pub struct BucketedHashTable<K: Hash, V> {
    buckets: Vec<Bucket<K, V>>,
    size: usize,
}

Bucket我对单链接堆栈的简单实现在哪里。

put在表（ , remove, ）的几乎所有方法中，get我都将获取要插入密钥的存储桶（从中删除，查找），因此我为此提取了一个方法：

    fn pick_bucket(&mut self, key: K) -> &mut Bucket<K, V> {
        let mut hasher = DefaultHasher::new();
        key.hash(&mut hasher);
        let hash = hasher.finish() as usize;
        let index = hash % self.buckets.len();
        &mut self.buckets[index]
    }

我返回对存储桶的引用，因为我不想将它移出buckets哈希表的 Vec。我返回一个可变引用，因为我要改变返回的存储桶（例如，在向其中插入一个新条目（键值对）时）。

上面的代码可以编译。

但是，如果我去掉中间变量index并计算[]括号内的索引，如下所示：

    fn pick_bucket(&mut self, key: K) -> &mut Bucket<K, V> {
        let mut hasher = DefaultHasher::new();
        key.hash(&mut hasher);
        let hash = hasher.finish() as usize;
        &mut self.buckets[hash % self.buckets.len()]
    }

我会得到这个借用错误：

error[E0502]: cannot borrow `self.buckets` as immutable because it is also borrowed as mutable
  --> src\lib.rs:30:34
   |
26 |     fn pick_bucket(&mut self, key: K) -> &mut Bucket<K, V> {
   |                    - let's call the lifetime of this reference `'1`
...
30 |         &mut self.buckets[hash % self.buckets.len()]
   |         -------------------------^^^^^^^^^^^^^^^^^^-
   |         |    |                   |
   |         |    |                   immutable borrow occurs here
   |         |    mutable borrow occurs here
   |         returning this value requires that `self.buckets` is borrowed for `'1`

我认为上面的两个代码片段是等价的。它们有什么不同，为什么第一个编译，为什么第二个不编译？

编辑：我认为self.buckets第一个代码片段中的不可变借用超出了范围，并在带有 的行的末尾“无效” let index = ...;，因此当方法返回时，没有对self.bucketsleft 的共享引用；在第二个片段中，self.buckets生命的不可变借用直到方法返回（因此在那一刻共享和可变引用共存）。如果这是正确的，为什么会这样？为什么在第二种情况下self.buckets到达]括号时，不可变借用不会“无效”，而是为整个表达式（整个返回线）而存在？

4

2 回答 2

2

我相信你已经在你的编辑中准确地找出了问题。在第一个示例中，self.buckets是不可变借用的，然后借用在语句的末尾结束。在第二个示例中，self.buckets在同一个语句中可变地借用，然后不可变地借用。这是不允许的。

self.buckets.len()是一个临时的，它的生命周期规则（丢弃范围）在Temporary Scopes中有解释：

除了生命周期延长之外，表达式的临时范围是包含该表达式的最小范围，并且是以下之一：

  • 整个函数体。
  • 一份声明。
  • if、while 或循环表达式的主体。
  • if 表达式的 else 块。
  • if 或 while 表达式或匹配守卫的条件表达式。
  • 匹配臂的表达式。
  • 惰性布尔表达式的第二个操作数。

注释中进一步解释了这一点：

在函数体的最终表达式中创建的临时变量在函数体中绑定的任何命名变量之后被删除，因为没有更小的封闭临时范围。

所以self.buckets.len()借用一直持续到函数的末尾（在函数体之后，甚至在语句完成之后）。但是更容易认为它持续到语句的末尾（无论如何它都会如此）。

在单个语句中没有创建“子表达式”放置范围。理论上这可能是可能的，但 Rust 并没有那么激进。

于 2021-12-29T20:58:00.660 回答
0

问题是，self当self.buckets.len(). 但随后在您返回 a 的同一行中&mut。检查这个更简单的例子：

struct MyVec(Vec<u8>);

impl MyVec {
    fn get_last_mut(&mut self) -> &mut u8 {
        &mut self.0[self.0.len() - 1]
    }
}

操场

编译器不够聪明，无法知道哪个借用引用优先。您可以像以前一样强制优先级（之前使用一个）：

struct MyVec(Vec<u8>);

impl MyVec {
    fn get_last_mut(&mut self) -> &mut u8 {
        let i = self.0.len() - 1;
        &mut self.0[i]
    }
}

操场

请注意，您不能&在拥有 a 的同时使用 a &mut，因此要么在之前使用它，要么在再次使用 a 之前将其&mut删除&。

于 2021-12-29T20:49:32.333 回答