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，默认的小数组，cpyt免费云主机域名hon 设置的一半的集合对象不会超过这个大小（8），因此在申请一个集合对象的时候直接就申请了这个小数组的内存大小。weakrelist，这个字段主要和垃圾回收有关，这里暂时不进行详细说明。首先先了解一下创建一个集合对象的过程，和前面其他的对象是一样的，首先先申请内存空间，然后进行相关的初始化操作。这个函数有两个参数，使用第一个参数申请内存空间，然后后面一个参数如果不为 NULL 而且是一个可迭代对象的话，就将这里面的对象加入到集合当中。首先我们先大致理清楚往集合当中插入数据的流程：首先根据对象的哈希值，计算需要将对象放在哪个位置，也就是对应数组的下标。查看对应下标的位置是否存在对象，如果不存在对象则将数据保存在对应下标的位置。如果对应的位置存在对象，则查看是否和当前要插入的对象相等，则返回。如果不相等，则使用类似于线性探测的方式去寻找下一个要插入的位置（具体的实现可以查看相关代码，具体的操作为线性探测法 + 开放地址法）。在 cpython 当中对于给哈希表数组扩容的操作，很多情况下都是用下面这行代码，从下面的代码来看对应扩容后数组的大小并不简单，当你的哈希表当中的元素个数大于 50000 时，新数组的大小是原数组的两倍，而如果你哈希表当中的元素个数小于等于 50000，那么久扩大为原来长度的四倍，这个主要是怕后面如果继续扩大四倍的话，可能会浪费很多内存空间。首先需要了解一下扩容机制，当哈希表需要扩容的时候，主要有以下两个步骤：创建新的数组，用于存储哈希表的键。遍历原来的哈希表，将原来哈希表当中的数据加入到新的申请的数组当中。这里需要注意的是因为数组的长度发生了变化，但是 key 的哈希值却没有发生变化，因此在新的数组当中数据对应的下标位置也会发生变化，因此需重新将所有的对象重新进行一次插入操作，下面的整个操作相对来说比较简单，这里不再进行说明了。从集合当中删除元素的代码如下所示：上面的代码相对来说也比较清晰，从 finger 开始寻找存在的元素，并且删除他。我们在前面提到过，当一个元素被删除之后他会被赋值成 dummy 而且哈希值为 -1 。“Python集合set实现原理源码分析”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注百云主机网站，小编将为大家输出更多高质量的实用文章！

相关推荐: 怎么在Server上搭建PHP环境

本文小编为大家详细介绍“怎么在Server上搭建PHP环境”，内容详细，步骤清晰，细节处理妥当，希望这篇“怎么在Server上搭建PHP环境”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。 第一步：安装Apache在Server服务器…