如何在C中使用结构和数组演示散列及其在初学者中的应用:简易方法-第4部分(链式)

这是有关散列和散列冲突的文章系列的第四篇也是最后一部分,前三部分是清楚理解本部分并处理较早概念的前提,可以在下面的链接中找到这些概念。 哈希:Part1哈希的应用:演示Part2哈希冲突:Part3 在第3部分中,讨论了哈希冲突和开放寻址下解决冲突的各种方法。 在本文中,通过演示示例详细讨论了通过链解决冲突。 链接是哈希解析的一种非常简单的方法,在此方法中,冲突键存储为链接列表,哈希值用作哈希表的索引。 简单来说,具有相同散列值的所有键都存储为链接列表,并且基于散列表中的散列值存储链接列表的根/头。 因此,在发生冲突的情况下,会将新节点插入到链表中,基于哈希值从哈希表中获取头/根值。 因此,基本上,哈希表可以看作是许多链接列表的根的数组,并且具有相同哈希值的所有键都将进入同一链接列表。 继续我们先前的演示应用程序,在m = 11的乘法哈希处理中,滚动号136001和136009都产生相同的哈希值2。不同的冲突解决方法存储的136009记录不同,但索引与哈希值不同。 现在,在链接这些记录并创建一个链表时,此链表的头将存储在基于哈希值即2的哈希表的索引2处。 实作 链接方法的实现与单链表非常相似。 以下是两个示例,第一个示例演示如何使用链接存储记录,然后全部打印它们,第二个示例演示基于键的特定记录搜索。 随着本系列的散列工作的结束。 请写出任何建议或改进。

菲尔的数据结构动物园

以编程方式解决问题通常涉及将数据项分组在一起,以便可以方便地对它们进行操作或将其复制为单个单元-将这些项收集在数据结构中 。 在过去的几十年中,已经设计了许多不同的数据结构,其中一些存储单个项目,例如电话号码,另一些存储更复杂的对象,例如名称/电话号码对 。 每个都有优点和缺点,或多或少适合特定的用例。 在本文中,我将描述并尝试按三种不同的摘要级别对一些最流行的数据结构及其实际实现进行分类,这些层次从柏拉图式理想开始,以基准测试的实际代码结束: 理论级别:无论具体实现如何,都将描述数据结构/收集类型,并列出其核心操作的渐近行为。 实现级别:将显示特定编程语言的容器类如何与上一级别引入的数据结构相关联-例如,尽管名称相似,但Java的Vector与Scala或Clojure的Vector实现不同。 另外,将为每个实现类提供核心操作的渐进复杂性。 经验级别:将测量数据结构效率的两个方面:将在不同配置下确定容器类的内存占用量。 将测量操作的运行时性能,这将证明渐进优势的扩展体现在具体场景中,以及渐近相等结构的相对性能是什么。 在第三部分中提供实际的速度和空间测量结果之前,可以根据数据结构可能存储的项数以抽象的方式描述执行时间和空间。 传统上,这是通过Big O表示法完成的,并且在表中使用以下缩写: C是恒定时间O(1) aC摊销固定时间 eC是有效的恒定时间 对数是对数时间,O(log…