Java教程

Hash (散列函数)

本文主要是介绍Hash (散列函数),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Hash (散列函数)
哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。
一般的线性表,树中,记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上,查找的效率依赖于查找过程中所进行的比较次数。 理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。
Hash算法是一个广义的算法,也可以认为是一种思想,使用Hash算法可以提高存储空间的利用率,可以提高数据的查询效率,也可以做数字签名来保障数据传递的安全性。所以Hash算法被广泛地应用在互联网应用中。

哈希表的概念及作用编辑 播报
哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量,通过一定的函数关系(称为哈希函数),计算出的值,即为该元素的存储地址。表示为:
Addr = H(key)
为此在建立一个哈希表之前需要解决两个主要问题:
⑴构造一个合适的哈希函数
均匀性 H(key)的值均匀分布在哈希表中;
简单 以提高地址计算的速度
⑵冲突的处理
冲突:在哈希表中,不同的关键字值对应到同一个存储位置的现象。即关键字K1≠K2,但H(K1)= H(K2)。均匀的哈希函数可以减少冲突,但不能避免冲突。发生冲突后,必须解决;也即必须寻找下一个可用地址。
解决冲突的方法
⑴链接法(拉链法)。将具有同一散列地址的记录存储在一条线性链表中。
⑵开放定址法。
⑶桶定址法。
哈希表的构造方法
直接定址法
数字分析法
平方取中法
折叠法
除留余数法

这篇关于Hash (散列函数)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!