Rust 中具有 HashMap 拥有的节点的链表

Question

我正在尝试用 Rust 构建一堆链表数据结构，但与我见过的其他示例不同，我希望实际节点由 HashMap 拥有。似乎如果 HashMap 拥有节点，那么生命周期不应该成为问题，这应该允许我通过 Option<&List> 而不是 Box<List> 引用列表中的下一个元素（如在中完成）。但是，我收到 mutable/immutable 借用错误。

我的最小示例是：

use std::collections::HashMap;

#[derive(Debug, Default)]
struct List<'a> {
    data: i32,
    child: Option<&'a List<'a>>,
}

fn main() {
    let mut map = HashMap::<i32, List>::new();

    let data = vec![(1, None), (2, Some(1))];

    for (data, child) in data.iter() {
        println!("Inserting {:?} with child {:?}", data, child);
        let new_node = map.entry(*data).or_insert(List {
            data: *data,
            child: None,
        });
        match child {
            Some(child_data) => {
                map.get(child_data).map(|child_node| {
                    new_node.child = Some(child_node);
                });
            }
            None => {}
        }
    }

    println!("Data: {:?}", map);
}

给出了错误

error[E0502]: cannot borrow `map` as mutable because it is also borrowed as immutable
  --> src/main.rs:16:24
   |
16 |         let new_node = map.entry(*data).or_insert(List {
   |                        ^^^^^^^^^^^^^^^^ mutable borrow occurs here
...
22 |                 map.get(child_data).map(|child_node| {
   |                 --- immutable borrow occurs here

error[E0502]: cannot borrow `map` as immutable because it is also borrowed as mutable
  --> src/main.rs:22:17
   |
16 |         let new_node = map.entry(*data).or_insert(List {
   |                        --- mutable borrow occurs here
...
22 |                 map.get(child_data).map(|child_node| {
   |                 ^^^ immutable borrow occurs here
23 |                     new_node.child = Some(child_node);
   |                     -------- mutable borrow later captured here by closure

我的问题是，这个错误是因为我没有正确设置 List 结构，还是我使用 HashMap 的方式导致的，我该如何解决？

Answer 1

错误正确：

如果你有一个引用自身的节点（例如(1, Some(1))），那么new_node和child_node将指向相同的值。这是非法的，因为 new_node 是一个可变的（读取：独占）引用。
HashMap，与 Vec 一样，由数组支持。当 HashMap 填满时，它将重新分配此数组，使所有现有引用无效。
HashMap 允许您删除条目。如果在别处引用已删除的条目，这将导致悬空指针。

这里有几个解决这个问题的办法：

改为存储索引。这是最简单的解决方案，大多数时候都推荐使用。
```
struct List {
  data: i32,
  child: Option<i32>,
}
```

使用像 elsa::FrozenMap 这样的仅追加集合。这只解决了问题 3，但 Box 和 Cell 应该处理其余的问题：

use elsa::FrozenMap;

struct List<'a> {
  data: i32,
  child: Cell<Option<&'a List<'a>>>,
}

fn main() {
  let map = FrozenMap::<i32, Box<List>>::new();

  // ...
}

Rust 中具有 HashMap 拥有的节点的链表

Linked list in Rust with nodes owned by HashMap

linked-list

rust

borrow-checker