数据结构选型速记

一、面试常考点

1. 选型原则

先看操作类型（查找/插入/删除/区间），再看数据规模和是否有序。

2. 高频映射

• 判重、频次统计：哈希表。
• 区间查询：前缀和/树状数组/线段树。
• TopK：堆。
• 最短路径（无权）：BFS。

二、速记表

场景	优先结构	说明
高频查找	哈希表	平均 O(1)，注意哈希冲突
有序查找	二分 + 有序数组	查询 O(log n)，插入成本高
动态最值	堆	取最值 O(1)，更新 O(log n)
队头队尾操作	双端队列	滑动窗口高频使用