python 列表 元组 字典 集合,Python 列表 字典 集合

　　字典和集合的效率是无法和它们背后的哈希表相比的。

　　哈希表实际上是一个稀疏数组。总是有空元素的数组称为稀疏数组。哈希表中的单元称为桶。在dict的哈希表中，每个键/值对使用一个表元素。每个表元素都有两个部分：对键的引用和对值的引用。因为单元格大小相同，所以可以通过偏移量读取单元格。确保大约三分之一的python原语是空的。当接近该阈值时，原始哈希表将被复制到更大的空间中。

　　哈希值相等：

　　的内置hash__方法是调用方的__hash__。如果两个对象比较时相等，那么它们的哈希值一定相等吗？也就是说，它们的__hash__必须相等。

　　例如，如果1==1.0为真，那么hash(1)==hash)也必须为真。

　　哈希表算法：

　　为了得到字典值dict[key]，python首先调用hash(调用key计算key的哈希值)，然后取值的最后几位(具体看哈希表的大小)作为偏移量。当使用哈希表时，如果插入的表元素为空，它会抛出一个KeyError异常。如果不为空，则表元素有一个found_key:found_value对。此时，python检查key==found_key是否为真，如果相等，则返回found_value。字典的搜索结束了。

　　以上是key和found_key不一致的情况。这被称为哈希冲突。这是因为哈希表将随机元素映射到几个数字，哈希表本身的索引只依赖于那个数字。为了解决哈希冲突，算法从哈希值中再取几个数，进行处理，然后以新得到的数为索引再次搜索原语。重复上述步骤。如果得到一个空的slow KeyError异常，如果匹配，就返回值。如果吐出来，如果有哈希冲突，就重复这个过程。

　　以上是获取字典值的算法，添加或修改新值的操作大致相同。

　　Dict实现和结果键必须被散列。

　　Hashable对象，hash(支持函数，__hash__)中得到的哈希值不变，支持__eq__)方法测试等价性，a==b=b。

　　默认情况下，所有用户定义的对象都是可哈希的。因为哈希值是通过id()获得的，所以它们不相等。

　　字典的内存开销很大。

　　因为字典使用哈希表，所以哈希表必须是稀疏数组，这样会降低空间效率。Dict是典型的空间交换时间。如果想保存大量数据，发端是更好的选择。

　　关键字查询速度很快

　　字典的内存开销很大，数据的高速访问会被忽略。数据量大对词典检索速度影响不大。

　　键的顺序取决于它们被添加的顺序。

　　如果在dict中添加了一个新的键，并且存在哈希冲突，那么这个新键可能会被放在另一个位置。这很可能会导致不同的添加顺序和字典顺序。

　　添加一个键可能会改变现有的顺序。

　　Python可能会在每次添加新内容时决定扩展字典。添加新的哈希表，并将现有元素放入新的哈希表中。在此过程中，可能会出现新的哈希冲突，并且可能会更改新字典的顺序。

　　《原则和规则》的实施和结果

　　set和frozenset的实现也依赖于哈希表，但是对功能的引用存储在哈希表中(请参见)。

　　Set和dict的特点一样，有上面的1到5点。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。