Python哈希表与字典实现 — dict底层/hash与eq/集与冻结集Python的dict和set底层使用哈希表实现是Python中最常用的数据结构之一。理解哈希表的工作机制对写出高效、正确的Python代码至关重要。1. Python dict 底层原理# Python 3.6 的 dict 使用紧凑哈希表实现比旧版节省约50%内存# Python 3.7 保证字典保持插入顺序## 内部结构# 1. 哈希数组indices存储稀疏的索引信息# 2. 条目数组entries按插入顺序紧凑存储键值对## 冲突解决开放地址法Open Addressing使用伪随机探测序列# 负载因子Load Factordict约为2/3当哈希表密度达到此值时触发扩容2. 自定义 __hash__ 和 __eq__class Person:自定义类实现hash和eq以便用作字典键或集合元素def __init__(self, name, age):self.name nameself.age agedef __hash__(self):哈希函数使用name和age的组合哈希值return hash((self.name, self.age)) # 元组是hashable的def __eq__(self, other):相等判断两个Person的name和age都相等时才相等if not isinstance(other, Person):return Falsereturn self.name other.name and self.age other.agedef __repr__(self):return fPerson({self.name}, {self.age})# 使用自定义类作为字典键p1 Person(Alice, 25)p2 Person(Bob, 30)p3 Person(Alice, 25) # 与p1相等d {p1: 工程师, p2: 设计师}print(d[p1]) # 工程师print(d[p3]) # 工程师因为p3 p1哈希值相同print(d[Person(Alice, 25)]) # 工程师相同hash和eq3. hashable vs unhashable 类型# hashable可哈希类型可作为字典键或集合元素# - int, float, str, tuple(仅当所有元素hashable), frozenset# - 自定义类默认hashableid-based## unhashable不可哈希类型尝试作为字典键会抛出TypeError# - list, dict, set, bytearray# - 包含不可哈希元素的tuple# 合法示例使用tuple作为键location_map {(40.7128, -74.0060): 纽约,(51.5074, -0.1278): 伦敦}print(坐标对应城市:, location_map[(40.7128, -74.0060)])# 非法示例会报错# bad_dict {[1, 2, 3]: list} # TypeError: unhashable type: list4. set 的内部实现# Python的set也是基于哈希表实现的与dict类似但没有value部分# 特性# - 元素必须hashable# - 无序但Python 3.7的迭代顺序实际与插入顺序相关# - O(1)平均查找、插入、删除# - 不支持索引和切片s set()s.add(3) # 添加元素s.add(1)s.add(2)s.add(3) # 重复元素不会添加print(set:, s) # {1, 2, 3}s.discard(2) # 安全删除元素不存在不会报错s.remove(1) # 删除元素不存在会抛出KeyErrorprint(after remove:, s)# 集合运算并集、交集、差集、对称差a {1, 2, 3, 4}b {3, 4, 5, 6}print(并集:, a | b) # {1, 2, 3, 4, 5, 6}print(交集:, a b) # {3, 4}print(差集:, a - b) # {1, 2}print(对称差:, a ^ b) # {1, 2, 5, 6}print(子集检查:, {1, 2}.issubset(a)) # Trueprint(超集检查:, a.issuperset({1, 2})) # True5. frozenset 不可变集合# frozenset是不可变的set可以用作字典键或set的元素fs frozenset([1, 2, 3])print(frozenset:, fs) # frozenset({1, 2, 3})# frozenset作为字典键inventory {frozenset([苹果, 香蕉]): 水果区,frozenset([牛奶, 酸奶]): 乳制品区}print(库存分类:, inventory)# frozenset作为set的元素set_of_sets {frozenset([1, 2]), frozenset([3, 4])}print(集合的集合:, set_of_sets)6. 负载因子和扩容Resizing# 当dict/set中的元素数量超过哈希表容量的2/3时触发扩容# 扩容时哈希表大小通常翻倍或更大# 扩容后所有元素需要重新哈希rehash这是O(n)操作# 因此提前预分配大小可以避免多次扩容# 预估元素数量时预分配大小仅作示例实际不直接暴露容量接口def build_large_dict(n):预分配容量避免多次扩容# Python 3.6 没有公开的预分配API# 但可以通过创建后批量添加来减少扩容次数d {}for i in range(n):d[i] str(i)return d7. Python 3.7 字典有序性保证# Python 3.7 正式将字典保持插入顺序列为语言规范# 之前的Python版本中dict是无序的或顺序只是实现细节## 如果需要有序字典有几种选择# 1. dict (Python 3.7) — 保持插入顺序# 2. collections.OrderedDict — 额外的功能如move_to_end()# 3. 按key排序dict(sorted(d.items()))# 演示dict保持插入顺序ordered {}ordered[z] 1ordered[a] 2ordered[m] 3ordered[b] 4print(有序字典:, list(ordered.keys())) # [z, a, m, b]# 按key排序sorted_dict dict(sorted(ordered.items()))print(排序后:, list(sorted_dict.keys())) # [a, b, m, z]使用示例if __name__ __main__:# 计数器使用dict统计频率text hello worldfreq {}for ch in text:freq[ch] freq.get(ch, 0) 1print(字符频率:, freq)# 使用set去重nums [1, 2, 2, 3, 3, 3, 4, 5, 5]unique list(set(nums))print(去重后:, unique)
Python哈希表与字典实现
Python哈希表与字典实现 — dict底层/hash与eq/集与冻结集Python的dict和set底层使用哈希表实现是Python中最常用的数据结构之一。理解哈希表的工作机制对写出高效、正确的Python代码至关重要。1. Python dict 底层原理# Python 3.6 的 dict 使用紧凑哈希表实现比旧版节省约50%内存# Python 3.7 保证字典保持插入顺序## 内部结构# 1. 哈希数组indices存储稀疏的索引信息# 2. 条目数组entries按插入顺序紧凑存储键值对## 冲突解决开放地址法Open Addressing使用伪随机探测序列# 负载因子Load Factordict约为2/3当哈希表密度达到此值时触发扩容2. 自定义 __hash__ 和 __eq__class Person:自定义类实现hash和eq以便用作字典键或集合元素def __init__(self, name, age):self.name nameself.age agedef __hash__(self):哈希函数使用name和age的组合哈希值return hash((self.name, self.age)) # 元组是hashable的def __eq__(self, other):相等判断两个Person的name和age都相等时才相等if not isinstance(other, Person):return Falsereturn self.name other.name and self.age other.agedef __repr__(self):return fPerson({self.name}, {self.age})# 使用自定义类作为字典键p1 Person(Alice, 25)p2 Person(Bob, 30)p3 Person(Alice, 25) # 与p1相等d {p1: 工程师, p2: 设计师}print(d[p1]) # 工程师print(d[p3]) # 工程师因为p3 p1哈希值相同print(d[Person(Alice, 25)]) # 工程师相同hash和eq3. hashable vs unhashable 类型# hashable可哈希类型可作为字典键或集合元素# - int, float, str, tuple(仅当所有元素hashable), frozenset# - 自定义类默认hashableid-based## unhashable不可哈希类型尝试作为字典键会抛出TypeError# - list, dict, set, bytearray# - 包含不可哈希元素的tuple# 合法示例使用tuple作为键location_map {(40.7128, -74.0060): 纽约,(51.5074, -0.1278): 伦敦}print(坐标对应城市:, location_map[(40.7128, -74.0060)])# 非法示例会报错# bad_dict {[1, 2, 3]: list} # TypeError: unhashable type: list4. set 的内部实现# Python的set也是基于哈希表实现的与dict类似但没有value部分# 特性# - 元素必须hashable# - 无序但Python 3.7的迭代顺序实际与插入顺序相关# - O(1)平均查找、插入、删除# - 不支持索引和切片s set()s.add(3) # 添加元素s.add(1)s.add(2)s.add(3) # 重复元素不会添加print(set:, s) # {1, 2, 3}s.discard(2) # 安全删除元素不存在不会报错s.remove(1) # 删除元素不存在会抛出KeyErrorprint(after remove:, s)# 集合运算并集、交集、差集、对称差a {1, 2, 3, 4}b {3, 4, 5, 6}print(并集:, a | b) # {1, 2, 3, 4, 5, 6}print(交集:, a b) # {3, 4}print(差集:, a - b) # {1, 2}print(对称差:, a ^ b) # {1, 2, 5, 6}print(子集检查:, {1, 2}.issubset(a)) # Trueprint(超集检查:, a.issuperset({1, 2})) # True5. frozenset 不可变集合# frozenset是不可变的set可以用作字典键或set的元素fs frozenset([1, 2, 3])print(frozenset:, fs) # frozenset({1, 2, 3})# frozenset作为字典键inventory {frozenset([苹果, 香蕉]): 水果区,frozenset([牛奶, 酸奶]): 乳制品区}print(库存分类:, inventory)# frozenset作为set的元素set_of_sets {frozenset([1, 2]), frozenset([3, 4])}print(集合的集合:, set_of_sets)6. 负载因子和扩容Resizing# 当dict/set中的元素数量超过哈希表容量的2/3时触发扩容# 扩容时哈希表大小通常翻倍或更大# 扩容后所有元素需要重新哈希rehash这是O(n)操作# 因此提前预分配大小可以避免多次扩容# 预估元素数量时预分配大小仅作示例实际不直接暴露容量接口def build_large_dict(n):预分配容量避免多次扩容# Python 3.6 没有公开的预分配API# 但可以通过创建后批量添加来减少扩容次数d {}for i in range(n):d[i] str(i)return d7. Python 3.7 字典有序性保证# Python 3.7 正式将字典保持插入顺序列为语言规范# 之前的Python版本中dict是无序的或顺序只是实现细节## 如果需要有序字典有几种选择# 1. dict (Python 3.7) — 保持插入顺序# 2. collections.OrderedDict — 额外的功能如move_to_end()# 3. 按key排序dict(sorted(d.items()))# 演示dict保持插入顺序ordered {}ordered[z] 1ordered[a] 2ordered[m] 3ordered[b] 4print(有序字典:, list(ordered.keys())) # [z, a, m, b]# 按key排序sorted_dict dict(sorted(ordered.items()))print(排序后:, list(sorted_dict.keys())) # [a, b, m, z]使用示例if __name__ __main__:# 计数器使用dict统计频率text hello worldfreq {}for ch in text:freq[ch] freq.get(ch, 0) 1print(字符频率:, freq)# 使用set去重nums [1, 2, 2, 3, 3, 3, 4, 5, 5]unique list(set(nums))print(去重后:, unique)
