作业帮什么是哈希算法,哈希函数主要有哪些?
来源：学生作业帮 编辑：作业帮 分类：综合作业 时间：2024/05/04 07:15:50
什么是哈希算法,哈希函数主要有哪些?
额.LZ是不是看了小说绘的终极解密啊?
我也蛮感兴趣滴.嘿嘿,
哈希函数是一般的线性表,树中,记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系.
将数据元素的关键字K作为自变量,通过一定的函数关系（称为哈希函数）,计算出的值,即为该元素的存储地址.表示为：
Addr = H（key）
为此在建立一个哈希表之前需要解决两个主要问题：
⑴构造一个合适的哈希函数
均匀性 H（key）的值均匀分布在哈希表中；
简单 以提高地址计算的速度
⑵冲突的处理
冲突：在哈希表中,不同的关键字值对应到同一个存储位置的现象.即关键字K1≠K2,但H（K1）= H（K2）.均匀的哈希函数可以减少冲突,但不能避免冲突.发生冲突后,必须解决；也即必须寻找下一个可用地址. 无论哈希函数设计有多么精细,都会产生冲突现象,也就是2个关键字处理函数的结果映射在了同一位置上,因此,有一些方法可以避免冲突.
1.拉链
拉出一个动态链表代替静态顺序储存结构,可以避免哈希函数的冲突,不过缺点就是链表的设计过于麻烦,增加了编程复杂度.此法可以完全避免哈希函数的冲突.
2.多哈希法
设计二种甚至多种哈希函数,可以避免冲突,但是冲突几率还是有的,函数设计的越好或越多都可以将几率降到最低（除非人品太差,否则几乎不可能冲突）.
3.开放地址法
开放地址法有一个公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k
我也蛮感兴趣滴.嘿嘿,
哈希函数是一般的线性表,树中,记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系.
将数据元素的关键字K作为自变量,通过一定的函数关系（称为哈希函数）,计算出的值,即为该元素的存储地址.表示为：
Addr = H（key）
为此在建立一个哈希表之前需要解决两个主要问题：
⑴构造一个合适的哈希函数
均匀性 H（key）的值均匀分布在哈希表中；
简单 以提高地址计算的速度
⑵冲突的处理
冲突：在哈希表中,不同的关键字值对应到同一个存储位置的现象.即关键字K1≠K2,但H（K1）= H（K2）.均匀的哈希函数可以减少冲突,但不能避免冲突.发生冲突后,必须解决；也即必须寻找下一个可用地址. 无论哈希函数设计有多么精细,都会产生冲突现象,也就是2个关键字处理函数的结果映射在了同一位置上,因此,有一些方法可以避免冲突.
1.拉链
拉出一个动态链表代替静态顺序储存结构,可以避免哈希函数的冲突,不过缺点就是链表的设计过于麻烦,增加了编程复杂度.此法可以完全避免哈希函数的冲突.
2.多哈希法
设计二种甚至多种哈希函数,可以避免冲突,但是冲突几率还是有的,函数设计的越好或越多都可以将几率降到最低（除非人品太差,否则几乎不可能冲突）.
3.开放地址法
开放地址法有一个公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k