Geekly articles weekly

Python中的字典实现

大家好，4月30日，“ 面向开发人员的算法”课程从OTUS开始，今天的材料专门为此出版。 让我们开始吧。



在本文中，您将学习如何在Python中实现字典。
使用键对字典进行索引，并且可以将它们视为关联的数组。 让我们在字典中添加3个键/值对：

>>> d = {'a': 1, 'b': 2} >>> d['c'] = 3 >>> d {'a': 1, 'b': 2, 'c': 3}

可以按以下方式访问值：

 >>> d['a'] 1 >>> d['b'] 2 >>> d['c'] 3 >>> d['d'] Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 'd'

键“d”不存在，因此会发生KeyError错误。

哈希表

Python中的字典是使用哈希表实现的。 它们是其索引是使用哈希函数计算的数组。 哈希函数的目标是将键均匀分布在数组中。 良好的哈希函数可最大程度地减少冲突次数，即 不同键具有相同哈希值的可能性。 Python中没有此类哈希函数。 在一般情况下，其最重要的哈希函数（对于字符串和整数值）会产生相似的值：

 >>> map(hash, (0, 1, 2, 3)) [0, 1, 2, 3] >>> map(hash, ("namea", "nameb", "namec", "named")) [-1658398457, -1658398460, -1658398459, -1658398462]

我们假定直到本文结束之前，我们将使用字符串作为键。 Python中用于字符串的哈希函数定义如下：

 arguments: string object returns: hash function string_hash: if hash cached: return it set len to string's length initialize var p pointing to 1st char of string object set x to value pointed by p left shifted by 7 bits while len >= 0: set var x to (1000003 * x) xor value pointed by p increment pointer p set x to x xor length of string object cache x as the hash so we don't need to calculate it again return x as the hash

如果您在Python中执行hash('a') ，它将12416037344 string_hash()并返回12416037344 。 在这里，我们默认使用64位计算机。

如果使用大小为的数组存储值/键对，则将使用掩码来计算数组中该单元格的单元格的索引，该索引的计算值为-1 。 这种方法可以快速计算单元格索引。 由于调整大小的机制，找到一个空单元的可能性很高，这将在下面进行描述。 这意味着在大多数情况下，简单的计算就很有意义。 数组的大小为8， 'a'的索引为： hash('a') & 7 = 0 。 就像'b'一样， 'b'的索引是2， 'c'的索引是3， 'z'的索引是3，这就是我们发生碰撞的地方。



正如我们所看到的，当键是顺序的时，Python中的哈希函数可以很好地完成其工作，这很好，因为您经常必须使用此类数据。 但是，一旦添加'z'键，就会发生冲突，因为它与先前的不一致。

我们可以使用链表来存储对，同时具有相同的哈希值，但这会增加搜索时间，并且平均不等于O（1）。 下一节描述了Python中字典使用的冲突解决方法。

开放式寻址

开放寻址是一种使用探测的冲突解决技术。 在'z'的情况下，数组中已经使用了单元3的索引，因此我们需要寻找另一个尚未使用的索引。 添加键/值对的操作以及搜索操作平均要花费O（1）。

为了搜索自由细胞，使用了二次探测序列。 它的实现如下：

 j = (5*j) + 1 + perturb; perturb >>= PERTURB_SHIFT; use j % 2**i as the next table index;

（5 * j）+1处的递归迅速增加了不影响原始索引的较大位差异。 在这种情况下，变量"perturb"接收哈希码的其他位。

出于好奇，让我们看看如果我们有一个表大小为32且j = 3的样本序列会发生什么。

3-> 11-> 19-> 29-> 5-> 6-> 16-> 31-> 28-> 13-> 2 ...

您可以通过参考源代码dictobject.c了解有关此探测序列的更多信息。 探测机制的详细说明可以在文件顶部找到。



让我们用这个例子看一下Python源代码。

C字典结构

以下C结构用于将条目存储在字典中：键/值对。 哈希，键和值被存储。 PyObject是Python中对象的基类。

 typedef struct { Py_ssize_t me_hash; PyObject *me_key; PyObject *me_value; } PyDictEntry;

以下结构是一个字典。 ma_fill是已使用和无效的单元格总数。 当删除密钥对时，单元被认为是不活动的。 ma_used是已使用（活动）单元的数量。 ma_mask等于-1数组的大小，用于计算单元ma_mask引。 ma_table是一个数组， ma_smalltable是大小为8的原始数组。

 typedef struct _dictobject PyDictObject; struct _dictobject { PyObject_HEAD Py_ssize_t ma_fill; Py_ssize_t ma_used; Py_ssize_t ma_mask; PyDictEntry *ma_table; PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); PyDictEntry ma_smalltable[PyDict_MINSIZE]; };

词汇初始化

当您仅创建字典时，将PyDict_New()函数。 我删除了几行，然后将C代码转换为伪代码以关注关键概念。

PyDict_New()函数：

  • 返回字典对象；
  • 分配一个新的字典对象；
  • 清除字典表；
  • 将已使用的字典单元格和未使用的单元格数（ ma_fill ）设置为0；
  • 将活动单元数（ ma_used ）设置为0； ma_used将其设置为0。
  • 将字典掩码（ ma_value ）设置为等于字典大小的值-1 = 7;
  • 设置字典搜索功能lookdict_string ;
  • 返回分配的字典对象。

新增项目

添加新的键/值对时， PyDict_SetItem()调用PyDict_SetItem() 。 此函数接受指向字典对象的指针和键/值对作为输入。 它检查键是否为字符串，并评估哈希值或重用缓存（如果存在）。 如果使用和未使用的单元格数大于数组大小的2/3，则将调用insertdict()以添加新的键/值对，并且字典大小也会更改。

为什么是2/3？ 这是确保探针序列可以足够快地找到游离细胞所必需的。 稍后我们将考虑调整大小的功能。

 arguments: dictionary, key, value returns: 0 if OK or -1 function PyDict_SetItem: if key's hash cached: use hash else: calculate hash call insertdict with dictionary object, key, hash and value if key/value pair added successfully and capacity over 2/3: call dictresize to resize dictionary's table

inserdict()使用lookdict_string()搜索功能查找空闲单元。 使用相同的功能搜索关键字。

lookdict_string()使用哈希值和掩码值计算单元lookdict_string()引。 如果无法通过单元索引=哈希和掩码（插槽索引=哈希和掩码）的值找到密钥，则她将使用上述循环开始探测，直到找到空闲的单元。 在第一次尝试进行探测时，如果键为null ，则如果在第一次搜索期间找到了未使用的单元格，它将返回一个未使用的单元格。 这样可以确保重用先前删除的单元格的优先级。
我们要添加以下键/值对： {'a': 1, 'b': 2′, 'z': 26, 'y': 25, 'c': 5, 'x': 24} 。 将会发生以下情况：

分配给字典结构的表大小为8。

  • PyDict_SetItem：键='a'，值= 1
    • 哈希=哈希（'a'）= 12416037344
    • insertdict
      • lookdict_string
        • 广告位索引=哈希和掩码= 12416037344＆7 = 0
        • 未使用插槽0，请返回此单元格
      • 使用键，值和哈希值对索引0处的条目进行初始化
      • ma_used = 1，ma_fill = 1
  • PyDict_SetItem：键='b'，值= 2
    • 哈希=哈希（'b'）= 12544037731
    • insertdict
      • lookdict_string
        • 广告位索引=哈希和掩码= 12544037731＆7 = 3
        • 未使用插槽3，请返回此单元格
      • 使用键，值和哈希值对索引3处的条目进行初始化
      • ma_used = 2，ma_fill = 2
  • PyDict_SetItem：键='z'，值= 26
    • 哈希=哈希（'z'）= 15616046971
    • insertdict
      • lookdict_string
        • 广告位索引=哈希和掩码= 15616046971＆7 = 3
        • 使用了插槽3，请尝试另一个单元：5是空闲的

        使用键，值和哈希值对索引5处的条目进行初始化
        ma_used = 3，ma_fill = 3
  • PyDict_SetItem：键='y'，值= 25
    • 哈希=哈希（'y'）= 15488046584
    • insertdict
      • lookdict_string
        • 广告位索引=哈希和掩码= 15488046584＆7 = 0
        • 使用了插槽0，请尝试其他单元：1空闲
      • 使用键，值和哈希值对索引1处的条目进行初始化
      • ma_used = 4，ma_fill = 4

PyDict_SetItem：键='c'，值= 3
  • 哈希=哈希（'c'）= 12672038114
  • insertdict
    • lookdict_string
      • 广告位索引=哈希和掩码= 12672038114＆7 = 2
      • 未使用插槽2，请返回此单元格
    • 使用键，值和哈希值对索引2处的条目进行初始化
    • ma_used = 5，ma_fill = 5

PyDict_SetItem：键='x'，值= 24
  • 哈希=哈希（'x'）= 15360046201
  • insertdict
    • lookdict_string
      • 插槽索引=哈希和掩码= 15360046201＆7 = 1
      • 使用了插槽1，请尝试另一个单元：7是空闲的
    • 使用键，值和哈希值对索引7处的条目进行初始化
    • ma_used = 6，ma_fill = 6

这是我们得到的：



现在使用了8个单元中的6个，占据了阵列容量的2/3以上。 dictresize()分配更大的数组。 此功能还将记录从旧表复制到新表。

在本例中， dictresize ()值minused = 24，其中4 * ma_used 。 当使用的单元数非常大（大于50,000）时，将使用2 * ma_used 。 为什么细胞增加4倍？ 这减少了实现调整大小的步骤数量，并增加了稀疏性。

该表的新大小应大于24，它是通过将当前大小向左移动1位直到表的大小变得大于24来计算的。结果，它将是32，例如8-> 16-> 32。

调整大小时，我们的表发生了什么：突出显示了一个大小为32的新表，使用新的掩码值31将旧表项插入到新表中，结果如下：



删除项目

PyDict_DelItem()删除记录。 计算记录键的哈希值，然后调用搜索函数以返回记录。 现在该单元为空。

我们要从字典中删除c键。 结果，我们得到以下数组：



请注意，如果使用的单元格数量远小于其总数，则删除元素的操作不会更改数组的大小。 但是，当添加键/值对时，是否需要调整大小取决于使用和未使用的单元格的数量，因此添加操作还可以减少数组。

该出版物已经结束，我们通常会等待您的评论，并邀请所有人参加将于4月18日举行的公开课 。

Source: https://habr.com/ru/post/zh-CN448350/

More articles:


All Articles