Python - 哈希表

Python 是一种高级、解释型编程语言，以其简洁和清晰而闻名，这使其成为初学者和有经验的开发者的首选。它支持多种编程范式，包括过程式、面向对象和函数式编程。Python 的设计强调代码的清晰性和易用性，允许开发人员编写清晰、逻辑化的代码来处理大小规模的任务。

Python 拥有动态类型系统和自动内存管理功能，并配有一个广泛的标准库，支持许多常见的编程任务，包括 Web 开发、数据分析、人工智能、科学计算等。通过 Python 包索引 (PyPI) 可以获得的大量第三方应用程序进一步扩展了其功能。Python 的多功能性和易用性使其成为全球最受欢迎的编程语言之一。

哈希表

哈希表，也称为散列映射，是一种通过键值对高效存储和检索数据的数据结构。在 Python 中，哈希表是通过字典实现的，字典允许在插入、删除和查找操作中实现平均 O(1) 的恒定时间复杂度。

关键概念

• 哈希函数
  • 将键转换为整数（哈希值）。
  • 然后将此整数映射到数组（哈希表）中的索引。
  • Python 内置的 `hash()` 函数可用于生成哈希值。
• 桶
  • 哈希表中的数组包含存储桶，每个存储桶可以存储多个键值对。
  • 每个存储桶都可以处理冲突（不同的键产生相同的哈希值的情况）。
• 冲突处理
  • 分离链接法：每个存储桶包含一个键值对列表（或其他数据结构）。
  • 开放寻址法：使用线性探测或二次探测等技术查找下一个可用存储桶。

特点

• 插入、删除和查找：由于高效的哈希和冲突解决机制，Python 字典在这些操作中提供 O(1) 的平均时间复杂度。
• 动态调整大小：Python 字典会随着键值对数量的增加自动调整自身大小以保持高效运行。这种调整有助于通过将负载因子（元素数量与哈希表大小的比率）保持在合理范围内来维持恒定的时间复杂度。
• 任意键类型：Python 字典中的键可以是任何不可变类型（例如，字符串、数字、元组）。不可变性保证了键的哈希值保持不变。
• 有序字典（Python 3.7+）：从 Python 3.7 开始，字典会保留键的插入顺序。这意味着在遍历字典时，项目将按照插入的顺序返回。
• 哈希和冲突解决
  • 高效哈希：Python 使用内部哈希函数将键映射到底层数组的索引。
  • 冲突解决：使用带有二次探测的开放寻址法来处理冲突（当两个键哈希到同一个索引时）。
• 高级接口：字典 API 简单直观，对于常见操作（如插入 (`dict[key] = value`）、检索 (`value = dict[key]`) 和删除 (`del dict[key]`)）具有清晰的语法。
• 可迭代性：您可以使用 `dict.keys()`、`dict.values()` 和 `dict.items()` 等方法来迭代键、值和键值对。这使得遍历和管理字典内容变得容易。
• 推导式：Python 支持字典推导式，允许以简洁易读的方式创建字典。
• 内置方法：Python 字典附带一套丰富的用于常见任务的方法，包括
  • `get(key, default)`：检索一个键的值，如果键不存在则返回默认值。
  • `update(other_dict)`：使用来自另一个字典的键值对更新字典。
  • `pop(key, default)`：删除一个键并返回其值，如果键不存在则返回默认值。
  • `clear()`：删除字典中的所有项。
• 安全和错误处理：尝试访问不存在的键时，会引发 `KeyError` 异常，可以使用 `try-except` 块来优雅地处理。

示例

输出

Name: Alina
Age: 30
City: Egypt
Updated Age: 31
City after deletion: Not Found
Name exists in hash table
Iterating over hash table:
name: Alina
age: 31
Squares dictionary: {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}