哈希表总结

介绍

哈希表是一种常见且高效的数据结构，通常用于快速判断元素是否出现过、统计元素频率等操作。本文目前记录了使用python中数据结构的一些解题方法和区别，包括以下内容：

  1. Python 中常用的哈希表实现方式。
  2. 各种哈希表结构在不同问题中的应用与选择。

哈希表

python中实现哈希表的方法一般有如下几种：

  • dict()
  • set()
  • collections.defaultdict

dict()

dict() 是 Python 中最常用的哈希表实现，基于哈希函数将键映射到一个数组中，以常数时间复杂度 O(1)完成查找、插入和删除操作。典型的使用场景包括统计字符频率、记录元素的索引位置等。但是其在使用的过程中，访问一个不存在的键会抛出 KeyError 异常，因此在访问之前通常需要检查键是否存在。

1
2
3
4
5
my_dict = {}
if 'key' in my_dict:
    value = my_dict['key']
else:
    value = 'default_value'

set()

set()是一个无序集合，元素唯一且不重复。它也基于哈希表实现，主要用于判断元素是否存在、去重操作等。与 dict() 不同的是，set() 仅存储键，没有对应的值,其查找、插入和删除操作的时间复杂度通常为O(1)。

添加删除元素

  • 添加元素：使用 add() 方法向集合中添加一个元素。如果元素已存在，集合不会发生变化。
    1
    2
    3
    my_set = {1, 2, 3, 4, 4}  # 结果：{1, 2, 3, 4}
    my_set.add(5)  # my_set = {1, 2, 3, 4, 5}
    my_set.add(4)  # my_set = {1, 2, 3, 4, 5}
  • 删除元素：使用 remove() 或 discard() 方法从集合中删除一个元素。如果元素不存在，remove() 会抛出 KeyError，而 discard() 则不会报错。

集合运算和去重

可以实现并集、交集、差集、对称差集的运算，以及可以对列表进行去重。

1
2
3
4
5
6
7
8
9
set1 = {1, 2, 3}
set2 = {3, 4, 5}
union_set = set1 | set2  # 结果：{1, 2, 3, 4, 5} 返回两个集合的并集
intersection_set = set1 & set2  # 结果：{3}  返回两个集合的交集
difference_set = set1 - set2  # 结果：{1, 2}  返回在第一个集合中但不在第二个集合中的元素
sym_diff_set = set1 ^ set2  # 结果：{1, 2, 4, 5} 返回两个集合中不同时存在于双方的元素

#去重
unique_items = list(set(items))

collections.defaultdict

defaultdict 是 dict() 的一个子类，它的特点是在访问不存在的键时，会自动初始化这个键的值，避免了手动检查键是否存在的过程。这在计数、分组等场景中非常有用。并且可以在创建 defaultdict 时指定默认值的生成方式（例如 int, list, set 等）。因此defaultdict 可以认为是 dict() 的增强版，在处理频繁访问或需要初始化的键时非常有用，可以减少代码复杂度，提升可读性。

1
2
3
from collections import defaultdict
my_defaultdict = defaultdict(int)
value = my_defaultdict['key']  # 自动初始化为 0

封面

封面