Hash算法
要求
- 正向快速：给定原文和 Hash 算法，在有限时间和有限资源内能计算得到 Hash 值
- 逆向困难：给定（若干）Hash 值，在有限时间内无法（基本不可能）逆推出原文
- 输入敏感：原始输入信息发生任何改变，新产生的 Hash 值都应该发生很大变化
- 碰撞避免：很难找到两段内容不同的明文，使得它们的 Hash 值一致（即发生碰撞）
常见算法
| MD5 | SHA-1 | SHA-2 | SHA-3 | SM3 | |
|---|---|---|---|---|---|
| 推出时间 | 1992 | 1995 | 2002 | 2008 | 2010 |
| 输出长度 | 128 bit | 160 bit | 256/512 bit | 224/256/384/512 bit | |
| 哈希冲突 | 较多 | 较多 | 很少 | 很少 | |
| 安全等级 | 低，已被成功攻击 | 低，已被成功攻击 | 高 | 高 | |
| 应用 | 已被弃用，仍用于数据完整性检查 | 已被弃用 | 加密货币交易验证、数字签名等（ SHA-256 是最安全的哈希算法之一，仍未出现成功的攻击案例，因此常用在各类安全应用与协议中） | 可用于替代 SHA-2 | 中国密码管理局于 2010 年 12 月 17 日发布了 GM/T 0004-2012 《SM3 密码杂凑算法》，建立了国内商用密码体系中的公开 Hash 算法标准 |
Hash冲突解决方案
链式地址
注：当链表很长时，查询效率 O(n) 很差。此时可以将链表转换为“AVL 树”或“红黑树”，从而将查询操作的时间复杂度优化至 O(logn) 。
开放寻址
线性探测
- 容易导致聚集现象
- 需要使用懒删除，None和TOMSTONE都代表空桶，但是探测到TOMSTONE时要继续探测
为了提高性能，可以记录首个TOMBSTONE的索引，并将搜索到的目标元素与该
TOMBSTONE交换位置
平方探测
- 优点：缓解聚集现象，使数据更加均匀
- 缺点：由于平方的增长，存在无法访问的空桶
多次哈希
- 优点：不易产生聚集现象
- 缺点：多个哈希函数带来额外计算量