Python 哈希表和集合

李昊哲-小课

246人浏览 · 2026-03-13 08:22:48

李昊哲-小课 · 2026-03-13 08:22:48 发布

Python 哈希表和集合详解

文件信息

文件名: 03_哈希表和集合.py
开发思路和开发过程:
1. 首先介绍哈希表的基本原理
2. 然后演示Python中字典的使用
3. 接着展示集合的操作
4. 最后介绍哈希表的实际应用案例
代码功能: 演示哈希表和集合数据结构的实现和使用，包括基本操作和实际应用场景。

代码实现

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
文件名: 03_哈希表和集合.py
开发思路和开发过程:
1. 首先介绍哈希表的基本原理
2. 然后演示Python中字典的使用
3. 接着展示集合的操作
4. 最后介绍哈希表的实际应用案例

代码功能: 演示哈希表和集合数据结构的实现和使用，包括基本操作和实际应用场景。
"""

print("=== 哈希表和集合详解 ===\n")

# 1. 哈希表基本原理
print("1. 哈希表基本原理:")
print("哈希表是一种通过哈希函数将键映射到值的数据结构")
print("主要优点：查找、插入、删除的时间复杂度平均为O(1)")
print("常见应用：字典、缓存、数据库索引等")
print()

# 2. Python中字典的使用（字典就是哈希表的实现）
print("2. Python中字典的使用:")

# 创建字典
student_grades = {
  "张三": 85,
  "李四": 92,
  "王五": 78,
  "赵六": 96
}
print(f"学生成绩字典: {student_grades}")

# 访问元素
print(f"张三的成绩: {student_grades['张三']}")

# 添加/更新元素
student_grades["钱七"] = 88
student_grades["张三"] = 90  # 更新张三的成绩
print(f"更新后的字典: {student_grades}")

# 删除元素
removed_grade = student_grades.pop("王五")
print(f"删除王五的成绩 {removed_grade}")
print(f"删除后的字典: {student_grades}")

# 检查键是否存在
if "李四" in student_grades:
  print(f"李四的成绩: {student_grades['李四']}")

# 获取所有键、值和键值对
print(f"所有学生: {list(student_grades.keys())}")
print(f"所有成绩: {list(student_grades.values())}")
print(f"所有键值对: {list(student_grades.items())}")

# 字典推导式
squared_dict = {x: x ** 2 for x in range(1, 6)}
print(f"字典推导式示例: {squared_dict}")

print()

# 3. 集合的操作
print("3. 集合的操作:")

# 创建集合
set1 = {1, 2, 3, 4, 5}
set2 = {4, 5, 6, 7, 8}
print(f"集合1: {set1}")
print(f"集合2: {set2}")

# 集合的基本操作
print(f"并集: {set1 | set2}")  # 或者 set1.union(set2)
print(f"交集: {set1 & set2}")  # 或者 set1.intersection(set2)
print(f"差集 (set1 - set2): {set1 - set2}")  # 或者 set1.difference(set2)
print(f"对称差集: {set1 ^ set2}")  # 或者 set1.symmetric_difference(set2)

# 添加和删除元素
set1.add(6)
print(f"添加6后集合1: {set1}")

set1.discard(1)  # discard不会引发异常如果元素不存在
print(f"删除1后集合1: {set1}")

# 子集和超集
set3 = {2, 3}
print(f"集合3: {set3}")
print(f"set3是set1的子集: {set3.issubset(set1)}")
print(f"set1是set3的超集: {set1.issuperset(set3)}")

# 集合推导式
even_squares = {x ** 2 for x in range(10) if x % 2 == 0}
print(f"偶数的平方集合: {even_squares}")

print()

# 4. collections模块中的高级哈希表结构
print("4. collections模块中的高级哈希表结构:")

from collections import defaultdict, Counter, OrderedDict

# defaultdict - 带默认值的字典
print("4.1 defaultdict - 带默认值的字典:")

# 普通字典在访问不存在的键时会报错
normal_dict = {}
# normal_dict['missing_key'].append(1)  # 这会引发KeyError

# defaultdict在访问不存在的键时会自动创建默认值
dd_list = defaultdict(list)
dd_list['fruits'].append('apple')
dd_list['fruits'].append('banana')
dd_list['vegetables'].append('carrot')
print(f"defaultdict(list)示例: {dict(dd_list)}")

dd_int = defaultdict(int)
dd_int['count1'] += 1
dd_int['count1'] += 2
dd_int['count2'] += 1
print(f"defaultdict(int)示例: {dict(dd_int)}")

# Counter - 计数器
print("\n4.2 Counter - 计数器:")
text = "hello world"
char_counter = Counter(text)
print(f"字符计数: {dict(char_counter)}")

words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
word_counter = Counter(words)
print(f"单词计数: {dict(word_counter)}")

# 获取最常见的元素
print(f"最常见的3个字符: {char_counter.most_common(3)}")

# OrderedDict - 有序字典（Python 3.7+字典已经是有序的，但OrderedDict仍有用途）
print("\n4.3 OrderedDict - 有序字典:")
ordered_dict = OrderedDict()
ordered_dict['first'] = 1
ordered_dict['second'] = 2
ordered_dict['third'] = 3
print(f"有序字典: {ordered_dict}")

# 移动元素到末尾
ordered_dict.move_to_end('first')
print(f"将'first'移动到末尾: {ordered_dict}")

print()

# 5. 哈希表的实际应用案例
print("5. 哈希表的实际应用案例:")

# 5.1 缓存实现（LRU Cache简化版）
print("5.1 简化的缓存实现:")


class SimpleCache:
  """简化的缓存实现"""

  def __init__(self, capacity=3):
    self.cache = {}
    self.capacity = capacity

  def get(self, key):
    """获取缓存值"""
    if key in self.cache:
      # 将访问的项移到末尾（简化实现）
      value = self.cache.pop(key)
      self.cache[key] = value
      return value
    return None

  def put(self, key, value):
    """放入缓存值"""
    if key in self.cache:
      # 更新现有键
      self.cache.pop(key)
    elif len(self.cache) >= self.capacity:
      # 删除最旧的项
      oldest_key = next(iter(self.cache))
      self.cache.pop(oldest_key)

    self.cache[key] = value

  def display(self):
    """显示缓存内容"""
    return dict(self.cache)


cache = SimpleCache(3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
print(f"初始缓存: {cache.display()}")

cache.get("a")  # 访问"a"
cache.put("d", 4)  # 添加"d"，应移除"b"
print(f"添加'd'后缓存: {cache.display()}")

# 5.2 电话簿应用
print("\n5.2 电话簿应用:")


class PhoneBook:
  """电话簿类"""

  def __init__(self):
    self.contacts = {}

  def add_contact(self, name, phone):
    """添加联系人"""
    self.contacts[name] = phone
    print(f"添加联系人: {name} - {phone}")

  def search_contact(self, name):
    """搜索联系人"""
    phone = self.contacts.get(name)
    if phone:
      return f"{name} 的电话号码是: {phone}"
    else:
      return f"未找到联系人: {name}"

  def delete_contact(self, name):
    """删除联系人"""
    if name in self.contacts:
      phone = self.contacts.pop(name)
      return f"已删除联系人: {name} - {phone}"
    else:
      return f"未找到联系人: {name}"

  def display_all(self):
    """显示所有联系人"""
    if not self.contacts:
      return "电话簿为空"
    result = "电话簿内容:\n"
    for name, phone in self.contacts.items():
      result += f"  {name}: {phone}\n"
    return result.strip()


# 使用电话簿
phonebook = PhoneBook()
phonebook.add_contact("张三", "13800138000")
phonebook.add_contact("李四", "13900139000")
phonebook.add_contact("王五", "13700137000")

print(phonebook.search_contact("李四"))
print(phonebook.search_contact("赵六"))

phonebook.delete_contact("王五")
print(phonebook.display_all())

print()

# 5.3 去重和频率统计
print("5.3 去重和频率统计:")

# 去除列表中的重复元素
original_list = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
unique_list = list(set(original_list))
print(f"原列表: {original_list}")
print(f"去重后: {unique_list}")

# 统计元素出现频率
data = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple', 'date']
frequency = Counter(data)
print(f"数据: {data}")
print(f"频率统计: {dict(frequency)}")
print(f"最常见的元素: {frequency.most_common(1)[0]}")

print("\n=== 哈希表和集合详解结束 ===")

哈希表工作原理

键值对 ──┐
         ├── 哈希函数 ── 哈希值 ── 数组索引 ── 存储桶 ── 存储值
键值对 ──┘

集合操作关系图

    集合A     集合B
      │         │
      ▼         ▼
   ┌─────────────────┐
   │   并集 A ∪ B    │
   └─────────────────┘
   
   ┌─────────────────┐
   │   交集 A ∩ B    │ ◄───┐
   └─────────────────┘     │
      │         │          │
      │         └──────────┘
      ▼
   ┌─────────────────┐
   │   差集 A - B    │
   └─────────────────┘

   ┌─────────────────┐
   │   差集 B - A    │ ◄── 集合B
   └─────────────────┘

   ┌─────────────────┐
   │ 对称差集 A ⊕ B  │ ◄───┐
   └─────────────────┘     │
      │         │          │
      └─────────┴──────────┘
        集合A     集合B

collections模块结构

collections模块
├── defaultdict
│   ├── 自动创建默认值
│   └── 避免KeyError
├── Counter
│   ├── 计数器
│   ├── 频率统计
│   └── most_common方法
└── OrderedDict
    ├── 有序字典
    └── move_to_end方法