Python 通过其字典 (dict) 和集合 (set) 类型,提供了高效的内置哈希表实现。了解它们的工作方式以及如何使用它们,对许多需要快速查找、插入和成员资格测试的机器学习任务来说,具有实用价值。Python 的字典 (dict)其本质上,Python 字典是一种哈希映射。它存储键值对,允许您非常迅速地检索与特定键关联的值,通常平均时间复杂度为 $O(1)$。字典中的键必须是可哈希的,意思是它们必须具有在生命周期内不变的哈希值(与 __hash__ 方法关联),并且可以与其他对象进行比较(与 __eq__ 方法关联)。大多数内置的不可变类型,如字符串、数字(整型、浮点型)以及只包含可哈希类型的元组都是可哈希的。可变类型,如列表和字典,不能用作键,因为它们的内容(因此其哈希值)可能会改变。这是一个基本示例:# 创建一个字典 feature_counts = {'word_a': 150, 'word_b': 85, 'word_c': 210} # 按键访问值(平均时间 O(1)) print(f"`word_b` 的计数: {feature_counts['word_b']}") # 添加新的键值对(平均时间 O(1)) feature_counts['word_d'] = 55 # 检查键是否存在(平均时间 O(1)) print(f"'`word_a'` 存在吗? {'word_a' in feature_counts}") print(f"'`word_x'` 存在吗? {'word_x' in feature_counts}") # 更新值(平均时间 O(1)) feature_counts['word_a'] += 10 print(f"`word_a` 的更新计数: {feature_counts['word_a']}") # 获取项目数量 print(f"特征数量: {len(feature_counts)}")机器学习中的字典:特征映射: 字典非常适合创建从分类特征(如字符串)到数值表示(如整数索引)的映射,许多机器学习算法都需要这种映射。categories = ['red', 'green', 'blue', 'green', 'red'] cat_to_index = {category: i for i, category in enumerate(set(categories))} print(f"分类到索引映射: {cat_to_index}") # 输出: 分类到索引映射: {'green': 0, 'blue': 1, 'red': 2} indexed_features = [cat_to_index[cat] for cat in categories] print(f"索引特征: {indexed_features}") # 输出: 索引特征: [2, 0, 1, 0, 2]计数频率: 使用字典可以高效地计算文本数据中的词频(TF)或统计项目出现次数。Python 的 collections.Counter 是用于此目的的专用字典子类。from collections import Counter document = "the quick brown fox jumps over the lazy dog the quick brown fox" words = document.split() word_counts = Counter(words) print(f"词频: {word_counts}") print(f"'the' 的频率: {word_counts['the']}") # 输出: 词频: Counter({'the': 3, 'quick': 2, 'brown': 2, 'fox': 2, 'jumps': 1, 'over': 1, 'lazy': 1, 'dog': 1}) # 输出: 'the' 的频率: 3缓存/记忆化: 存储计算成本高的函数调用的结果,尤其是在输入可能重复的情况下。Python 的集合 (set)集合是无序的、包含唯一可哈希元素的集合。与字典一样,它们内部使用哈希表,为添加元素以及(非常重要地)检查成员资格(测试元素是否存在于集合中)提供了平均 $O(1)$ 的时间复杂度。# 创建一个集合 unique_tags = {'ml', 'python', 'data_science', 'algorithms'} # 添加一个元素(平均时间 O(1)) unique_tags.add('hashing') # 检查成员资格(平均时间 O(1)) print(f"'python' 在集合中吗? {'python' in unique_tags}") print(f"'java' 在集合中吗? {'java' in unique_tags}") # 移除一个元素(平均时间 O(1)) unique_tags.remove('algorithms') # 如果未找到则引发 KeyError # unique_tags.discard('algorithms') # 如果未找到则不引发错误 print(f"当前标签: {unique_tags}")机器学习中的集合:查找唯一项: 可以轻松地从列表或其他可迭代对象中提取唯一元素。feature_list = ['temperature', 'humidity', 'pressure', 'temperature', 'wind_speed'] unique_features = set(feature_list) print(f"唯一特征: {unique_features}") # 输出: 唯一特征: {'pressure', 'humidity', 'wind_speed', 'temperature'}快速成员资格测试: 快速检查项目是否属于某个组,这对于过滤或验证非常有用。例如,检查用户 ID 是否属于已知的测试用户组。集合操作: 高效执行数学集合操作,如并集 (|)、交集 (&)、差集 (-) 和对称差集 (^)。这对于比较特征集、查找组间的共同元素等很有用。set_A = {'apple', 'banana', 'cherry'} set_B = {'banana', 'cherry', 'date'} print(f"交集: {set_A & set_B}") # 共同元素 print(f"并集: {set_A | set_B}") # 所有唯一元素 print(f"差集 (A - B): {set_A - set_B}") # 存在于 A 但不存在于 B 的元素 # 输出: 交集: {'cherry', 'banana'} # 输出: 并集: {'date', 'cherry', 'apple', 'banana'} # 输出: 差集 (A - B): {'apple'}示例:简化的哈希表映射虽然 Python 处理底层细节,但将映射可视化有助于理解。哈希函数将键转换为整数(哈希值),而取模运算符 (%) 将此哈希值映射到表中数组的一个索引。digraph HashTable { rankdir=LR; node [shape=record, style=filled, fillcolor="#e9ecef"]; edge [arrowhead=vee]; inputs [label="键:\n'apple'\n'banana'\n'grape'\n'orange'", shape=none, fontcolor="#495057"]; hash_func [label="哈希函数()\n%", shape=cylinder, fillcolor="#a5d8ff", style=filled]; ht [label="<f0> 0 | <f1> 1 | <f2> 2 | <f3> 3 | <f4> 4 | <f5> 5 ", labeljust=l, shape=record, fillcolor="#ffec99"]; inputs -> hash_func [style=invis]; // Helper for positioning subgraph cluster_input { label = "输入处理"; style=filled; fillcolor="#f8f9fa"; node [shape=plaintext]; "key_apple" [label="'apple'"]; "key_banana" [label="'banana'"]; "key_grape" [label="'grape'"]; "key_orange" [label="'orange'"]; } subgraph cluster_mapping { label="哈希表(大小为 6)"; style=filled; fillcolor="#f8f9fa"; ht; } "key_apple" -> hash_func [label=" hash('apple') % 6 = 3 ", fontsize=10, fontcolor="#1c7ed6"]; "key_banana" -> hash_func [label=" hash('banana') % 6 = 5 ", fontsize=10, fontcolor="#1c7ed6"]; "key_grape" -> hash_func [label=" hash('grape') % 6 = 1 ", fontsize=10, fontcolor="#1c7ed6"]; "key_orange" -> hash_func [label=" hash('orange') % 6 = 3 ", fontsize=10, fontcolor="#f76707"]; // 碰撞示例 hash_func -> ht:f3 [label=" 3 ", headport="w", tailport="e", fontsize=10, fontcolor="#495057"]; hash_func -> ht:f5 [label=" 5 ", headport="w", tailport="e", fontsize=10, fontcolor="#495057"]; hash_func -> ht:f1 [label=" 1 ", headport="w", tailport="e", fontsize=10, fontcolor="#495057"]; // 指示冲突解决(例如,链式或探测法会指向此处) node [shape=plaintext, fillcolor=none]; ht:f3 -> "slot3_data" [label=" 存储 'apple'\n(并处理 'orange' 冲突)", fontsize=9, fontcolor="#495057"]; ht:f5 -> "slot5_data" [label=" 存储 'banana'", fontsize=9, fontcolor="#495057"]; ht:f1 -> "slot1_data" [label=" 存储 'grape'", fontsize=9, fontcolor="#495057"]; }键由哈希函数和取模运算处理,以确定它们在哈希表中的槽位索引。冲突(例如 'apple' 和 'orange' 都映射到索引 3)由 Python 内部处理。与特征哈希的关系字典明确存储从特征(键)到其索引或值的映射,而特征哈希(在“用于降维的特征哈希”一节中有详细介绍)直接使用哈希函数来确定输出特征向量中的索引,而不存储原始特征键。设想将单词映射到长度为 D 的固定大小向量中的索引。字典方法: index = feature_map['word'](需要构建和存储 feature_map)。特征哈希方法: index = hash('word') % D(不需要存储映射,多个特征可能映射到同一索引导致的冲突会被隐式处理)。Python 的内置 hash() 函数可以用来实现一个简单版本,尽管库的实现(如 Scikit-learn 的 HashingVectorizer)经过优化,并处理符号哈希和其他细节。# 简化的特征哈希思想 feature_vector_size = 10 word1 = "machine" word2 = "learning" word3 = "algorithms" # 可能发生冲突 index1 = hash(word1) % feature_vector_size index2 = hash(word2) % feature_vector_size index3 = hash(word3) % feature_vector_size # 潜在冲突 print(f"'`machine'` 映射到索引: {abs(index1)}") # 使用 abs 获取非负索引 print(f"'`learning'` 映射到索引: {abs(index2)}") print(f"'`algorithms'` 映射到索引: {abs(index3)}") # 注意: hash() 的值可能为负,因此使用 abs()。 # 实际实现可能使用不同的哈希函数。性能说明虽然 dict 和 set 操作的平均时间复杂度为 $O(1)$,但需要记住:最坏情况: 在(罕见的)最坏情况下,当许多键哈希到同一索引(高冲突)时,性能可能会下降到接近 $O(n)$,其中 $n$ 是元素数量。Python 的实现使用复杂的探测技术,在实践中能有效缓解此问题。大小调整: 随着字典和集合的增长,底层表可能需要调整大小以保持较低的负载因子(元素与表大小的比率)并维持高性能。调整大小涉及创建一个更大的表并重新哈希/重新插入所有现有元素,这需要 $O(n)$ 的时间。这种情况不常发生,因此插入的均摊成本仍为 $O(1)$。内存: 哈希表比简单的列表需要更多的内存来存储相同的元素,因为它们需要表数组本身的存储空间,而该数组通常只被部分填充。Python 的 dict 和 set 是功能强大的工具,由高效的哈希表实现支持。恰当地运用它们可以实现快速的数据操作和查找,这在机器学习流程中通常是很重要的步骤,涵盖从数据预处理、特征工程到某些算法的实现。它们也为理解高级哈希技术(如特征哈希和局部敏感哈希)提供了实践上的支持。