哈希查找（Hashing Search）是一种在特定数据结构——哈希表（Hash Table）中查找特定元素的高效算法。哈希表通过哈希函数（Hash Function）将输入的关键字映射到一个固定大小的地址区间（通常为数组索引），并使用冲突解决策略（如开放寻址法、链地址法等）处理可能出现的哈希冲突（不同的关键字映射到同一地址）。哈希查找的基本思想是：
-
计算哈希值：使用哈希函数将待查找的关键字转化为哈希表中的一个地址（索引）。
-
检查该地址：在哈希表中，查看该地址对应的存储单元是否包含待查找的关键字。如果包含，则查找成功，返回关键字对应的值；如果不包含，有两种可能：
- 如果哈希表使用了开放寻址法等冲突解决策略，继续按照某种规则检查其他可能的地址，直至找到关键字或确定关键字不在哈希表中。
- 如果哈希表使用了链地址法等冲突解决策略，沿着该地址对应的链表进行查找，直至找到关键字或链表结束。
时间复杂度：
- 最好情况（无冲突或冲突很少）：哈希函数能够将关键字均匀地分布到哈希表中，查找过程几乎不需要比较，时间复杂度接近 O(1)。
- 最坏情况（大量冲突，哈希表接近满载）：所有关键字都映射到同一个地址或相邻地址，查找过程可能需要遍历整个哈希表，时间复杂度为 O(n)。
- 平均情况：取决于哈希函数的质量、哈希表的负载因子（已存储元素数量与哈希表大小的比例）以及冲突解决策略。理想情况下，通过精心设计的哈希函数和适当的哈希表大小，可以将平均时间复杂度控制在接近 O(1)。
空间复杂度：哈希查找的空间复杂度主要取决于哈希表的大小，通常为O(n)。在实际应用中，为了保持较低的冲突率和较高的查找效率，哈希表的大小通常会略大于已存储元素的数量。
哈希查找适用于需要频繁进行插入、删除、查找操作且数据规模较大的场景，特别是当数据之间缺乏明显的顺序关系时。哈希查找的优势在于查找速度快，但前提是需要有足够的内存空间存储哈希表，并且哈希函数的设计至关重要。以下是使用Python内置dict（哈希表的一种实现）进行哈希查找的示例：
Python
1# 建立哈希表
2hash_table = {
3 'apple': 0.½,
4 'banana': 1.0,
5 'cherry': 0.75,
6 # ... 其他键值对
7}
8
9# 查找关键字
10target_key = 'banana'
11result = hash_table.get(target_key, None)
12if result is not None:
13 print(f"Target found, value: {result}")
14else:
15 print("Target not found")用Python内置的dict作为哈希表，通过get方法查找关键字'banana'对应的值。如果找到，返回值；否则返回None。Python的dict内部已经实现了高效的哈希函数和冲突解决策略，使得哈希查找操作变得简单易用。
