C语言的哈希表算法的简单学习/回顾

本文最后更新于2014年8月3日,已超过 1 年没有更新,如果文章内容失效,还请反馈给我,谢谢!

碰到了个哈希表问题,虽然之前学习过(隔了也有好久了,而且后来我基本没用到过),但突然被问到哈希表算法我还真的是懵了,下来之后去网上搜索相关资料,看已有的代码示例,自己修改然后编译执行(好久没有用C语言写过代码了,各种错误,好不适应o(╯□╰)o),终于想起来其实自己之前在《数据结构》这门课和这本书上学习过,但当时没有实际编写、编译执行过对应的代码,所以印象还是不够深刻,只是简单的记得,下面重新学习/回顾一下哈希表算法:


哈希表,也称散列表。

通过散列函数(算法的好坏和散列函数的好坏息息相关,如果散列函数没选好,冲突较多的话,哈希表的效率就无法体现)将数据值和它的存储位置联系起来。即,通过精心地向表插入元素,从而提高访问/查找速度。本例中采取的解决冲突的办法是建立一个小写字母链表(对于默认/没有明显分布规律的英文单词组成的元素集合,这样一种散列函数的思路应该是没什么问题的,虽然没有考虑大写字母的问题),将字符串节点挂在对应位置的后面,根据计算出的散列函数值将元素都添加到这个链表中,可以从头部插入也可以从尾部追加,甚至可以再这个位置后面再挂一个散列表。

代码实现了将文件名按字母a-z分类,不区分大小写。先以数组存储各节点,当扫描发现该元素不存在时即将节点加入链表中(即,通过链接法解决碰撞问题)。然后遍历显示所有的文件名。查找字符串“androi”是否在该散列表中。

代码如下:

上面代码中还存在一个问题:释放手动申请的内存时,只是释放了第一个节点的空间,位于其后的节点没有进行手动释放,因为逻辑上我还有点没弄清楚 ̄□ ̄||,暂时的想法:

思路和show_all()函数很像,通过遍历该hash结构,依次释放遍历到的节点。不过执行起来会出现 Segmentation fault  ̄□ ̄||,我还得再测试测试。

将字符串数组中的元素循环插入哈希表,然后简单测试了一下建立散列表之后的查找功能(代码中查找的是字符串’androi’,当然也可以通过使用命令行参数手动输入或是产生随机字符串进行查找),这里只是为了演示/学习该算法,所以,暂时就先到这了,网上说的虽然也还行,但毕竟不系统,等明天起来再看看书,然后修改修改。


今天早晨起来之后又翻了翻书(本想着是找之前的课本《数据结构》来看的,因为我在上面做了很多笔记,后来发现我在将书打包的时候,将那些非常“重要”的书封装了几层,找出来太过麻烦而且灰尘也厚,所以后来看的是《算法导论》,一堆定理和公式,头发晕……),下面是一些概念性的内容:

散列表
实现字典的一种有效数据结构就是散列表(hash table)。在最坏情况下,在散列表中,查找一个元素的时间与在链表中查找一个元素的时间相同,在最坏情况下都是O(n),但在实践中,散列技术的效率是很高的(这也是人们喜欢用散列技术的原因,在一些合理的假设下,在散列表中查找一个元素的期望时间为O(1))。
散列表是普通数组概念的推广。因为可以对数组进行直接寻址故可以在O(1)的时间内访问数组的任意元素
如果存储空间允许,我们可以提供一个数组,为每个可能的关键字保留一个位置,这时就可以采用“直接寻址技术”。
当实际存储的关键字数比可能的关键字总数要小时,这时采用散列表就会较直接数组寻址更为有效,因为散列表通常采用的数组尺寸与所要存储的关键字数是成比例的。在散列表中,不是直接把关键字用作数组下标,而是根据关键字计算出数组下标(需要解决“碰撞”的问题,所谓碰撞,即多个关键字映射到同一个数组下标位置)。
装载因子 α :给定一个能够存放n个元素的、具有m个槽位的散列表T,定义T的装载因子α为 n/m ,即一个链表中平均存储的元素个数。
1.直接寻址表
当关键字的全域U比较小时,直接寻址是一种简单而有效的技术
2.散列表
直接寻址技术存在一个很明显的问题:当全域U很大,一般的计算机的可用内存容量无法完全装入;而且,如果实际要存储的关键字很少时,会非常浪费空间
所以,当存储在字典中的关键字集合K比所有可能的关键字域U要小得多时,散列表需要的存储空间要比直接寻址表少很多。
通过链接法解决碰撞
在“链接法”中,把散列到同一个槽中的元素都放在一个链表中。插入过程要快些,最坏情况运行时间为O(1),查找操作的最坏运行时间和表的长度成正比。
开放寻址法
在开放寻址法中,所有的元素都存放在散列表中。在这种方法中,散列表可能会被填满,以至于不能插入任何元素,但装载因子α是绝对不会超过1的。
散列方法的平均性态依赖于所选取的散列函数在一般情况下,将所有的关键字分布在m个槽位上的均匀程度。(简单一致散列:任何元素被散列/映射到每一个槽位中的可能性是相同的,并且与其他元素已经被散列到什么位置无关。

参考地址:

声明: 除非注明,ixyzero.com文章均为原创,转载请以链接形式标明本文地址,谢谢!
https://ixyzero.com/blog/archives/842.html

《C语言的哈希表算法的简单学习/回顾》上有5条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注