Python虚拟机集合set实现原理是什么


本文小编为大家详细介绍免费云主机域名“Python虚拟机集合set实现原理是什么”,内容详细,步骤清晰,细节处理妥当,希望这篇“Python虚拟机集合set实现原理是什么”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。上面的数据结果用图示如下图所示:上面各个字段的含义如下所示:dummy entries :如果在哈希表当中的数组原来有一个数据,如果我们删除这个 entry 的时候,对应的位置就会被赋值成 dummy,与 dummy 有关的定义在上面的代码当中已经给出,dummy 对象的哈希值等于 -1。明白 dummy 的含义之后,fill 和 used 这两个字段的含义就比较容易理解了,used 就是数组当中真实有效的对象的个数,fill 还需要加上 dummy 对象的个数。mask,数组的长度等于 2n2^n2n,mask 的值等于 2n−12^n – 12n−1 。table,实际保存 entry 对象的数组。hash,这个值对 frozenset 有用,保存计算出来的哈希值。如果你的数组很大的话,计算哈希值其实也是一个比较大的开销,因此可以将计算出来的哈希值保存下来,以便下一次求的时候可以将哈希值直接返回,这也印证了在 python 当中为什么只有 immutable 对象才能够放入到集合和字典当中,因为哈希值计算一次保存下来了,如果再加入对象对象的哈希值也会变化,这样做就会发生错误了。finger,主要是用于记录下一个开始寻找被删除对象的下标。smalltable,默认的小数组,cpython 设置的一半的集合对象不会超过这个大小(8),因此在申请一个集合对象的时候直接就申请了这个小数组的内存大小。weakrelist,这个字段主要和垃圾回收有关,这里暂时不进行详细说明。首先先了解一下创建一个集合对象的过程,和前面其他的对象是一样的,首先先申请内存空间,然后进行相关的初始化操作。这个函数有两个参数,使用第一个参数申请内存空间,然后后面一个参数如果不为 NULL 而且是一个可迭代对象的话,就将这里面的对象加入到集合当中。首先我们先大致理清楚往集合当中插入数据的流程:首先根据对象的哈希值,计算需要将对象放在哪个位置,也就是对应数组的下标。查看对应下标的位置是否存在对象,如果不存在对象则将数据保存在对应下标的位置。如果对应的位置存在对象,则查看是否和当前要插入的对象相等,则返回。如果不相等,则使用类似于线性探测的方式去寻找下一个要插入的位置(具体的实现可以查看相关代码,具体的操作为线性探测法 + 开放地址法)。在 cpython 当中对于给哈希表数组扩容的操作,很多情况下都是用下面这行代码,从下面的代码来看对应扩容后数组的大小并不简单,当你的哈希表当中的元素个数大于 50000 时,新数组的大小是原数组的两倍,而如果你哈希表当中的元素个数小于等于 50000,那么久扩大为原来长度的四倍,这个主要是怕后面如果继续扩大四倍的话,可能会浪费很多内存空间。首先需要了解一下扩容机制,当哈希表需要扩容的时候,主要有以下两个步骤:创建新的数组,用于存储哈希表的键。遍历原来的哈希表,将原来哈希表当中的数据加入到新的申请的数组当中。这里需要注意的是因为数组的长度发生了变化,但是 key 的哈希值却没有发生变化,因此在新的数组当中数据对应的下标位置也会发生变化,因此需重新将所有的对象重新进行一次插入操作,下面的整个操作相对来说比较简单,这里不再进行说明了。从集合当中删除元素的代码如下所示:上面的代码相对来说也比较清晰,从 finger 开始寻找存在的元素,并且删除他。我们在前面提到过,当一个元素被删除之后他会被赋值成 dummy 而且哈希值为 -1 。读到这里,这篇“Python虚拟机集合set实现原理是什么”文章已经介绍完毕,想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会,如果想了解更多相关内容的文章,欢迎关注百云主机行业资讯频道。

相关推荐: C语言怎么实现弹跳小球效果

本文小编为大家详细介绍“C语言怎么实现弹跳小球效果”,内容详细,步骤清晰,细节处理妥当,希望这篇“C语言怎么实现弹跳小球效果”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。项目描述: 使小球来回的跳动,跳动的路径是一个 “V “字型效…

免责声明:本站发布的图片视频文字,以转载和分享为主,文章观点不代表本站立场,本站不承担相关法律责任;如果涉及侵权请联系邮箱:360163164@qq.com举报,并提供相关证据,经查实将立刻删除涉嫌侵权内容。

(0)
打赏 微信扫一扫 微信扫一扫
上一篇 05/26 09:06
下一篇 05/26 09:17

相关推荐