Hash Table

用途

提供平均常数时间的键值存取，高效实现字典与集合。

机制

hash(key) % capacity 定位桶。冲突处理：链地址法（桶存链表）或开放寻址（探测下一空桶）。装载因子 = 元素数/桶数，超阈值扩容 rehash。良好哈希函数使键均匀分布。

用例

• 字典与映射实现
• 数据库索引
• 缓存（LRU）
• 去重与集合

示例

• 输入

  {"name":"Ada"} → hash("name")=5

  输出

  Value stored in bucket 5

  O(1) on average

常见错误

A poorly distributed hash function causes collision pile-ups

Use a high-quality hash function and a suitable load factor