如何高效合并两个Vec<(u32, Vec<u8>)>并去重（允许原地修改）

核心思路 #

避免将完整大对象存入哈希表，改用键到索引的映射定位旧向量中的重复项，直接在原向量上修改，大幅降低内存开销。

实现代码 #

use std::collections::HashMap;

pub fn merge_in_place(old_v: &mut Vec<(u32, Vec<u8>)>, new_v: Vec<(u32, Vec<u8>)>) {
    // 预分配哈希表容量，避免扩容开销
    let mut key_to_idx = HashMap::with_capacity(old_v.len() + new_v.len());
    
    // 构建旧向量的键-索引映射
    for (idx, (key, _)) in old_v.iter().enumerate() {
        key_to_idx.insert(*key, idx);
    }

    // 遍历新向量，处理每个条目
    for (key, mut new_val) in new_v {
        match key_to_idx.get(&key) {
            Some(&idx) => {
                // 交换新旧值，原旧值会被自动drop释放内存
                std::mem::swap(&mut old_v[idx].1, &mut new_val);
            }
            None => {
                let new_idx = old_v.len();
                old_v.push((key, new_val));
                key_to_idx.insert(key, new_idx);
            }
        }
    }
}

优势分析 #

• 内存开销极低：哈希表仅存储u32（键）和usize（索引），无需复制或存储大体积的Vec<u8>，相比原方案内存占用减少90%以上（按单条500KB计算）。
• 原地修改：直接复用原向量的内存空间，避免创建新的大向量，减少内存分配压力。
• 高效操作：哈希表查找、替换、插入均为O(1)平均时间复杂度，整体时间复杂度为O(m + n)（m、n分别为新旧向量条目数）。
• 内存复用：使用std::mem::swap替换值，确保旧内存及时释放，避免冗余占用。

可选优化：基于排序的无哈希表方案 #

如果可以接受向量有序，且对哈希表的内存开销仍有顾虑，可采用排序+二分查找的方案：

pub fn merge_sorted_in_place(old_v: &mut Vec<(u32, Vec<u8>)>, mut new_v: Vec<(u32, Vec<u8>)>) {
    // 对新旧向量按键排序
    old_v.sort_by_key(|&(k, _)| k);
    new_v.sort_by_key(|&(k, _)| k);

    let mut old_idx = 0;
    let mut new_iter = new_v.into_iter().peekable();

    while let Some((new_key, mut new_val)) = new_iter.next() {
        // 二分查找旧向量中的键
        match old_v[old_idx..].binary_search_by_key(&new_key, |&(k, _)| k) {
            Ok(idx) => {
                // 替换重复项
                std::mem::swap(&mut old_v[old_idx + idx].1, &mut new_val);
            }
            Err(idx) => {
                // 插入新条目到正确位置
                old_v.insert(old_idx + idx, (new_key, new_val));
                old_idx += idx + 1;
            }
        }
    }
}

此方案完全无需哈希表，但排序会带来O(m log m + n log n)的时间开销，适合对内存要求极高且条目数增长缓慢的场景。

内容的提问来源于stack exchange，提问作者Ahmet Yazıcı