哈希(散列)
Hash是把任意长度的输入(预映射)通过散列算法变换成固定长度的输出,该输出就是散列值
不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值
Hash算法可以将一个数据转换为一个标志,这个标志和数据源的每一个字节都有关
Hash算法很难找到逆向规律
Hash算法是一个广义的算法,也可以认为是一种思想,使用Hash算法可以提高存储空间的利用率和提高数据查询效率
哈希表 Hash Table
是根据关键码值(key value)直接进行访问的数据结构
添加、搜索、删除的流程都是类似的
1.利用哈希函数生成key对应的index(O(1))
2.根据index操作定位序列中的元素(O(1))
哈希表是空间换时间的应用
哈希表内部的元素,也叫Bucket(桶),整个序列叫Buckets或Bucket Array
哈希冲突 Hash Collision
哈希冲突,也叫哈希碰撞,2个不同的key,经过哈希函数计算出相同的结果
key1 != key2 , hash(key1) = hash(key2)
解决哈希冲突的常用方法
1.开放定址(Open Addressing):按照一定规则向其他地址探索,直至遇到空桶
2.再散列(Re-Hashing):设计多个哈希函数
3.链地址(Separate Chaining):通过链表将同一index的元素串起来
哈希函数
哈希表中哈希函数的实现步骤如下
1.先生成key的哈希值(必须是整数)
2.用key的哈希值与序列的大小进行运算,生成一个索引值(索引值需要在序列内,所以要与序列长度运算)
(1).hash_code(key) % len(table) (取模运算效率较低)
(2).hash_code(key) & (len(table) - 1)
需要将序列的长度设计为 2^n,因为 2^n - 1 在二进制中值全部为 1,任何数 & 1*n 都等于该数的后n位
本质是取出hash_code(key)二进制格式的后n位,此值取值范围一定在 0*n - 1*n (如:0000-1111) 之间
良好的哈希函数
哈希值分布更均匀 => 减少哈希冲突 => 提升哈希表的性能
常用算法
MD4、MD5、SHA-1
生成key的哈希值
key的常见类型:
str、int、float、自定义对象
不同类型的key,生成哈希值的方式不同,但目标是一致的
1.尽量让每个key的哈希值是唯一的
2.尽量让key中所有信息都参与运算
int
用该整数值本身作为哈希值
float
将浮点数的二进制格式转为整数值,该整数值为哈希值
Long 和 Double (8个字节,64位)
int(value ^ (value >>> 32))
哈希值必须是int类型(4个字节),也就是32位,需要让Long和Double的64位都参与运算
value >>> 32 :取出value的高 32bit
value ^ (value >>> 32) : 高 32bit 与低 32bit 运算得出 32bit 的哈希值
& : 可能只取出低 32bit
| : 可能只取出高 32bit
str
ABCD => A*n^3 + B*n^2 + C*n^1 + D*n^0 => [(A*n + B)*n + C]*n + D
字符的本质就是一个整数(每个字符都有对应的ASCII值)
乘数n取31,31是一个奇素数,31*i == (i << 5) - i
生成str的哈希值
def hash_code(s):
hash_s = 0
for i in s :
c = ord(i)
hash_s = (hash_s << 5) - hash_s + c
return hash_s
r = 'a1b2c3'
res = hash_code(r)
print(res)
2825250864