算法图解5-哈希

哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构 。散列表也被称之为散列映射、映射、字典和关联数组

通过k-v值映射到表中的一个记录，以加快查找速度。映射函数称之为散列函数或者哈希函数，存放记录的数组称之为散列表

• 若关键字为k，则其值存放在f(k)的存储位置上 ； 称这个对应关系f为散列函数，按这个思想建立的表为散列表
• 对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突

哈希函数

哈希函数可以把给定的数据转换成固定长度的无规律数值，这个值就是哈希值。 转换后的无规律数值可以作为数据摘要应用于各种各样的场景。

特征

• 哈希值多用16进制来表示。由于计算机只能处理二进制，也就是或哈希函数在计算机内部进行着某种运算。
• 确定性：输出的哈希值数据长度不变，不管输入的是多少
• 唯一性：只要输入的值相同，输出的哈希值必然相同
• 即时输入的数据完全不同，输出的哈希值可能是相同的，称之为“哈希冲突”
• 不可反向：不能从哈希值推导出原来的数据
• 哈希值的计算相对容易

解决冲突方法

1. 链接法：将具有同一个散列地址的记录存储在同一条线性链表中
2. 开放地址法
3. 桶定址法。桶：一片足够大的存储空间；桶定址：为表中的每个地址关联一个桶。如果桶满了，则使用开放地址法

代表算法

• MD5
• SHA-1
• SHA-2：应用广泛