python字典算法

Python字典是一种高效的哈希表实现，常用于快速查找和键值对存储。以下是与字典相关的核心算法和应用

1. 字典基础操作

创建字典：

python

d1 = {} 空字典

d2 = dict(a=1, b=2) 使用构造函数

d3 = {'name': 'Alice', 'age': 25} 直接初始化

访问/修改元素：

python

value = d3['name'] 访问，KeyError若键不存在

d3['age'] = 26 修改

d3['city'] = 'Paris' 新增键值对

val = d3.get('phone', 'N/A') 安全访问，返回默认值

删除元素：

python

del d3['city'] 删除键

age = d3.pop('age') 删除并返回值

2. 常见算法应用

统计元素频率

python

from collections import defaultdict

nums = [1, 2, 3, 2, 1, 3, 3]

counts = defaultdict(int)

for num in nums:

counts[num] += 1

或使用普通字典

counts = {}

for num in nums:

counts[num] = counts.get(num, 0) + 1

两数之和（快速查找）

python

def two_sum(nums, target):

seen = {}

for i, num in enumerate(nums):

complement = target

num

if complement in seen:

return [seen[complement], i]

seen[num] = i

return []

反转字典（值→键）

处理重复值：

python

from collections import defaultdict

original = {'a': 1, 'b': 2, 'c': 1}

reversed_dict = defaultdict(list)

for k, v in original.items:

reversed_dict[v].append(k)

输出：{1: ['a', 'c'], 2: ['b']}

3. 字典高级操作

合并字典：

python

d1 = {'a': 1}

d2 = {'b': 2}

merged = {d1, d2} Python 3.5+

merged = d1 | d2 Python 3.9+

过滤字典：

python

filtered = {k: v for k, v in d.items if v > 10}

按键/值排序：

python

sorted_by_key = dict(sorted(d.items)) 按键排序

sorted_by_value = dict(sorted(d.items, key=lambda x: x[1]))

4. 底层原理与注意事项

哈希冲突：Python使用开放寻址法处理冲突，平均时间复杂度为O(1)。

插入顺序保留：Python 3.7+ 的字典会记录插入顺序，遍历时按插入顺序输出。

视图对象动态更新：`d.keys`、`d.values`、`d.items` 返回视图对象，随字典变化实时更新。

深浅拷贝：

python

shallow_copy = d.copy 浅拷贝

import copy

deep_copy = copy.deepcopy(d) 深拷贝（处理嵌套对象）

5. 性能优化场景

快速查找：利用O(1)查找特性优化算法（如缓存、去重）。

LRU缓存实现：结合双向链表与字典，或直接使用`collections.OrderedDict`。

图结构邻接表：用字典存储节点及其邻居。

6. 典型错误规避

遍历时修改字典：避免直接遍历视图，可转为列表处理：

python

for key in list(d.keys):

if condition(key):

del d[key]

自定义对象作为键：需正确实现`__hash__`和`__eq__`方法。

掌握字典的底层原理和高效操作，能够显著提升算法设计能力，尤其在处理查找、统计、缓存等问题时表现优异。