1. 平衡二叉搜索树 — std::set / std::map

底层数据结构

红黑树（自平衡二叉搜索树），元素按键值有序存储。

时间复杂度

  • 插入、删除、查找：O(log n) 平均 & 最坏
  • 遍历有序：O(n)
  • 前驱后继（lower_bound/upper_bound）：O(log n)

空间复杂度

  • O(n)，每个节点额外存储左右孩子指针、父节点指针、颜色（通常 3 个指针 + 1 字节），内存开销较大。

使用条件

  • 需要元素按 key 有序（按序遍历、输出排序结果）
  • 需要频繁的范围查询（比 x 大的最小元素、比 x 小的最大元素）
  • 迭代器不能因插入而失效（有稳定迭代器需求）
  • 元素类型没有合适的哈希函数，或担心哈希被卡
  • 数据规模 ≤ 2×10⁵ 且 O(log n) 完全够用

2. 哈希表 — std::unordered_set / std::unordered_map

底层数据结构

开链法（Separate Chaining）哈希表。由一个桶数组（动态扩缩容）和链表/红黑树（当桶内冲突过多时 C++11 后可能转红黑树）构成。

时间复杂度

  • 插入、删除、查找：平均 O(1)，最坏 O(n)（大量冲突退化为链表）
  • 不支持顺序查询

空间复杂度

  • O(n)，但常数较大（桶数组 + 每个节点的指针/哈希值存储），负载因子默认约 1.0，内存占用通常大于红黑树。

使用条件

  • 只需要快速判存在，不关心顺序
  • 数据分布较均匀，哈希冲突概率低
  • 没有范围查询需求
  • 作为通用哈希表，适用于绝大多数情况，竞赛中极少被故意卡（int/string 等默认哈希很安全）

3. 直接寻址数组 — bool arr[128] / std::array<bool, N>

底层数据结构

把 key 直接当作数组下标，相当于“哈希函数为恒等映射”。每个位置存储一个 bool 或计数。

时间复杂度

  • 插入、删除、查找：严格 O(1)，常数极小
  • “哈希函数”就是取下标，零冲突

空间复杂度

  • O(M)，M 为 key 域的大小（例如字母大小写共 128，或数字范围 10⁷）。
  • 如果 key 域很大但实际存储元素稀疏，空间浪费严重。

使用条件

  • key 的范围很小且连续/可枚举（如 ASCII 字符、小范围整数）
  • 追求极致速度，同时内存放得下整个域
  • 这是 “用空间换时间”的终极形态，也是竞赛中处理字符集问题的最优解
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param jewels string字符串 
     * @param stones string字符串 
     * @return int整型
     */
    int numJewelsInStones(string jewels, string stones) {
        array<bool,128> isJewel{};
        for(const auto& jewel:jewels) isJewel[jewel]=true;
        int cnt=0;
        for(const auto& stone:stones) cnt+=isJewel[stone];
        return cnt;
    }
};