Python学习[3]—数据结构: 词典和集合dict and set

Python中的词典（dict）和集合（set）是两种重要的数据结构，它们都依赖于哈希表实现高效的数据存储和检索。以下是对这两种数据结构的详细解析：

1. Hashable的定义

一个对象要成为哈希表中的键，必须满足以下条件：

生命周期内哈希值不变：对象必须实现__hash__()方法，确保在其生命周期内哈希值不变。
可比较性：对象需实现__eq__()方法，以便与其他对象进行比较。
相同值的哈希一致性：若两个对象相等，则它们的哈希值也必须相同。

示例：

可哈希类型：元组（tuple）、字符串（str）、冻结集合（frozenset）等不可变类型。
不可哈希类型：列表（list）、字典（dict）、集合（set）等可变类型。

>>> tt = (1, 2) # tuple>>> hash(tt)-3550055125485641917>>> tt = 'dafae' # string>>> hash(tt)8556443493751015873>>> tt = [2, 3, 4] # list>>> hash(tt)TypeError: unhashable type: 'list'2. Mapping类型

Python的collections.abc模块提供了Mapping和MutableMapping抽象基类，作为字典和其他映射类型的接口。

>>> import collections.abc as abc>>> my_dict = {}>>> isinstance(my_dict, abc.Mapping)True3. dict类

字典是键值对的集合，其中键必须是可哈希的。字典支持多种构建方式：

>>> a = dict(one=1, two=2, three=3)>>> b = {'one': 1, 'two': 2, 'three': 3}>>> c = dict(zip(['one', 'two', 'three'], [1, 2, 3]))>>> d = dict([('one', 1), ('three', 3), ('two', 2)])>>> e = dict({'three': 3, 'one': 1, 'two': 2})>>> print(a == b == c == d == e)True字典推导式（dictcomps）

字典推导式提供了一种简洁的构建字典的方式：

>>> data = [(1, "one"), (2, "two"), (11, "eleven"), (5, "five"), (8, "eight")]>>> data_dict = {i: j for i, j in data if i > 3}>>> data_dict{11: 'eleven', 5: 'five', 8: 'eight'}处理缺失键的方法

setdefault方法：若键存在，返回其值；否则，插入键并设置默认值。
>>> d = {'1': [1, 2, 3], '3': [1]}>>> d.setdefault('2', []).append(2)>>> d{'1': [1, 2, 3], '3': [1], '2': [2]}
defaultdict：自动处理缺失键，为其设置默认值。
>>> import collections>>> d = collections.defaultdict(list, {'1': [1, 2, 3], '3': [1]})>>> d['2'].append(2)>>> ddefaultdict(<class 'list'>, {'1': [1, 2, 3], '3': [1], '2': [2]})

字典的变体

OrderedDict：保持键的插入顺序。
ChainMap：管理多个映射的视图。
Counter：用于计数可哈希对象。
>>> a = collections.Counter('addjjjddd')>>> aCounter({'d': 5, 'j': 3, 'a': 1})>>> a.update('dddaae')>>> aCounter({'d': 8, 'a': 3, 'j': 3, 'e': 1})>>> a.most_common(1)[('d', 8)]
UserDict：便于自定义字典类。
>>> class userdict(collections.UserDict):... def __setitem__(self, key, item):... self.data[str(key)] = item + '-add'>>> a = userdict({1: '1', 2: '2'})>>> a{'1': '1-add', '2': '2-add'}
MappingProxyType：创建不可变映射。

4. set、frozenset类

集合是无序不重复元素的集合，分为可变集合（set）和不可变集合（frozenset）。集合支持多种集合运算：

>>> a = {'a', 'b', 'c'}>>> d = {'d', 'c'}>>> a & d # 交集{'c'}>>> a | d # 并集{'b', 'c', 'a', 'd'}>>> a.pop() # 随机移除并返回元素'b'>>> {'a'} <= a # 子集检查True5. dict、set与哈希表

字典和集合通过哈希表实现高效查找。查找过程如下：

计算键的哈希值。
根据哈希值定位存储桶（bucket）。
若桶为空，抛出KeyError；否则，检查键是否匹配。
若哈希冲突，重新计算哈希值并重复查找。

哈希表需保持稀疏以减少冲突，确保高效性能。

总结

字典和集合是Python中强大的数据结构，利用哈希表实现快速查找和操作。理解其底层机制有助于编写高效代码，并根据需求选择合适的变体或处理方法。

您可能感兴趣问答

Collapsible

热门标签

热点问答