哈希函数
哈希函数将任意键映射到固定范围的整数索引。理想情况下，不同键映射到不同位置，但键空间通常远大于桶数量，冲突不可避免。
性质要求：确定性、均匀分布、雪崩效应、计算高效。常见算法：除留余数法 h(k) = k % m（m 取质数）；乘法哈希；MurmurHash、xxHash 等现代哈希。
对于字符串，常用多项式滚动哈希：h = (h * base + c) % mod，可结合双模减少碰撞。
冲突解决
链地址法（Separate Chaining）：每个桶维护链表（或红黑树，如 Java 8 桶内元素多时）。冲突时插入同一桶的链中。实现简单，可容纳任意多元素。
开放寻址（Open Addressing）：冲突时按探测序列找下一个空位。线性探测 h'(k) = (h(k) + i) % m 易产生聚集；二次探测、双重哈希可缓解。删除需标记为"已删除"而非直接清空，否则会断链。
负载因子与扩容
负载因子 α = 元素数 / 桶数。α 越大，冲突越多，查找越慢。开放寻址通常 α < 0.7；链地址法可更高，但 α > 1 时链变长。
扩容：当 α 超过阈值（如 0.75），创建新桶数组（通常 2 倍），重新哈希所有元素。均摊后插入仍为 O(1)。
Java HashMap 默认初始容量 16，负载因子 0.75，超过则扩容为 2 倍。