哈希表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构 。散列表也被称之为散列映射、映射、字典和关联数组
通过k-v值映射到表中的一个记录，以加快查找速度。映射函数称之为散列函数或者哈希函数，存放记录的数组称之为散列表
-
若关键字为k，则其值存放在f(k)的存储位置上 ； 称这个对应关系f为散列函数，按这个思想建立的表为散列表
-
对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突
哈希函数
哈希函数可以把给定的数据转换成固定长度的无规律数值，这个值就是哈希值。
转换后的无规律数值可以作为数据摘要应用于各种各样的场景。
特征
- 哈希值多用16进制来表示。由于计算机只能处理二进制，也就是或哈希函数在计算机内部进行着某种运算。
- 确定性：输出的哈希值数据长度不变，不管输入的是多少
- 唯一性：只要输入的值相同，输出的哈希值必然相同
- 即时输入的数据完全不同，输出的哈希值可能是相同的，称之为“哈希冲突”
- 不可反向：不能从哈希值推导出原来的数据
- 哈希值的计算相对容易
解决冲突方法
- 链接法：将具有同一个散列地址的记录存储在同一条线性链表中
- 开放地址法
- 桶定址法。桶：一片足够大的存储空间；桶定址：为表中的每个地址关联一个桶。如果桶满了，则使用开放地址法
代表算法
-
MD5
-
SHA-1
-
SHA-2：应用广泛
