Hash Table 哈希表

用来存储和引用 hash 值的数据结构。计算机科学基础结构之一,本质是”键 → 槽位”的快速映射。

工作原理

1. 拿到键(key),用 hash function 算出 hash
2. 把 hash 映射到数组的某个槽位
3. 数据存到那个槽位里
4. 查找时同样算 hash,直接跳到槽位 —— O(1) 时间

槽位冲突(hash collision)时,常用”链表挂在槽位下”或”开放寻址”解决。

在安全里干什么

场景	怎么用
杀毒软件	已知 malware 的 SHA-256 指纹存在 hash table 里,扫文件时 O(1) 查
密码破解	Rainbow Table = 预计算的 hash → 明文映射,字典攻击核心武器
IP/域名黑名单	实时连接检查时 O(1) 命中
去重存储	邮件附件、网盘秒传

和 hash function 别混

• Hash function = 算法,把输入压成 hash
• Hash table = 数据结构,用 hash 做索引存东西

两者关系: hash table 依赖一个 hash function 来定位槽位。