哈希表
- 哈希函数：把键转成整数哈希值
- 目标：快、分布均匀、对常见输入模式不敏感
- 例：h = hash(key)
- 均匀分布能让元素在桶中“平均摊开”，避免局部拥挤
- 映射到桶位（数组索引）
- 典型做法：index = h mod table_size
- 直接用数组下标访问是常数时间，因此“定位”非常快
- 冲突处理：同一桶位出现多个键怎么办？
- 拉链法（链表/小向量）：桶里存一个小容器。查找时先定位桶，再在桶内线性搜索或二分/散列（若用小向量或有序结构）。
- 开放寻址：若命中占用，按探测序列查找下一个空位（线性/二次/双重散列）。
- 设计得当时，桶内元素个数或探测步数的期望值是常数。