企业官网建设流程全解析

数据结构：二分查找与哈希查找的实战对比与场景选择

> 本文整理数据结构：二分查找与哈希查找的实战对比与场景选择的排查思路与可运行示例，适合课程设计、实验调试时查阅。

本章要点

二分查找和哈希查找是两种最常用的查找算法，但它们的适用场景截然不同。本章通过可运行的Python代码对比两种算法，帮助你理解：

- 何时二分查找比哈希查找更快

- 哈希查找为什么在某些场景下“看起来慢”

- 如何在实际项目（如爬虫去重、简易数据库）中选择正确的查找策略

原理简述

二分查找

基于有序数组，每次将查找范围缩小一半。时间复杂度O(log n)，空间复杂度O(1)。

哈希查找

通过哈希函数将key映射到存储位置。平均时间复杂度O(1)，最坏O(n)，空间复杂度O(n)。

核心区别：

- 二分查找需要数据有序，但可以原地查找

- 哈希查找不要求顺序，但需要额外内存

示例代码：关键词搜索工具

下面实现一个简单的关键词搜索工具，对比两种算法在实际搜索中的表现：

import time import random import string # 生成随机关键词数据 def generate_data(size=100000): """生成模拟的URL或关键词数据""" data = [] for i in range(size): # 生成随机字符串作为关键词 keyword = ''.join(random.choices(string.ascii_lowercase, k=8)) data.append(keyword) return sorted(data) # 二分查找需要有序 # 二分查找实现 def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 # 哈希查找实现 def hash_search(hash_table, target): return hash_table.get(target, -1) # 性能对比测试 def performance_comparison(): # 生成测试数据 print("生成100000条测试数据...") sorted_data = generate_data(100000) # 构建哈希表 hash_table = {key: idx for idx, key in enumerate(sorted_data)} # 准备测试关键词（存在和不存在各一半） test_keys = [] for _ in range(1000): if random.random() < 0.5: # 存在的关键词 test_keys.append(random.choice(sorted_data)) else: # 不存在的关键词 test_keys.append(''.join(random.choices(string.ascii_lowercase, k=8))) # 测试二分查找 start = time.time() for key in test_keys: binary_search(sorted_data, key) binary_time = time.time() - start # 测试哈希查找 start = time.time() for key in test_keys: hash_search(hash_table, key) hash_time = time.time() - start print(f"\n二分查找总耗时: {binary_time:.4f}秒") print(f"哈希查找总耗时: {hash_time:.4f}秒") print(f"数据量: 100000条, 查询次数: 1000次") if __name__ == "__main__": performance_comparison()

调试要点

1.数据量小时二分更快：当数据量小于1000条时，二分查找的log n优势不明显，但哈希表的哈希计算开销还在

2.哈希更耗内存：上述代码中，哈希表占用内存约为有序列表的2-3倍

3.哈希冲突影响性能：如果哈希函数设计不好，最坏情况会退化为O(n)

复杂度对比

| 场景 | 二分查找 | 哈希查找 |

|------|----------|----------|

| 平均时间复杂度 | O(log n) | O(1) |

| 最坏时间复杂度 | O(log n) | O(n) |

| 空间复杂度 | O(1) | O(n) |

| 数据要求 | 必须有序 | 无要求 |

| 适合数据量 | 百万级以下 | 千万级以上 |

常见坑与决策指南

何时用二分查找

-数据已经有序：比如数据库的B+树索引本质就是二分查找的变种

-内存敏感：比如嵌入式设备或移动端，不能承受哈希表的额外内存

-范围查询：二分查找可以快速找到某个区间的所有元素

何时用哈希查找

-频繁插入删除：哈希表插入删除都是O(1)，而有序数组插入需要O(n)

-精确查找：只需要判断某个key是否存在，不需要范围查询

-数据量大且无序：比如爬虫去重，每天千万级URL

实战案例：爬虫去重优化

# 场景：爬虫需要判断URL是否已经爬取过 # 方案1：用哈希表去重（适合千万级） visited_urls = set() # Python的set本质就是哈希表 def is_visited_hash(url): return url in visited_urls # 方案2：用二分查找去重（适合百万级，且需要排序） visited_list = [] def is_visited_binary(url): # 需要先排序，然后二分查找 idx = binary_search(visited_list, url) return idx != -1 # 实际选择：如果每天爬取100万URL，用哈希表 # 如果只有10万URL且需要按时间排序输出，用二分查找

简易数据库查询中的副业应用

假设你要开发一个简单的商品价格查询工具（比如帮人查某宝商品历史价格）：

# 用哈希表实现简易缓存 class PriceCache: def __init__(self): self.cache = {} # 哈希表实现O(1)查找 self.hit_count = 0 self.miss_count = 0 def get_price(self, product_id): if product_id in self.cache: self.hit_count += 1 return self.cache[product_id] else: self.miss_count += 1 # 模拟从数据库查询 price = self.query_database(product_id) self.cache[product_id] = price return price def query_database(self, product_id): # 实际项目中这里会查询数据库 # 这里为了演示，返回模拟数据 return random.randint(100, 10000) # 使用示例 cache = PriceCache() # 第一次查询，缓存未命中 print(cache.get_price("product_001")) # 从数据库获取 # 第二次查询，缓存命中 print(cache.get_price("product_001")) # 直接从缓存返回

决策流程图

数据是否有序？ ├── 是 → 数据量是否小于100万？ │ ├── 是 → 用二分查找（省内存，速度快） │ └── 否 → 用哈希查找（O(1)查询更重要） └── 否 → 是否需要范围查询？ ├── 是 → 先排序再用二分查找 └── 否 → 用哈希查找

总结

二分查找和哈希查找不是对立的，而是互补的。理解它们的适用场景，能让你在实际项目中做出更好的技术决策。比如在爬虫去重系统中，先用哈希表做快速去重，再用有序数组做二分查找进行历史数据分析，这种组合策略往往能取得最佳效果。

下一节将讲树查找，适合构建更复杂的索引。学完之后，你可以尝试用树结构实现一个简易的搜索引擎，这在实际项目中很有价值。