集合类型

选择集合时先列出操作：怎样查找、在哪一端增删、是否要求顺序、是否需要范围扫描，以及键值大小与数量分布。单独比较一个 O(1) 与 O(log n)，会漏掉哈希、字符串比较、分配和缓存访问的成本。

按操作速查

以下复杂度把一次键比较或哈希的成本单独留给具体类型；摊销不表示每一次操作都同样快。

HashSet/BTreeSet 对应只存键的需求；固定数量可使用数组。是否使用内联小容器，应依据实际容量分布与所选库规则，不存在通用“少于 20 项就零堆分配”的阈值。标准库集合概览

Vec：容量不是长度

Vec 包含指针、长度和容量信息，但字段顺序不作为稳定 C 布局承诺。它自身可以在栈上、堆上或其他对象内部，不能一概称为“栈上的 24 字节”。零大小元素与零容量还具有特殊分配行为。

with_capacity(n) 请求至少 n 项容量，不创建 n 个已初始化 T。reserve(additional) 按当前长度加 additional 计算需求，不是直接设置最终容量。普通 push 在容量足够时无需扩容；扩容策略与增长倍数不是应用可依赖的永久公式。Vec 保证

fn main() {
    let mut values = Vec::with_capacity(8);
    assert_eq!(values.len(), 0);
    assert!(values.capacity() >= 8);
    values.extend([10, 20, 30]);
    values.clear();
    assert!(values.is_empty());
    assert!(values.capacity() >= 8); // clear 不要求归还缓冲
}

可能扩容的操作使缓存裸指针失去有效性，安全借用规则会限制冲突访问。即使没扩容，insert、remove、sort 等也可能改变索引对应的对象；“地址没变”和“仍是原先那个逻辑元素”不是同一件事。

swap_remove 可用末项替换被删位置，避免保持顺序所需的移动，代价是顺序改变。需要长期稳定标识时，应设计 ID、代际索引或合适的间接存储，不要把当前下标当作永久身份。

删除时把顺序与身份分开

fn main() {
    let original = vec![(10, "a"), (20, "b"), (30, "c"), (40, "d")];
    let mut ordered = original.clone();
    assert_eq!(ordered.remove(1), (20, "b"));
    assert_eq!(ordered, [(10, "a"), (30, "c"), (40, "d")]);

    let mut unordered = original;
    assert_eq!(unordered.swap_remove(1), (20, "b"));
    assert_eq!(unordered, [(10, "a"), (40, "d"), (30, "c")]);
    assert_eq!(unordered[1].0, 40); // 索引 1 现在属于另一个 ID
}

若另有 HashMap<ID, usize> 维护位置，swap_remove 后必须更新被搬来末项的索引，否则查询会定位到错误对象。ID 解决逻辑身份，映射维护解决存储位置，两者缺一不可。单纯将 Vec 元素改成 Box 只能让未移动的堆对象地址更稳定，不能防止对象被删除或旧 ID 被复用。

HashMap：哈希、相等与随机种子共同构成契约

相等的键必须产生相等的哈希结果。自定义 Hash 与 Eq 需要相互一致；键放入后不能通过内部可变性等方式改变参与哈希或相等比较的部分，否则破坏集合约定。

标准库当前实现源于 SwissTable，并使用带随机状态的默认哈希构造器；默认算法与细节可演进。随机状态并非简单的“每次进程启动只有一个所有表共享的固定种子”。选择替代哈希器时应结合输入威胁模型、键长度和测量，不承诺固定快 10% 或 30%。HashMap

Entry 接口把查询与插入意图放在一次操作中：

use std::collections::HashMap;
fn main() {
    let mut counts = HashMap::new();
    for word in ["red", "blue", "red"] {
        *counts.entry(word).or_insert(0_u32) += 1;
    }
    assert_eq!(counts.get("red"), Some(&2));
}

不要依赖 HashMap 遍历顺序生成稳定快照或测试期望。当前实现遍历可能按 capacity 而不是仅按 len 扫描，曾经很大而后来变稀疏的表值得单独测量。需要稳定顺序时，显式排序输出或选择有序结构。

借用查询避免为了查找而分配

use std::collections::HashMap;
fn main() {
    let mut values: HashMap<String, Vec<u32>> = HashMap::new();
    values.insert(String::from("red"), vec![1]);
    assert_eq!(values.get("red").map(Vec::len), Some(1));

    let mut constructed = 0;
    values.entry(String::from("red")).or_insert_with(|| {
        constructed += 1;
        vec![99]
    }).push(2);
    assert_eq!(constructed, 0);
    assert_eq!(values.get("red").unwrap(), &[1, 2]);
}

String 键可以借用 str 查询，因为相应 Borrow 契约使两种表示的相等与哈希一致。这个能力并不意味着任意自定义“可转成字符串”的类型都适合 Borrow：若键按忽略大小写比较，而普通 str 按大小写敏感比较，两者就不具有同一种键语义。

or_insert_with 只在空缺时构造值，但本例传给 entry 的 String 仍在调用前创建。热点若主要是命中，可以衡量先 get_mut、缺失再创建键的路径；它减少命中时的键分配，却可能使缺失路径多一次查找。不要把 Entry 理解成键和值都自动惰性创建。HashMap 借用查询

BTreeMap：顺序是接口能力，不是性能附赠

BTreeMap 依据 Ord 排序，适合范围查询、寻找边界和有序输出。节点内部存放多项，具有一定局部性，但整个树不是一个连续数组。排序 Vec 也能同时提供连续布局与有序读取，所以“缓存局部性和顺序不能兼得”并不成立。

use std::collections::BTreeMap;
fn main() {
    let values = BTreeMap::from([(10, "a"), (20, "b"), (30, "c")]);
    let selected: Vec<_> = values.range(15..=30)
        .map(|(&key, &value)| (key, value)).collect();
    assert_eq!(selected, [(20, "b"), (30, "c")]);
}

选择树还是排序 Vec，要比较更新频率与范围读取：一批数据构建后长期只读，排序 Vec 往往值得测；频繁在线插删则可能更适合树。键比较若涉及长字符串，比较本身的成本也应算入。

最近边界查询需要明确包含关系

use std::collections::BTreeMap;
fn main() {
    let changes = BTreeMap::from([(10, "v1"), (20, "v2"), (30, "v3")]);
    let at = |time| changes.range(..=time).next_back().map(|(_, v)| *v);
    assert_eq!(at(9), None);
    assert_eq!(at(20), Some("v2"));
    assert_eq!(at(25), Some("v2"));

    let sorted = [(10, "v1"), (20, "v2"), (30, "v3")];
    let end = sorted.partition_point(|(time, _)| *time <= 25);
    let predecessor = end.checked_sub(1).map(|i| sorted[i].1);
    assert_eq!(predecessor, Some("v2"));
}

这里查询的是“不晚于 time 的最后一次变化”。树用有序 range 再 next_back，排序切片用 partition_point 找到第一个大于 time 的位置。切片在最早时间之前会返回 0，因此需要 checked_sub 处理不存在前驱。若允许相同时间重复，Map 的同键插入会替换值，Vec 则可保留多项，必须另定并列事件顺序。BTreeMap 范围

VecDeque：逻辑连续不等于物理连续

环形缓冲允许前端和尾端高效操作，扩容仍可能发生。as_slices 返回两段，按顺序连接才是逻辑内容；make_contiguous 可整理成一个连续切片，但整理本身可能需要移动元素。VecDeque

use std::collections::VecDeque;
fn main() {
    let mut queue = VecDeque::from([1, 2, 3]);
    assert_eq!(queue.pop_front(), Some(1));
    queue.push_back(4);
    let (a, b) = queue.as_slices();
    let logical: Vec<_> = a.iter().chain(b).copied().collect();
    assert_eq!(logical, [2, 3, 4]);
}

不要为了把 Vec 当 FIFO 而不断 remove(0)：每次都移动剩余元素，长队列会积累大量工作。若业务只需批量读取然后整体清空，Vec 仍可能合适，操作模式比容器名字更重要。

逻辑队列怎样跨过物理末端？

把 A、B、C 看作逻辑身份，把格子编号看作物理位置。头部接近缓冲末端时，队列仍按 A、B、C 排列，只是存储分成两段。公式中的取模解释了这种折返；它不表示 Rust 的索引会允许任意越界值。

$$p(i)=(h+i)\mathrm{mod}C,0\le i<\mathrm{len}\le C$$

BinaryHeap：调度顺序是 Ord 的结果

标准 BinaryHeap 是最大堆；需要最早期限先执行，可以将比较键包装为 Reverse。若并列任务需要 FIFO，就在键中加入按入队顺序分配的序号，不能依赖内部排列顺序。

use std::{cmp::Reverse, collections::BinaryHeap};
fn main() {
    let mut pending = BinaryHeap::from([
        Reverse((20u64, 0u64)),
        Reverse((10, 2)),
        Reverse((10, 1)),
    ]);
    assert_eq!(pending.pop(), Some(Reverse((10, 1))));
    assert_eq!(pending.pop(), Some(Reverse((10, 2))));
    assert_eq!(pending.pop(), Some(Reverse((20, 0))));
    assert_eq!(pending.pop(), None);

    let mut scores = BinaryHeap::from([9, 5, 3]);
    {
        let mut top = scores.peek_mut().unwrap();
        *top = 1;
    } // guard 正常析构，维护新的堆序
    assert_eq!(scores.peek(), Some(&5));
}

序号的分配与回绕是调度器的责任；长寿命系统应在溢出前处理，而不是让重复序号悄悄改变顺序。真实任务可只把期限、序号和任务 ID 放在堆中，将大对象保存在独立表里，从而不让任务正文参与 Ord。

普通 iter 不提供排序遍历，连续 pop 才按堆优先级取出。也不要通过内部可变性悄悄修改堆中元素的排序字段；更新堆顶可以使用 peek_mut，任意任务改期则需要明确的删除/重插或版本化失效策略。后者允许旧条目留在堆中，弹出时检查版本并跳过，但必须控制陈旧条目的积累。BinaryHeap 契约

衡量真实成本

记录元素数、键分布、插删比例、容量峰值和是否要求输出顺序，再测试构建与稳态两个阶段。预分配降低扩容次数，但可能增加长期内存占用；shrink_to_fit 也不保证 RSS 立刻下降，后面还隔着分配器和操作系统。

使用集合的安全 API 不等于所有逻辑条件由编译器证明：索引有效性、业务 ID 生命周期、哈希一致性和排序规则仍是设计的一部分。