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