企业官网建设流程全解析

============================================================
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 Factor）：dict约为2/3，当哈希表密度达到此值时触发扩容

============================================================
2. 自定义 __hash__ 和 __eq__
============================================================

class Person:
"""自定义类，实现hash和eq以便用作字典键或集合元素"""
def __init__(self, name, age):
self.name = name
self.age = age

def __hash__(self):
"""哈希函数：使用name和age的组合哈希值"""
return hash((self.name, self.age)) # 元组是hashable的

def __eq__(self, other):
"""相等判断：两个Person的name和age都相等时才相等"""
if not isinstance(other, Person):
return False
return self.name == other.name and self.age == other.age

def __repr__(self):
return f"Person({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和eq）

============================================================
3. hashable vs unhashable 类型
============================================================
# hashable（可哈希）类型：可作为字典键或集合元素
# - int, float, str, tuple(仅当所有元素hashable), frozenset
# - 自定义类默认hashable（id-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: 'list'

============================================================
4. 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) # 删除元素（不存在会抛出KeyError）
print("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)) # True
print("超集检查:", a.issuperset({1, 2})) # True

============================================================
5. 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 d

============================================================
7. 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"] = 1
ordered["a"] = 2
ordered["m"] = 3
ordered["b"] = 4
print("有序字典:", 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 world"
freq = {}
for ch in text:
freq[ch] = freq.get(ch, 0) + 1
print("字符频率:", freq)

# 使用set去重
nums = [1, 2, 2, 3, 3, 3, 4, 5, 5]
unique = list(set(nums))
print("去重后:", unique)