[!info] related notes 算法面试题型 MOC

哈希表与有序表（HashMap / TreeMap）

哈希函数

将任意大小的 key 映射到固定范围的整数（桶下标）。好的哈希函数应当：

• 确定性：相同输入始终相同输出
• 均匀性：输出在桶间均匀分布
• 高效：计算速度快

index = hash(key) % table_size

碰撞处理

链地址法（Chaining）

每个桶维护一个链表（或红黑树）。Java HashMap 在链表长度 > 8 时转为红黑树。

桶0: -> [key1] -> [key5]
桶1: (空)
桶2: -> [key3] -> [key7] -> [key9]

开放寻址法（Open Addressing）

碰撞时按探测序列寻找下一个空槽。常见策略：线性探测、二次探测、双重哈希。

• 优点：缓存友好（数据连续存储）
• 缺点：需要控制装载因子，删除麻烦（需要墓碑标记）

装载因子与再哈希

$$\alpha = \frac{n}{m} \quad (n=\text{元素数}, m=\text{桶数})$$

• 当 $\alpha$ 超过阈值（Java HashMap 默认 0.75），触发再哈希（rehash）：桶数翻倍，所有元素重新分布。
• 再哈希是 $O(n)$ 的摊销操作，但均摊后插入仍为 $O(1)$。

JS 中的 Map / Set

const map = new Map();
map.set('name', 'Alice');
map.get('name');       // 'Alice'
map.has('name');       // true
map.delete('name');
map.size;              // 0

// 遍历保持插入顺序
for (const [key, val] of map) { /* ... */ }

const set = new Set([1, 2, 3, 2]);
// set = {1, 2, 3}  自动去重

JS 的 Map 保持插入顺序，但不提供有序表的能力（不能按 key 大小遍历）。

哈希表 vs 有序表

维度	HashMap / HashSet	TreeMap / TreeSet
底层实现	数组 + 链表/红黑树	红黑树
增删改查	平均 $O(1)$	$O(\log n)$
顺序	无序	key 有序
区间查询	不支持	支持（floor/ceiling/subMap）
前驱后继	不支持	$O(\log n)$
适用场景	快速查找、计数、去重	需要顺序、区间、排名

去重与比较器

• Set/Map 的”相等”依赖其比较策略。
• TreeSet/TreeMap 如果比较器认为两个元素相等，会发生去重。

比较器要点（Java）

• Comparator<T> 定义元素的排序与”相等”判定（compare(a,b) == 0 视作相等）。
• 如果你需要”看起来相等但不去重”，通常意味着：
  • 不能用 TreeSet/TreeMap 的默认语义；
  • 或者比较器需要把更多字段纳入比较。

选择建议

• 只要快：优先哈希表。
• 需要顺序/区间：用有序表。

相关笔记

• 算法面试题型 MOC
• 排序算法总结