harry's blog

1. 哈希表

哈希表（Hash Table）是一种基于数组的集合数据结构，它能够通过一个哈希函数将元素映射到数组的索引上，从而使得数据存储和检索变得非常高效。

哈希表的最大优势在于其快速的查找、插入和删除操作，每个操作的平均时间复杂度为 O(1)。在处理大量数据时，哈希表能够直接通过哈希函数计算出数据的位置，因此不需要像其他数据结构（如链表、树等）一样进行顺序查找。

哈希表在 Python 中通常就是指字典（dict），此外 collections 模块中的 defaultdict 也是 python 中哈希表的高效实现

1.1 python 字典

创建一个字典: my_dict = {'apple': 1, 'banana': 2, 'cherry': 3}
查找元素: print(my_dict['apple']) # 输出: 1
插入新的键值对: my_dict['orange'] = 4
删除元素: del my_dict['banana']
检查字典是否包含某个键: print('cherry' in my_dict) # 输出: True

1.2 collections

collections 是 Python 标准库中的一个模块，提供了一些特殊的容器类型，这些容器类型是内置容器类型（如列表、字典、元组）的替代品。它们提供了一些额外的功能，使得在某些特定场景下更加方便和高效。defaultdict 是 collections 模块中的一个类，用于创建带有默认值的字典。它继承自 dict 类，并提供了一个默认值，当访问一个不存在的键时，会自动返回这个默认值。

from collections import defaultdict

d = defaultdict(int) # 创建一个带有默认值的字典
print(d['a'])  # 输出: 0

d = defaultdict(list) # 创建一个带有默认值的列表
d['a'].append(1)
d['a'].append(2)
print(d['a'])  # 输出: [1, 2]

d = defaultdict(set) # 创建一个带有默认值的集合
d['a'].add(1)
d['a'].add(2)
print(d['a'])  # 输出: {1, 2}

d = defaultdict(lambda: 'default') # 创建一个带有默认值的函数
print(d['a'])  # 输出: default

本文由 Yonghui Wang 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Apr 26, 2025 10:33 pm

LeetCode-hot100

1. 哈希表

1.1 python 字典

1.2 collections