请选择 进入手机版 | 继续访问电脑版

散列表

[复制链接]
密战 发表于 2021-1-1 10:31:54 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
文章目次



前言

农民山泉:我们不生产水,我们是大自然的搬运工。
大草如是说:我不生成知识点,我是书本的板运工。详细内容见《算法导论》第11章。
当年上《数据布局》的时候,由于课时原因,老师快速带过了9.3节哈希表的相关内容。后来,我偷闲看了小甲鱼–数据布局–散列表的相关视频。从数据布局的角度来说,哈希表并没有什么难度。无非是,通过映射的方式来实现增删查的字典利用。但是从算法的角度,当看过麻省理工学院公开课–算法导论–哈希表的相关视频,对于哈希表我一脸懵逼。由于算法课程原因,我翻看了《算法导论》第十一章散列表的相关内容。下面将会抛开数学证明,简单的整理下哈希表的相关内容,详细内容见书上。
这里不会先容,为什么需要哈希表,哪些地方会用到哈希表,使用的时候需要如何设计等。因为,我也不知道这些^__^ 。这里仅思量哈希表是个什么啥。

摘要

先容了三种散列函数,用以完成映射:除法散列法、乘法散列法、全域散列法。
先容了两种冲突办理办法:链表法、开放寻址法。


思路先容

我们可以把一组信息作为一个元素来存储。比如某个同学,他可能有学号,姓名,班级等信息。在设计数据布局的时候,我们可以将该同学的一组信息放在一个元素内。这个元素有个关键字,只有该元素拥有,而别的元素没有相同的内容,比如学号。
通过元素关键字,我们可以找到该元素的其他相关信息。那我们如安在设计的数据布局中快速得找到关键字呢?(目前,我们暂时仅思量查找,不思量增加和删除)
脱去元素信息和元素信息对应的数据布局,把问题抽出来,‘如何快速找到关键字?’。
顺便说下,盘算机中的任何内容都是0和1组成。所以我们有理由相信,可以将关键字转换成数字。数字相对于其他字符,易于盘算处理惩罚。后文,我们统一认为关键字是数字范例。这里留下了一个问题,有哪些转化方式,这些转换方式的适用场景与优缺点。
此时,我们拥有了一堆乱糟糟的关键字,我们如何快速定位我们需要的关键字呢?第一种方法是排序。我们可以在有序的关键字聚集中快速找到我们需要的内容。但是,排序是有代价的,不思量线性时间排序,好的排序时间复杂度约莫是nlog(n)。除了排序有没有什么好的办法呢?
有的。借鉴下桶排序的思想,我们可以将关键字与下标创建起一对一的映射关系。(可以是一对多的关系,背面通过链表的方式办理冲突便是一对多关系)将关键字作为关键字数组存储位置下表的方式,是一对一映射关系的一种,可以在O(1)时间内找到关键字在数组中的位置。我们称这种方式为直接寻址法
但是,直接寻址法,有很大的毛病。当关键字的全域比较大的时候,由于一对一关系,需要很大的存储空间。但是实际关键字的个数可能远远小于关键字的全域,导致大量的空间被浪费。
既然有一对一有许多空间被浪费,我们何不一对多呢?这里有两个问题:如何一对多?其造成冲突如何办理?
首先思量第一个问题,一对多一定会有冲突,如何设计一对多以淘汰冲突。这里引入一个概念哈希函数。通过哈希函数,将关键字的全域U映射到散列表的槽位上。好的哈希函数应(近似地)满足简单均匀散列假设:每个关键字都等可能的散列到m个槽位中的任何一个,与其他关键字已散列到谁人位置无关。我们设计的哈希函数应当趋向于这个目的。
接着,思量第二个问题,一对多一定会有冲突,如何办理冲突。借鉴下,通排序的思想,我们可以将在同一个槽位上冲突的关键字串联起来。或者,我们可以再次盘算,将关键字放在表中的另一个位置。
此时,顺其自然产生了第三个问题:一对多设计的差别哈希函数之间的对比;冲突办理计谋的对比;在特定场景,两着的使用等
本文,复制书上的知识点,顺道借着这些问题思路看书上的点。
也可以阅读这篇文章

散列函数

本节将讨论一些关于如何设计好的散列函数的问题,并先容三种详细方法。此中的两种方法(用除法进行散列和用乘法进行散列)本质上属于启发式方法,而第三种方法(全域散列)则利用了随机技能来提供可证明的精良性能。
一个好的散列函数应(近似地)满足简单均匀散列假设:每个关键字都被等可能地散列到m个槽位中的任何一个,并与其他关键字已散列到哪个槽位无关。遗憾的是,一般无法检査这一条件是否建立,因为很少能知道关键字散列所满足的概率分布,而且各关键字可能并不是完全独立的。

有时,我们知道关键字的概率分布。比方,如果各关键字都是随机的实数k,它们独立均匀地分布于0≤k
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )