作者:哈喽随风amy | 来源:互联网 | 2023-10-12 12:12
2、散列表是如何实现查找的?上面提到的某个函数,被称为散列函数,它负责记录存储位置和它的关键字之间的对应关系f。保证存储空间的有效利用,并减少为处理冲突而耗费的时间。冲突就是,
要详细介绍哈希表系列的概要,共有三篇文章1、哈希表
2、哈希函数的作用和结构
3、哈希表搜索的代码实现
文章目录散失清单系列共有三个报道正文篇的要点是散失清单概要1、散失清单是什么? 2、哈希表是怎么实现搜索的? 3、哈希表搜索步骤4、好哈希函数两个原则: 5、冲突是什么? 6、总结
因为哈希表的内容太多了,所以我打算分三篇文章说解散名单。
本篇的重点是散列表的概要1、散列表是什么?散列表(又称仁爱的荔枝表(Hash table))使用散列技术将记录存储在连续的存储空间中。
哈希表使用某个函数f,使其为存储位置 = f(关键字)。 这样,无需比较关键字就可以得到所需记录的存储位置。
哈希技术记录之间没有逻辑关系,只与关键字相关。 因此,散列主要是面向查找的存储结构
2、哈希表是怎么实现搜索的? 上述函数称为散列函数,记录存储位置及其关键字之间的对应关系f。
散列函数,又称为仁爱的荔枝(Hash)函数
所记录的存储位置与其关键字的对应关系f被称为散列函数散列技术,是一种新的存储技术散列技术。 在记录的存储位置和该关键字之间,各关键字key位于存储位置f(key )查找时:
如果该记录存在于发现集合中,则基于该决定的对应关系来找到规定的值key的映射f[key]一定位于f[key]的位置。key 为关键字,f 为散列函数,f(key)为存储位置
3、散列表搜索步骤在存储时,通过散列函数计算纪录的散列地址,并按此散列地址存储该记录。
请想象一个场景。 你想寄快递。 快递的哥哥给我贴了快递的订单号码,让我放在了驿站里的桌子上。
但是,一进车站,就有很多桌子。 你不知道他在说什么。
这个时候,有人来问你要不要寄快递。 然后,我问你有没有贴快递的订单号码。 你给他订单号后,他帮你放在指定的桌子上。
这就是哈希表的保存过程。快递单号就是关键字,驿站里的那个人就是散列函数,而快递放到的桌子就是最终得出的指定地址。
当查找记录时,我们通过同样的散列函数计算记录的散列地址,按此散列地址访问该记录。
果然是那一幕,但这个时候的你不是来快递的,而是来拿挚友送的麻辣鸭翅的。
你直接进入了那个放置快递的车站,给了那个人快递的号码。 那个人用你的快递号码找到了你的快递,拿来给你了。
的步骤与存储步骤相同,只是使用的用途不同。我们都是将关键字给予散列函数,通过散列函数计算得出的存储位置来存储 / 查找。
更简单地说,散列函数所起的作用是通过计算得到东西存哪去,从哪拿?
4、好散列函数的两个原则:1、计算简单
散列函数的计算时间不能超过与其他搜索技术比较关键字的时间。
2、散列地址分布均匀
解决冲突的最佳方法是将哈希地址均匀地尽量分布在存储空间中。
确保有效利用存储空间,减少处理冲突所需的时间。
5、冲突是什么? 在上面提出的原则中,有一个新词叫做“冲突”。 什么是冲突?
冲突是指两个不同的关键字,但通过散列函数得到的地址是一样的。
key1 key2,但f(key1)=f (key2)
同义词
此时的key1和key2被称为该散列函数的同义词
那可不行啊。 单人房怎么能两个人住?
请不要担心。 这个问题当然由神通广大的xsdwbl解决了。
我的下一篇文章慢慢来~
6、总结最后总结哈希表的优缺点。
散列技术最适合的求解问题是查找与给定值相等的记录:
优点:简化比较过程、提高搜索效率的缺点:在没有很多常规数据结构的情况下,不能用单个关键字记录多个记录的不正确的范围搜索是本文的全部内容。 如果您认为可以为您服务,请访问3358 www.Sina.com/http://www.Sina.com /
下一期再见吧。