一, 定义
Hash : 散列, 通过关于键值 (key) 的函数, 将数据映射到内存存储中一个位置来访问. 这个过程叫做 Hash, 这个映射函数称做散列函数, 存放记录的数组称做散列表(Hash Table), 又叫哈希表.
简单地说, 它是密码学中的一个重要的函数, 一般以 Hash(.)表示. 这个函数可以将任意一段数据 (一般称这段数据为 "消息") 压缩成固定长度的字符串(一般称输出的字符串为 "摘要"). 哈希函数需要满足下述条件:
1, 确定性: 哈希函数的算法是确定性算法, 算法执行过程不引入任何随机量. 这意味着相同消息的哈希结果一定相同.
2, 高效性: 给定任意一个消息 m, 可以快速计算 Hash(m)
3, 目标抗碰撞性: 给定任意一个消息 m0, 很难找到另一个消息 m1, 使得 Hash(m0) = Hash(m1)
4, 广义抗碰撞性: 很难找到两个消息 m0 不等于 m1 的情况下, 使得 Hash(m0) = Hash(m1)
二, 优点
先分类, 再查找, 通过计算, 缩小范围, 加快查找速度
三, 作用
1, 数字签名: 给数据打指纹
2, 密码存储
四, 特性
1, 正向快速: 给定明文和 hash 算法, 在有限时间和有限资源内能计算出 hash 值.
2, 逆向困难: 给定 (若干) hash 值, 在有限时间内很难(基本不可能) 逆推出明文.
3, 输入敏感: 原始输入信息修改一点信息, 产生的 hash 值看起来应该都有很大不同.
4, 冲突避免: 很难找到两段内容不同的明文, 使得它们的 hash 值一致(发生冲突).
五, hash 算法
1, 直接定值法: 取 Key 或者 Key 的某个线性函数值为散列地址.
2, 数字分析法: 需要知道 Key 的集合, 并且 Key 的位数比地址位数多, 选择 Key 数字分布均匀的位.
Hash(Key) 取六位:
列数 : 1 (2) 3 (4) 5 (6) (7) 8 (9) 10 11 12 (13)
- key1: 5 2 4 2 7 5 8 5 3 6 5 1 3
- key2: 5 4 4 8 7 7 7 5 4 8 9 5 1
- key3: 3 1 5 3 7 8 5 4 6 3 5 5 2
- key4: 5 3 6 4 3 2 5 4 5 3 2 6 4
其中 (2,4,6,7,9,13) 这 6 列数字无重复, 分布较均匀, 取此六列作为 Hash(Key) 的值.
- Hash(Key1) :225833
- Hash(Key2):487741
- Hash(Key3):138562
- Hash(Key4):342554
3, 平方取中法: 取 Key 平方值的中间几位作为 Hash 地址.
4, 折叠法: 将关键字分割成位数相同的几部分 (最后一部分的位数可以不同), 然后 取这几部分的叠加和(舍去进位) 作为哈希地址. 当 Key 的位数较多的时候数字分布均匀适合采用这种方案.
5, 随机数法: 伪随机探测再散列.
具体实现: 建立一个伪随机数发生器, Hash(Key) = random(Key). 以此伪随机数作为哈希地址.
6, 除留余数法: 取关键字被某个除数 p 求余, 得到的作为散列地址. 即 H(Key) = Key % p;
[python 进阶] 哈希算法(Hash)
来源: http://www.bubuko.com/infodetail-3351850.html