哈希
散列表
散列表（Hash table，也叫哈希表）是根据键（key）而直接访问在内存存储位置的数据结构。即，通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，该函数叫散列函数，存放记录的数组叫做散列表。
散列函数
特点
- 确定性
如果两个散列值不同（by同一函数），则其原始输入也不同。 - 散列碰撞（collision）
输入输出不唯一对应，不同输入可能对应相同输出。 - 不可逆性
一个哈希值对应无数明文，理论上不可逆。 - 混淆特性
部分改变输入值，一个具有强烈混淆特性的散列函数会产生一个完全不相同的散列值
常见散列函数
- MD5
- SHA-1
散列冲突
即使再好的散列函数也无法避免冲突，当待存储数据大于存储区域（n）时，必然会存在哈希值相同的情况，即散列冲突。
解决方法
- 开放寻址法
- 线性探测方法
冲突时依次往后查找，看是否有空闲位置，直到找到为止。 - 二次探测
冲突时依次找hash + 1^2, -1^2, +2^2, -2^2, +3^2... - 双重散列
通过多个散列函数依次查找
-
链表法
在散列表中，每个位置对应一条链表，所有散列值相同的元素都放在相同位置对应链表中。
image
