Python 字典实现原理

本文主要是介绍Python 字典实现原理，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Python里的实现用了一种被称为散列表（hash table，也被称为哈希表）的更高效的数据结构。

散列表的核心是散列函数（hashing function，也被称为哈希函数）。散列函数会把键作为参数，然后对它执行一些简单的计算从而生成一个数字。由于计算机上的所有数据最终都按比特（二进制数）存储，因此可以很容易地找到一个合适的散列函数。Python也有一个内置的函数hash来实现这个散列函数。你可以通过下面这样的交互操作来进行尝试：

>>> hash(2)
2
>>> hash(3.4)
922337203685477379
>>> hash(3.4)
922337203685477379
>>> hash('c')
2429946187753368536
>>> hash(None)
8795546022280
>>> hash((1,'spam'))
-5029320327249233509
>>> hash([1,2,3])
Traceback (most recent call last):
  File "<pyshell#6>", line 1, in <module>
    hash([1,2,3])
TypeError: unhashable type: 'list'
>>> 

提供任何“能够被散列”的东西给hash函数都会产生一个int结果。注意看最后两次交互操作。元组是可以被散列的，但列表则不行。散列函数的一个要求是，无论何时，调用它去处理特定的对象，它都必须始终计算出完全相同的结果。由于散列函数依赖于对象的底层存储方式来生成散列值，因此在对象的底层存储方式不会发生变化的时候，能够保证这个值是有效的。换句话说，我们只能散列贫血对象（不可变的对象）。像数字、字符串和元组都是不可变的，因此它们可以被散列。然而，因为列表是可以被修改的，所以Python不允许对它们进行散列操作。

只要有一个合适的散列函数，就可以简单地创建一个散列表来实现字典了。散列表实际上只是一个用来存储(key, value)键值对的大型列表。然而，这些“对”并不是一个接一个地被顺序存储的，而是会被存储在列表中的散列键所确定的索引处。比如，假设我们分配了一个大小为1000的列表（这就是我们的“表”）。为了存储键值对(“c”，“Clubs”)，我们会先计算hash(“c”) % 1000=226。因此，这个元素将会被存储在位置226。在这里，余数操作可以保证我们得到的结果在range(1000)范围内，这个值会是我们表里的一个有效索引。当有一个恰当的散列函数时，元素将会以相对平均的方式分布在整个表格之中。

只要字典中没有两个键被散列到完全相同的位置，这个实现就会非常高效。插入一个新元素需要花费常量时间，因为我们只需要应用散列函数，然后把这个元素分配到列表中对应的位置。查找会有类似的复杂性，我们还是先计算散列值，然后我们就能够知道应该去哪里找到元素了。要删除一个元素，我们只需将一个特殊的标记（例如None）放到相应的位置。因此，所有基本的字典操作都可以在常量Θ(1)时间内完成。

那么，当两个键被散列到同一个位置时会发生什么呢？这种现象被称为碰撞（collision）。现在，你只需要知道已经有很好的技术来处理这个问题就行了。在使用了这些技术并确保有足够大小的表格之后，就可以建立一个允许常量时间操作的数据结构了。所以，Python的词典非常高效，只要你有足够多的可用内存，你就可以轻松地处理成千上万甚至是几百万条条目了。并且，Python解释器本身就在很大程度上依赖于使用字典来维护命名空间，所以字典的实现已经经过了高度的优化

总结

• python字典通过散列表这种数据结构实现
• 列表不能求哈希值

这篇关于Python 字典实现原理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！