Vec and HashMap memory layout comparison

When writing unsafe Rust, there’s a problem that seems simple but can cause production disasters:

You store a reference from one collection into another field, thinking “as long as I don’t modify the collection, the address is stable.”

For Vec, this is true. For HashMap, the documentation makes no such promise.

This article explains why—from memory layout to how Miri detects this kind of UB.

Vec’s Memory Layout: Why It Has Stable Address Guarantees

Let’s look at Vec’s actual structure. The simplified definition from the standard library looks like this:

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

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

ptr points to a contiguous block of heap memory, len is how much is currently used, and cap is the total capacity. Key point: The Vec struct itself only has three usize-sized fields; elements are stored on the heap, not inside the Vec.

The Rust standard library documentation in Vec::as_ptr explicitly states:

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

More importantly: Vec guarantees it will never use “small vector optimization” (SSO). This means even if you create an empty Vec, it won’t inline elements on the stack. Only when capacity is 0 is the pointer dangling—but once heap memory is allocated, that memory’s address is stable until reallocation is triggered.

What triggers reallocation? Only these situations:

  1. push/insert causes len == cap, requiring growth
  2. Manually calling shrink_to_fit
  3. Methods that consume Vec like into_raw_parts

As long as you don’t do these, the heap address is rock solid.

HashMap’s Real Structure: Why There’s No Equivalent Guarantee

Now let’s look at HashMap. The standard library uses the hashbrown implementation, with the core structure being RawTable:

struct RawTable<T> {
    ctrl: NonNull<u8>,           // Control byte array (describes each slot's state)
    bucket_mask: usize,          // Array size - 1, used for hash masking
    items: usize,                // Current element count
    growth_left: usize,          // How many more elements can be inserted before growth
}

Note: HashMap has no explicit pointer to the heap. ctrl points to a contiguous memory region that contains both control bytes and actual key-value pairs. The overall layout looks roughly like this:

[ctrl0, ctrl1, ..., ctrlN, pad, | K0, V0, K1, V1, ... KN, VN ]
 ^                            ^
 ctrl pointer                 Key-value pairs start here

Key differences from Vec:

  1. Different growth strategy: Load factor exceeding 0.875 triggers rehash, moving all elements
  2. Deletion leaves tombstones: remove doesn’t immediately compact, just marks as deleted
  3. No documented address stability guarantee: The standard library only says HashMap::with_capacity(n) can hold n elements without reallocation, but doesn’t say element addresses stay the same

Searching through the HashMap documentation, you’ll find no guarantee similar to Vec’s “element storage location” promise.

Here’s a concrete example. Suppose you want to implement an indexed string parser:

use std::collections::HashMap;

struct Parser<'a> {
    data: HashMap<String, String>,
    current: Option<&'a str>,  // Points to a value in data
}

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

    fn set_key(&mut self, key: &str) {
        // Assume key definitely exists
        self.current = self.data.get(key).map(|v| v.as_str());
    }
}

This code can’t even be written in safe Rust—the borrow checker will stop you. But if you bypass it with unsafe:

use std::collections::HashMap;

struct BadParser {
    data: HashMap<String, String>,
    current: *const str,  // Raw pointer, bypassing borrow check
}

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();  // Store pointer to HashMap value
        }
    }

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

The problem: if you later insert into data, it may trigger rehash, moving all values to new addresses. At this point, current becomes a dangling pointer.

Using Miri to Detect This UB

Miri detecting dangling pointer error

Miri is Rust’s undefined behavior detection tool. Let’s write an example that triggers the problem:

use std::collections::HashMap;

fn main() {
    let mut map: HashMap<u32, String> = HashMap::with_capacity(2);
    map.insert(1, "hello".to_string());
    
    // Get raw pointer to value
    let ptr: *const String = map.get(&1).unwrap();
    
    // Trigger rehash
    map.insert(2, "world".to_string());
    map.insert(3, "foo".to_string());  // Triggers growth
    
    // ptr is now dangling!
    unsafe {
        let _val = &*ptr;  // UB!
    }
}

Run 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 explicitly tells you: dereferencing a dangling pointer is UB.

Let’s verify the same problem with 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());  // Triggers growth, ptr invalid
    
    unsafe {
        let _val = &*ptr;  // Same UB
    }
}

Miri will also error. The difference: Vec’s documentation explicitly tells you when reallocation happens, HashMap doesn’t.

Can Pin Solve This?

Some say: use Pin!

Pin was introduced in Rust 1.32 to mark “this value won’t move.” But it’s not magic:

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

struct SelfRef {
    data: String,
    ptr: *const u8,
    _pin: PhantomPinned,  // Mark as !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)
    }
}

Note: Here Pin is on the Box containing SelfRef, not the String itself. Box guarantees heap address stability, and String’s heap buffer address is also stable, so ptr pointing inside data is stable.

But if you Pin HashMap:

let map = HashMap::new();
let pinned = Pin::new(&map);  // Completely useless!

Pin can only prevent the HashMap struct itself from being moved, it can’t control HashMap’s internal rehash moving elements. Pin has no magic; it can’t change collection internals.

Correct Approaches: Stable Address Solutions

If you really need self-referential structures, here are some approaches:

Solution 1: Box Wrapping

use std::collections::HashMap;

struct StableIndex<'a> {
    // Box guarantees heap address stability
    data: HashMap<String, Box<String>>,
    current: Option<&'a str>,
}

HashMap moves Box pointers (usize size), but Box points to stable heap memory.

Solution 2: Use Dedicated Arena Crates

use generational_arena::{Arena, Index};

struct WithArena {
    data: Arena<String>,
    current: Option<Index>,  // Generational index, not pointer
}

Arenas guarantee element address stability until deletion, and Index has generation to detect use-after-free.

Solution 3: owning_ref or self_cell

use self_cell::self_cell;

self_cell! {
    struct Parser {
        owner: String,
        #[covariant]
        dependent: str,  // Points inside owner
    }
}

self_cell uses unsafe to encapsulate self-reference logic while providing a safe API.

Summary

CollectionAddress Stability GuaranteeReallocation TriggerSafe for Self-Reference?
VecDocumented promisepush beyond capYes (if stable no growth)
StringDocumented promisepush_str beyond capYes
HashMapNo promiseload factor > 0.875No
BTreeMapNo promisenode split/mergeNo

Key logic: In safe Rust, you couldn’t do this dangerous operation anyway. But when writing unsafe, if it’s not in the documentation, it’s not a guarantee. Today’s implementation detail might change tomorrow.

Always run Miri before shipping unsafe Rust. It can save you.

Want to learn more Rust internals? Follow the “Full Stack Summit - Mengshou Programming” WeChat official account for weekly updates.

Also check out Mengshou Programming AI Programming Assistant Service to help you use AI programming tools in production.

FAQ

Is storing references in Vec always safe?

It’s safe as long as the reference points to heap data. Rust explicitly guarantees Vec won’t inline elements. But if the reference points to a temporary stack variable, that’s another story.

Will HashMap really use inline storage?

Not currently. But Rust’s stability promise is “if it’s not in the docs, it’s not guaranteed,” so you can’t assume future implementations won’t optimize this way.

Can I use BTreeMap instead of HashMap?

Same logic—BTreeMap also has no documented promise that keys/values don’t overlap with the struct’s address. Choose based on performance needs, not to solve this inline problem.