[Hello算法02]数据结构，哈希表，哈希冲突

本文为书籍 《Hello算法》学习笔记原书链接Hello 算法本文仅作学习记录及分享一、数据结构常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图它们可以从“逻辑结构”和“物理结构”两个维度进行分类。数据结构可以从逻辑结构和物理结构两个角度进行分类。逻辑结构描述了数据元素之间的逻辑关系而物理结构描述了数据在计算机内存中的存储方式。常见的逻辑结构包括线性、树状和网状等。通常我们根据逻辑结构将数据结构分为线性数组、链表、栈、队列和非线性树、图、堆两种。哈希表的实现可能同时包含线性数据结构和非线性数据结构。链表在初始化后仍可以在程序运行过程中对其长度进行调整因此也称“动态数据结构”。数组在初始化后长度不可变因此也称“静态数据结构”。值得注意的是数组可通过重新分配内存实现长度变化从而具备一定的“动态性”。物理结构主要分为连续空间存储数组和分散空间存储链表。所有数据结构都是由数组、链表或两者的组合实现的。哈希表同时包含线性数据结构和非线性数据结构是因为哈希表底层是数组而为了解决哈希冲突我们可能会使用“链式地址”后续“哈希冲突”章节会讲数组中每个桶指向一个链表当链表长度超过一定阈值时又可能被转化为树通常为红黑树。从存储的角度来看哈希表的底层是数组其中每一个桶槽位可能包含一个值也可能包含一个链表或一棵树。因此哈希表可能同时包含线性数据结构数组、链表和非线性数据结构树。二、哈希表# 初始化哈希表 hmap: dict {} # 添加操作 # 在哈希表中添加键值对 (key, value) hmap[12836] 小哈 hmap[15937] 小啰 hmap[16750] 小算 hmap[13276] 小法 hmap[10583] 小鸭 # 查询操作 # 向哈希表中输入键 key 得到值 value name: str hmap[15937] # 删除操作 # 在哈希表中删除键值对 (key, value) hmap.pop(10583)遍历方式# 遍历哈希表 # 遍历键值对 key-value for key, value in hmap.items(): print(key, -, value) # 单独遍历键 key for key in hmap.keys(): print(key) # 单独遍历值 value for value in hmap.values(): print(value)在哈希表中我们将数组中的每个空位称为桶bucket每个桶可存储一个键值对。因此查询操作就是找到key对应的桶并在桶中获取value。在哈希表中输入空间是所有key输出空间是所有桶数组索引。换句话说输入一个key 我们可以通过哈希函数得到该key对应的键值对在数组中的存储位置。输入一个key哈希函数的计算过程分为以下两步。通过某种哈希算法hash()计算得到哈希值。将哈希值对桶数量数组长度capacity取模从而获取该key对应的桶数组索引index。哈希函数工作原理class Pair: 键值对 def __init__(self, key: int, val: str): self.key key self.val val class ArrayHashMap: 基于数组实现的哈希表 def __init__(self): 构造方法 # 初始化数组包含 100 个桶 self.buckets: list[Pair | None] [None] * 100 def hash_func(self, key: int) - int: 哈希函数 index key % 100 return index def get(self, key: int) - str | None: 查询操作 index: int self.hash_func(key) pair: Pair self.buckets[index] if pair is None: return None return pair.val def put(self, key: int, val: str): 添加和更新操作 pair Pair(key, val) index: int self.hash_func(key) self.buckets[index] pair def remove(self, key: int): 删除操作 index: int self.hash_func(key) # 置为 None 代表删除 self.buckets[index] None def entry_set(self) - list[Pair]: 获取所有键值对 result: list[Pair] [] for pair in self.buckets: if pair is not None: result.append(pair) return result def key_set(self) - list[int]: 获取所有键 result [] for pair in self.buckets: if pair is not None: result.append(pair.key) return result def value_set(self) - list[str]: 获取所有值 result [] for pair in self.buckets: if pair is not None: result.append(pair.val) return result def print(self): 打印哈希表 for pair in self.buckets: if pair is not None: print(pair.key, -, pair.val)三、哈希冲突从本质上看哈希函数的作用是将所有key构成的输入空间映射到数组所有索引构成的输出空间而输入空间往往远大于输出空间。因此理论上一定存在“多个输入对应相同输出”的情况。我们将这种多个输入对应同一输出的情况称为哈希冲突hash collision。哈希表容量越大多个key被分配到同一个桶中的概率就越低冲突就越少。因此我们可以通过扩容哈希表来减少哈希冲突。负载因子load factor是哈希表的一个重要概念其定义为哈希表的元素数量除以桶数量用于衡量哈希冲突的严重程度也常作为哈希表扩容的触发条件。