哈希表

哈希表（Hash Table）

又称为散列表，是一种基于键值对（Key-Value Pair）存储的数据结构。它通过哈希函数将键（Key）映射为数组索引，从而实现高效的插入、查找和删除操作。
简而言之：

给定一个键 key，我们可以使用哈希函数快速定位其对应的值 value，时间复杂度接近$O(1)$。

哈希表的两个关键组件

• 哈希函数
  • 将任意长度的输入（如字符串、整数等）转换为固定长度的数值该数值再通过取模运算确定其在数组中的位置
• 冲突解决策略
  • 不同的键可能映射到同一个位置（称为哈希冲突），需要通过链地址法、开放寻址法等方式解决。

工作流程

1. 插入操作：输入键 key → 哈希函数计算索引 → 存储值 value 到对应桶中。
2. 查询操作：输入键 key → 哈希函数计算索引 → 直接访问桶获取值 value。
3. 删除操作：类似查询，找到后进行删除。