字典是 Python 中最通用的数据结构之一。dict 可以将一组唯一键映射到对应的值如下所示{1: ’ one’,2: ’ two’,3: ’ three’,}字典是你应该已经了解的基本内容。不管怎样程序员还可以用和前面列表推导类似的推导来创建一个新的字典。这里有一个非常简单的例子如下所示squares {number: number**2 for number in range(100)}重要的是使用字典推导具有与列表推导相同的优点。因此在许多情况下字典推导要更加高效、更加简短、更加整洁。对于更复杂的代码而言需要用到许多 if 语句或函数调用来创建一个字典这时最好使用简单的 for 循环尤其是它还提高了可读性。对于刚刚接触 Python 3 的 Python 程序员来说在遍历字典元素时有一点需要特别注意。字典的 keys()、values()和 items()3 个方法的返回值类型不再是列表。此外与之对应的 iterkeys()、itervalues()和 iteritems()本来返回的是迭代器而 Python 3 中并没有这 3 个方法。现在 keys()、values()和 items()返回的是视图对象view objects。• keys()返回 dict_keys 对象可以查看字典的所有键。• values()返回 dict_values 对象可以查看字典的所有值。• items()返回 dict_items 对象可以查看字典所有的(key, value)二元元组。视图对象可以动态查看字典的内容因此每次字典发生变化时视图都会相应改变见下面这个例子words {‘foo’: ‘bar’, ‘fizz’: ‘bazz’}items words.items()words[‘spam’] ‘eggs’itemsdict_ _items([(‘spam’, ‘eggs’), (‘fizz’, ‘bazz’), (‘foo’, ‘bar’)])视图对象既有旧的 keys()、values()和 items()方法返回的列表的特性也有旧的 iterkeys()、itervalues()和 iteritems()方法返回的迭代器的特性。视图无需冗余地将所有值都保存在内存里像列表那样但你仍然可以获取其长度使用 len也可以测试元素是否包含其中使用 in 子句。当然视图是可迭代的。最后一件重要的事情是在 keys()和 values()方法返回的视图中键和值的顺序是完全对应的。在 Python 2 中如果你想保证获取的键和值顺序一致那么在两次函数调用之间不能修改字典的内容。现在 dict_keys 和 dict_values 是动态的所以即使在调用 keys()和 values()之间字典内容发生了变化那么这两个视图的元素遍历顺序也是完全一致的。实现细节CPython 使用伪随机探测pseudo-random probing的散列表hash table作为字典的底层数据结构。这似乎是非常高深的实现细节但在短期内不太可能发生变化所以程序员也可以把它当做一个有趣的事实来了解。由于这一实现细节只有可哈希的hashable对象才能作为字典的键。如果一个对象有一个在整个生命周期都不变的散列值hash value而且这个值可以与其他对象进行比较那么这个对象就是可哈希的。Python 所有不可变的内置类型都是可哈希的。可变类型如列表、字典和集合是不可哈希的因此不能作为字典的键。定义可哈希类型的协议包括下面这两个方法。•hash这一方法给出 dict 内部实现需要的散列值整数。对于用户自定义类的实例对象这个值由 id()给出。•eq比较两个对象的值是否相等。对于用户自定义类除了自身之外所有实例对象默认不相等。如果两个对象相等那么它们的散列值一定相等。反之则不一定成立。这说明可能会发生散列冲突hash collision即散列值相等的两个对象可能并不相等。这是允许的所有 Python 实现都必须解决散列冲突。CPython 用开放定址法open addressing来解决这一冲突https://en.wikipedia.org/wiki/Open_addressing。不过发生冲突的概率对性能有很大影响如果概率很高字典将无法从其内部优化中受益。字典的 3 个基本操作添加元素、获取元素和删除元素的平均时间复杂度为 O(1)但它们的平摊最坏情况复杂度要高得多为 O(n)这里的 n 是当前字典的元素数目。此外如果字典的键是用户自定义类的对象并且散列方法不正确的话发生冲突的风险很大那么这会给字典性能带来巨大的负面影响。CPython 字典的时间复杂度的完整表格如表 2-2 所示。表 2-2操作 平均复杂度 平摊最坏情况复杂度获取元素 O(1) O(n)修改元素 O(1) O(n)删除元素 O(1) O(n)复制 O(n) O(n)遍历 O(n) O(n)还有很重要的一点需要注意在复制和遍历字典的操作中最坏情况复杂度中的 n 是字典曾经达到的最大元素数目而不是当前元素数目。换句话说如果一个字典曾经元素个数很多后来又大大减少了那么遍历这个字典可能要花费相当长的时间。因此在某些情况下如果需要频繁遍历某个字典那么最好创建一个新的字典对象而不是仅在旧字典中删除元素。
Python 高手编程系列十三：字典
字典是 Python 中最通用的数据结构之一。dict 可以将一组唯一键映射到对应的值如下所示{1: ’ one’,2: ’ two’,3: ’ three’,}字典是你应该已经了解的基本内容。不管怎样程序员还可以用和前面列表推导类似的推导来创建一个新的字典。这里有一个非常简单的例子如下所示squares {number: number**2 for number in range(100)}重要的是使用字典推导具有与列表推导相同的优点。因此在许多情况下字典推导要更加高效、更加简短、更加整洁。对于更复杂的代码而言需要用到许多 if 语句或函数调用来创建一个字典这时最好使用简单的 for 循环尤其是它还提高了可读性。对于刚刚接触 Python 3 的 Python 程序员来说在遍历字典元素时有一点需要特别注意。字典的 keys()、values()和 items()3 个方法的返回值类型不再是列表。此外与之对应的 iterkeys()、itervalues()和 iteritems()本来返回的是迭代器而 Python 3 中并没有这 3 个方法。现在 keys()、values()和 items()返回的是视图对象view objects。• keys()返回 dict_keys 对象可以查看字典的所有键。• values()返回 dict_values 对象可以查看字典的所有值。• items()返回 dict_items 对象可以查看字典所有的(key, value)二元元组。视图对象可以动态查看字典的内容因此每次字典发生变化时视图都会相应改变见下面这个例子words {‘foo’: ‘bar’, ‘fizz’: ‘bazz’}items words.items()words[‘spam’] ‘eggs’itemsdict_ _items([(‘spam’, ‘eggs’), (‘fizz’, ‘bazz’), (‘foo’, ‘bar’)])视图对象既有旧的 keys()、values()和 items()方法返回的列表的特性也有旧的 iterkeys()、itervalues()和 iteritems()方法返回的迭代器的特性。视图无需冗余地将所有值都保存在内存里像列表那样但你仍然可以获取其长度使用 len也可以测试元素是否包含其中使用 in 子句。当然视图是可迭代的。最后一件重要的事情是在 keys()和 values()方法返回的视图中键和值的顺序是完全对应的。在 Python 2 中如果你想保证获取的键和值顺序一致那么在两次函数调用之间不能修改字典的内容。现在 dict_keys 和 dict_values 是动态的所以即使在调用 keys()和 values()之间字典内容发生了变化那么这两个视图的元素遍历顺序也是完全一致的。实现细节CPython 使用伪随机探测pseudo-random probing的散列表hash table作为字典的底层数据结构。这似乎是非常高深的实现细节但在短期内不太可能发生变化所以程序员也可以把它当做一个有趣的事实来了解。由于这一实现细节只有可哈希的hashable对象才能作为字典的键。如果一个对象有一个在整个生命周期都不变的散列值hash value而且这个值可以与其他对象进行比较那么这个对象就是可哈希的。Python 所有不可变的内置类型都是可哈希的。可变类型如列表、字典和集合是不可哈希的因此不能作为字典的键。定义可哈希类型的协议包括下面这两个方法。•hash这一方法给出 dict 内部实现需要的散列值整数。对于用户自定义类的实例对象这个值由 id()给出。•eq比较两个对象的值是否相等。对于用户自定义类除了自身之外所有实例对象默认不相等。如果两个对象相等那么它们的散列值一定相等。反之则不一定成立。这说明可能会发生散列冲突hash collision即散列值相等的两个对象可能并不相等。这是允许的所有 Python 实现都必须解决散列冲突。CPython 用开放定址法open addressing来解决这一冲突https://en.wikipedia.org/wiki/Open_addressing。不过发生冲突的概率对性能有很大影响如果概率很高字典将无法从其内部优化中受益。字典的 3 个基本操作添加元素、获取元素和删除元素的平均时间复杂度为 O(1)但它们的平摊最坏情况复杂度要高得多为 O(n)这里的 n 是当前字典的元素数目。此外如果字典的键是用户自定义类的对象并且散列方法不正确的话发生冲突的风险很大那么这会给字典性能带来巨大的负面影响。CPython 字典的时间复杂度的完整表格如表 2-2 所示。表 2-2操作 平均复杂度 平摊最坏情况复杂度获取元素 O(1) O(n)修改元素 O(1) O(n)删除元素 O(1) O(n)复制 O(n) O(n)遍历 O(n) O(n)还有很重要的一点需要注意在复制和遍历字典的操作中最坏情况复杂度中的 n 是字典曾经达到的最大元素数目而不是当前元素数目。换句话说如果一个字典曾经元素个数很多后来又大大减少了那么遍历这个字典可能要花费相当长的时间。因此在某些情况下如果需要频繁遍历某个字典那么最好创建一个新的字典对象而不是仅在旧字典中删除元素。
