[!info] related notes 算法面试题型 MOC 二叉搜索树 两数之和：哈希查找应用

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

哈希函数

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

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

index = hash(key) % table_size

碰撞处理

链地址法（Chaining）

每个桶维护一个链表（或红黑树）。OpenJDK HashMap 的树化还受桶数组容量约束：达到树化阈值时，若容量小于 64，优先扩容，不能仅按链表长度判断。

桶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
底层实现（Java）	数组 + 链表/红黑树	红黑树
增删改查	平均 $O(1)$	$O(\log n)$
顺序	无序	key 有序
区间查询	不支持	支持（floor/ceiling/subMap）
前驱后继	不支持	$O(\log n)$
适用场景	快速查找、计数、去重	需要按键排序、区间查询

普通 TreeMap 不直接提供按排名选择第 k 个元素的 O(log n) 操作；这通常需要维护子树大小等额外信息。

去重与比较器

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

比较器要点（Java）

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

选择建议

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

相关笔记

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