本文目录
- 18 哈希表(Hash Table)
- S1 说明
- 特征
- 解决问题
- S2 示例
- 示例 1
- 示例 2
- S3 应用
- 应用1: LRU 缓存机制
- 应用2:高级拼写检查器
- 应用3:DNA 序列的 K-mer 计数
往期链接
01 数组 | 02 链表 | 03 栈 | 04 队列 | 05 二叉树 | 06 二叉搜索树 | 07 AVL树 | 08 红黑树 | 09 B树 | 10 B+树 |
---|
11 线段树 | 12 树状数组 | 13 图形数据结构 | 14 邻接矩阵 | 15 完全图 | 16 有向图 | 17 散列 |
---|
18 哈希表(Hash Table)
S1 说明
哈希表(Hash Table)是一种用于存储键值对的数据结构,通过哈希函数将键映射到数组的索引位置,从而实现快速的查找、插入和删除操作。哈希表的基本思想是将数据存储在一个数组中,并使用哈希函数计算每个元素的存储位置。
特征
- 快速查找:
哈希表的查找、插入和删除操作的平均时间复杂度为 O ( 1 ) O(1) O(1),在最坏情况下为 O ( n ) O(n) O(n),但通过良好的哈希函数和冲突解决策略,可以保持接近 O ( 1 ) O(1) O(1)的性能。 - 键唯一性:
在哈希表中,每个键都是唯一的。若插入相同的键,则会更新其对应的值。 - 哈希函数:
哈希函数将键转换为数组索引。一个好的哈希函数应该能够均匀分布键,减少冲突的发生。 - 冲突解决:
当不同的键映射到相同的索引时,会发生冲突。常用的冲突解决方法有链式地址法(使用链表存储同一索引的多个元素)和开放地址法(寻找下一个空位)。 - 动态扩展:
当哈希表装载因子(存储的元素数量与数组大小的比率)超过某个阈值时,通常会进行扩展,以保持高性能。
解决问题
哈希表可以解决许多实际问题,包括但不限于:
- 缓存:使用哈希表存储计算结果或频繁访问的数据,实现快速访问。
- 数据去重:通过哈希表存储已访问的数据,快速判断新数据是否为重复。
- 频率统计:在字典或集合中存储数据频率,便于快速查找和更新。
- 索引建立:在数据库中使用哈希表建立索引,提高数据检索速度。
- 密码存储:在用户认证中,使用哈希表存储用户信息,提高查找效率。
S2 示例
示例 1
class Person:def __init__(self, name, age):self.name = nameself.age = agedef __hash__(self):"""自定义哈希函数,将名字和年龄结合起来生成哈希值"""return hash((self.name, self.age))def __eq__(self, other):"""比较两个对象是否相等"""if isinstance(other, Person):return self.name == other.name and self.age == other.agereturn False# 创建一些对象
person1 = Person("敖耳散", 30)
person2 = Person("包而嗣", 25)
person3 = Person("敖耳散", 30)# 使用哈希值
print(f"Hash of person1: {hash(person1)}")
print(f"Hash of person2: {hash(person2)}")
print(f"Hash of person3: {hash(person3)}")# 比较对象
print(f"person1 == person3: {person1 == person3}") # 输出: True
print(f"person1 == person2: {person1 == person2}") # 输出: False# 使用对象作为字典的键
person_dict = {person1