Day 71:哈希表—链表链接
18年11月5日 · 史二美—北京理工大学 841 人阅读
哈希表
散列表是一种数据结构,它能够以快速、健壮的方式存储和检索数据。结构的α和ω是散列函数。这是一个确定性函数,它接受输入键并将其转换成整数,也称为哈希码。哈希代码用于获取存储值的内部数组中桶的索引。
在下面的例子中,散列函数是由Python通过_ _ hash _ _方法本地提供的,现在几乎任何语言都有某种内置散列方法。当不同的密钥产生相同的散列码时,可能会出现这种情况,这叫做碰撞。有许多方法可以解决它。而这里介绍的解决方案叫做链接。我们在每个桶中保存一个链表,通过提供一组标准链表操作,冲突值保存在同一个链表中。为了能够有效地迭代密钥和值,我们的实现还提供了一个包含哈希表中所有密钥值对的双重链表。
下面列出的HashTable类可能是一个非常标准的实现,便于我们可以经常阅读插入、删除和查找操作可以在预期的O ( 1 )时间内完成。然而,有一个缺陷。预期时间是在分布均匀的[随机数据上测量的。真实数据很少具有这种属性,散列表可能会对分布非常敏感。对于任何散列表实现,都存在一组病态的数据,这些数据将针对单个存储桶。在这种情况下,时间会下降到O ( n )。所以我们应该想出一个解决方案——随机化。
为了让时间回到O ( 1 ),我们必须首先从一系列散列函数中随机选择散列函数。这样,我们就可以得到一个确定性函数,但是,它是随机的,所以插入病理集合的任务变得难以处理,好在哈希表也相当健壮。在大多数情况下,遇到的这不会是一个问题,或者至少不会是一个大到我们会注意到的问题。
这里是我们将在0到1000之间插入几百个随机数后的桶作业。内置哈希函数将会将任何整数X映射到其哈希代码X,哈希( X ) = X。有些同学可能会注意到三分之一的桶永远不会被占用,虽然这不是一个真正的问题,但它表明:在很多的情况下,我们依赖速度,但是我们应该真正注意的是它的行为。
实现代码
测试
Python3Turtle