哈希表原理

通过哈希函数将键映射到桶，实现 平均查找效率。

核心机制

哈希函数：将任意键映射为固定范围内的数组索引，要求均匀分布以降低冲突。

冲突处理

方法	原理	特点
链式地址	每个桶维护链表，冲突时追加	实现简单，链表过长时退化为
开放寻址	冲突后线性探测下一个空位	无额外指针开销，删除需惰性标记

扩容（Rehashing）

负载因子（元素数 / 桶数）超过阈值时，创建更大的桶数组，将所有元素重新哈希散列。扩容操作本身 ，但均摊后仍有 效率。

典型应用

索引缓存、去重、频率统计、记忆化搜索。