Vec 与 HashMap 内存布局对比

写 unsafe Rust 的时候，有个问题看起来简单，但踩到就是生产事故：

你把一个集合里的引用存到另一个字段，觉得"只要我不改集合，地址就稳"。

对 Vec 来说，这是对的。对 HashMap 来说，文档可没这么说。

这篇文章讲清楚为什么——从内存布局讲到 Miri 怎么检测这种 UB。

Vec 的内存布局：为什么它有稳定地址承诺

先看 Vec 的真实结构。标准库里的定义（简化版）长这样：

pub struct Vec<T> {
    buf: RawVec<T>,
    len: usize,
}

struct RawVec<T> {
    ptr: Unique<T>,
    cap: usize,
    alloc: Global,
}

ptr 指向堆上的一块连续内存，len 是当前用了多少，cap 是总容量。关键点：Vec 这个 struct 本身只有三个 usize 大小的字段，元素存在堆上，不在 Vec 里面。

Rust 标准库文档在 Vec::as_ptr 里明确写了：

“The caller must ensure that the vector outlives the pointer this function returns, or else it will end up pointing to garbage.”

更重要的是：Vec 保证永远不会使用"小向量优化"（small vector optimization）。也就是说，哪怕你创建空 Vec，它也不会把元素内联存到栈上。只有当容量为0时，指针才是 dangling，但一旦分配了堆内存，那块内存的地址就稳定了——直到触发 reallocation。

什么会触发 reallocation？只有这几种情况：

  1. push/insert 导致 len == cap，需要扩容
  2. 手动调用 shrink_to_fit
  3. 调用 into_raw_parts 之类消耗 Vec 的方法

只要你不干这几件事，堆上的地址就稳如狗。

HashMap 的真实结构：为什么没有同等承诺

再来看 HashMap。标准库用的是 hashbrown 的实现，核心结构是 RawTable：

struct RawTable<T> {
    ctrl: NonNull<u8>,           // 控制字节数组（描述每个 slot 状态）
    bucket_mask: usize,          // 数组大小 - 1，用于哈希掩码
    items: usize,                // 当前元素数量
    growth_left: usize,          // 还能插入多少个才需要扩容
}

注意：HashMap 里没有显式的指针指向堆。ctrl 指向的是一块连续的内存区域，里面包含控制字节和实际的键值对。整体布局大概长这样：

[ctrl0, ctrl1, ..., ctrlN, pad, | K0, V0, K1, V1, ... KN, VN ]
 ^                            ^
 ctrl pointer                 键值对从这里开始

和 Vec 的关键区别：

  1. HashMap 的扩容策略不同：load factor 超过 0.875 就会触发 rehash，所有元素重排
  2. 删除会留下 tombstone：remove 操作不会立即压缩，只是标记为已删除
  3. 没有文档承诺地址稳定：标准库只说 HashMap::with_capacity(n) 能容纳 n 个元素不重新分配，但没说元素地址不变

HashMap 的文档里找遍了，没有类似 Vec “元素存储位置"的保证。

一段看似合法但实际 UB 的代码

来看个具体例子。假设你想实现一个带索引的字符串解析器：

use std::collections::HashMap;

struct Parser<'a> {
    data: HashMap<String, String>,
    current: Option<&'a str>,  // 指向 data 里某个 value
}

impl<'a> Parser<'a> {
    fn new() -> Self {
        Parser {
            data: HashMap::new(),
            current: None,
        }
    }

    fn set_key(&mut self, key: &str) {
        // 假设 key 一定存在
        self.current = self.data.get(key).map(|v| v.as_str());
    }
}

这段代码在 safe Rust 里根本写不出来——借用检查器会阻止你。但如果你用 unsafe 绕过：

use std::collections::HashMap;

struct BadParser {
    data: HashMap<String, String>,
    current: *const str,  // 原始指针，绕过借用检查
}

impl BadParser {
    fn new() -> Self {
        BadParser {
            data: HashMap::new(),
            current: std::ptr::null(),
        }
    }

    unsafe fn set_key(&mut self, key: &str) {
        if let Some(v) = self.data.get(key) {
            self.current = v.as_str();  // 存下指向 HashMap value 的指针
        }
    }

    unsafe fn get(&self) -> Option<&str> {
        if self.current.is_null() {
            None
        } else {
            Some(&*self.current)  // 解引用
        }
    }
}

问题来了：如果之后对 data 做 insert，可能触发 rehash，所有的 value 都会被搬到新地址。这时候 current 就成了 dangling pointer。

用 Miri 检测这种 UB

Miri 检测到悬垂指针错误

Miri 是 Rust 的未定义行为检测工具。我们来写个能触发问题的例子：

use std::collections::HashMap;

fn main() {
    let mut map: HashMap<u32, String> = HashMap::with_capacity(2);
    map.insert(1, "hello".to_string());
    
    // 获取指向 value 的原始指针
    let ptr: *const String = map.get(&1).unwrap();
    
    // 触发 rehash
    map.insert(2, "world".to_string());
    map.insert(3, "foo".to_string());  // 触发扩容
    
    // 这里的 ptr 已经悬空了！
    unsafe {
        let _val = &*ptr;  // UB！
    }
}

运行 cargo miri run：

$ cargo miri run
error: Undefined Behavior: pointer to alloc1403 is out-of-bounds
  --> src/main.rs:15:20
   |
15 |         let _val = &*ptr;
   |                    ^^^^^ pointer to alloc1403 is out-of-bounds
   |
   = help: this indicates a bug in the program: it performed an invalid operation

Miri 明确告诉你：悬垂指针解引用是 UB。

换个用 Vec 的版本验证一下同样的问题：

fn main() {
    let mut vec = Vec::with_capacity(2);
    vec.push("hello".to_string());
    
    let ptr: *const String = &vec[0];
    
    vec.push("world".to_string());
    vec.push("foo".to_string());  // 触发扩容，ptr 失效
    
    unsafe {
        let _val = &*ptr;  // 同样 UB
    }
}

Miri 也会报错。区别是：Vec 的文档明确告诉你什么时候会 reallocation，HashMap 可没说。

Pin 能解决吗？

有人说：用 Pin 啊！

Pin 是 Rust 1.32 引入的，目的是标记"这个值不会动”。但它不是魔法：

use std::pin::Pin;
use std::marker::PhantomPinned;

struct SelfRef {
    data: String,
    ptr: *const u8,
    _pin: PhantomPinned,  // 标记为 !Unpin
}

impl SelfRef {
    fn new(text: &str) -> Pin<Box<Self>> {
        let mut boxed = Box::new(SelfRef {
            data: text.to_string(),
            ptr: std::ptr::null(),
            _pin: PhantomPinned,
        });
        
        let ptr = boxed.data.as_ptr();
        boxed.ptr = ptr;
        
        Box::into_pin(boxed)
    }
}

注意：这里 Pin 的是 Box 里的 SelfRef，不是 String 本身。Box 保证堆地址不变，String 的堆缓冲区地址也不变，所以 ptr 指向的 data 内部是稳定的。

但如果你 Pin 的是 HashMap：

let map = HashMap::new();
let pinned = Pin::new(&map);  // 完全没用！

Pin 只能阻止 HashMap 结构体本身被移动，管不了 HashMap 内部 rehash 时搬动元素。Pin 没有魔法，它改变不了集合的内部行为。

正确的做法：稳定地址方案

如果你确实需要自引用结构，有几种方案：

方案1：Box 包裹

use std::collections::HashMap;

struct StableIndex<'a> {
    // Box 保证堆地址稳定
    data: HashMap<String, Box<String>>,
    current: Option<&'a str>,
}

HashMap 搬动的是 Box 指针（usize 大小），Box 指向的堆内存不动。

方案2：用专门的 arena crate

use generational_arena::{Arena, Index};

struct WithArena {
    data: Arena<String>,
    current: Option<Index>,  // 代际索引，不是指针
}

arena 保证元素地址稳定直到删除，Index 带 generation 能检测 use-after-free。

方案3：owning_ref 或 self_cell

use self_cell::self_cell;

self_cell! {
    struct Parser {
        owner: String,
        #[covariant]
        dependent: str,  // 指向 owner 内部
    }
}

self_cell 用 unsafe 封装了自引用逻辑，保证 API 安全。

总结

集合地址稳定保证reallocation 触发条件适合自引用？
Vec有文档承诺push 超过 cap适合（需稳定不扩容）
String有文档承诺push_str 超过 cap适合
HashMap无承诺load factor > 0.875不适合
BTreeMap无承诺节点分裂/合并不适合

关键逻辑：safe Rust 里你本来就做不到这种危险操作。但写 unsafe 时，文档没写的保证就不是保证。今天的实现细节可能明天就改。

写 unsafe Rust 之前，先用 Miri 跑一遍。它能救你一命。

想跟着学更多 Rust 底层原理？关注「全栈之巅-梦兽编程」公众号，每周更新。

也欢迎了解 梦兽编程 AI 编程助手服务 ，帮你把 AI 编程工具用到生产环境。

常见问题

Vec 和 HashMap 的 reallocation 有什么区别？

Vec 只有扩容时才 realloc，且你可以用 with_capacity 预先分配。HashMap 的 rehash 由 load factor 触发（约 87.5%），插入到满 map 时几乎必然触发，且无法预测具体时机。

Pin<Box> 能让 HashMap 元素地址稳定吗？

不能。Pin 保证的是 Box 堆内存不动，但 Box 里 HashMap 的内部 rehash 不受 Pin 影响。元素还是会被搬。

现在的 HashMap 真的会内联存储吗？

当前stdlib的 HashMap 不会。但如果未来引入 small-map 优化（比如 1-2 个元素内联），符合稳定性承诺。依赖非文档行为就是给自己埋雷。