23哈希

哈希

降低数据复杂度，对直接访问进行改进

实现方式：用哈希函数将长数据映射成一个短值

特性

1.执行效率高，对于二进制文本尽可能快计算出哈希值

2.结果尽可能具有同一性，输出的值尽可能均匀分布

3.存在雪崩效应：任何一个微小数值的变化都能使输出产生巨大变化

4.哈希函数不能反向推导

哈希碰撞

对两个不同的值映射成同一个输出

这个情况不能避免，只能缓解

缓解方式

1.链地址法（对哈希函数要求较低）

数组加链表存储同一哈希值的不同数据

优点：

容错率高

不会溢出

缺点：

链表过长

浪费原有空间，同时需要额外的空间存储指针

缓存性能不好

2.开放地址法

将所有数据存储在哈希表中，同一哈希值的不同数据相邻放置

问题：可能需要扩容

解决方法：

线性探测法：不断向下一个一个找空间存储

缺点：可能出现大规模聚集导致时间浪费

平方探测法：不断向下探测i^2个空间（i不断递增，直到有存储空间）

双重哈希法：再定义一个哈希函数，使用：原本的哈希值+i*新的哈希值（i不断递增，直到有存储空间）

3.再哈希

装填因子：n个数据/m个存储空间（已存的数据占当前存储空间的比例）

将装填因子设置为0.75，一旦哈希表达到0.75，就扩容这个哈希表，并重新进行另一个哈希映射（这个新的哈希函数与空间量有公式挂钩）

哈希应用

密码校验，编译，编程语言，模式匹配算法，负载均衡