如何复用HashMap持有的值的引用？Rust递归类型借用问题求解

Rust的借用检查器严格禁止同一变量同时存在可变借用与不可变借用。你通过table.get(&Nil)获取了table内部Nil实例的不可变引用，此时table处于不可变借用状态；后续调用table.insert需要对table进行可变借用，且插入参数还依赖之前的不可变引用nil。Rust无法保证可变借用（修改HashMap）过程中旧的不可变引用仍有效（比如HashMap扩容可能移动内部元素，导致旧引用失效），因此触发了借用冲突错误。

要实现“等价对象引用完全一致”的需求，最常用的是字符串池（interner）模式，以下提供两种可行方案：

方案1：用Arc结合Interner（安全且简单） #

虽然你最初想避免智能指针，但Arc可以安全实现引用一致性，且符合Rust内存安全规则。我们可以实现专门的ListInterner，确保每个等价List实例仅创建一次，后续均返回同一个Arc的引用：

use std::collections::HashMap;
use std::sync::Arc;

#[derive(Eq, Hash, PartialEq, Clone)]
enum List {
    Cons(isize, Arc<List>),
    Nil,
}

struct ListInterner {
    map: HashMap<List, Arc<List>>,
}

impl ListInterner {
    fn new() -> Self {
        let mut map = HashMap::new();
        let nil = Arc::new(List::Nil);
        map.insert(List::Nil, nil.clone());
        Self { map }
    }

    // 获取唯一的List引用，等价实例返回的Arc底层指针一致
    fn get(&mut self, list: List) -> Arc<List> {
        if let Some(existing) = self.map.get(&list) {
            existing.clone()
        } else {
            let arc = Arc::new(list.clone());
            self.map.insert(list, arc.clone());
            arc
        }
    }
}

fn main() {
    use List::*;
    let mut interner = ListInterner::new();
    
    let nil = interner.get(Nil);
    let cons1 = interner.get(Cons(1, nil.clone()));
    
    // 验证引用一致性：多次获取同一List，Arc底层指针相同
    let cons1_again = interner.get(Cons(1, nil));
    assert!(Arc::ptr_eq(&cons1, &cons1_again));
}

通过Arc::ptr_eq可直接验证底层实例的指针是否一致，满足你后续类似std::ptr::eq的需求。

方案2：无智能指针的unsafe实现（需手动保证内存安全） #

若坚持不用智能指针，需手动管理内存并确保引用不会失效。可以用Vec存储所有唯一实例（仅允许向末尾添加元素，禁止删除或移动），结合HashMap映射值到索引，再通过索引获取引用：

use std::collections::HashMap;

#[derive(Eq, Hash, PartialEq, Clone, Copy)]
enum ListIdx {
    Cons(isize, usize),
    Nil,
}

#[derive(Eq, Hash, PartialEq)]
enum List {
    Cons(isize, &'static List),
    Nil,
}

struct ListInterner {
    storage: Vec<Box<List>>,
    map: HashMap<ListIdx, usize>,
}

impl ListInterner {
    fn new() -> Self {
        let mut storage = Vec::new();
        let mut map = HashMap::new();
        
        // 初始化Nil实例
        let nil = Box::new(List::Nil);
        let nil_ptr = &*nil as *const List;
        storage.push(nil);
        map.insert(ListIdx::Nil, 0);
        
        // 强制转换为'static，需保证storage仅添加元素、绝不修改已有元素
        unsafe {
            let _ = &*nil_ptr as &'static List;
        }
        
        Self { storage, map }
    }

    fn get(&mut self, idx: ListIdx) -> &'static List {
        if let Some(&index) = self.map.get(&idx) {
            unsafe {
                &*self.storage[index] as &'static List
            }
        } else {
            let list = match idx {
                ListIdx::Cons(val, inner_idx) => {
                    let inner = self.get(ListIdx::Nil);
                    List::Cons(val, inner)
                }
                ListIdx::Nil => List::Nil,
            };
            let boxed = Box::new(list);
            let ptr = &*boxed as *const List;
            let index = self.storage.len();
            self.storage.push(boxed);
            self.map.insert(idx, index);
            unsafe {
                &*ptr as &'static List
            }
        }
    }
}

fn main() {
    let mut interner = ListInterner::new();
    let nil = interner.get(ListIdx::Nil);
    let cons1 = interner.get(ListIdx::Cons(1, 0));
    
    // 验证引用一致性
    let cons1_again = interner.get(ListIdx::Cons(1, 0));
    assert!(std::ptr::eq(cons1, cons1_again));
}

注意：此方案使用unsafe，必须严格保证storage仅向末尾添加元素，绝不删除或移动已有元素，否则'static引用会变成悬垂引用，引发未定义行为。

内容的提问来源于stack exchange，提问作者user3310334