python爬虫 + hashtable + uniapp + 事务
·
#44
今日计划
1.python 爬虫
看懂 p15并且
完成俩个实战demo
2.前端
看完3个小时 的vue3 速成课 然后
20个小时的主课uniapp 再安排时间看
安排vue3 的详细课程
小兔鲜儿项目day 4 PPT
优化项目 把那个项目前端组件化 有时间搞
黑马javaweb的tlias 前端项目找时间写
3.后端 ssm 框架 视频课 今天要看完
事务
4.瑞吉外卖 day1
5.算法
哈希表 能写多少写多少
今日源码
豆瓣爬虫
下面针对这段豆瓣影评爬虫代码，用「0基础小白」能理解的语言分模块讲解，把每个部分的作用和逻辑讲清楚：
### **整体介绍**
这段代码是一个「豆瓣影评爬虫」，简单说就是：
**自动打开豆瓣电影的「最受欢迎影评」页面，一页一页地把电影名、影评内容等信息抄下来，然后存到数据库里，方便后续查看或分析**。
用到的核心工具：
- `requests`：模拟浏览器上网，获取网页内容；
- `pyquery`：解析网页，提取我们需要的信息（比如电影名、影评）；
- `pymongo`：把提取的信息存到MongoDB数据库（相当于一个电子文件夹）。
### **模块1：准备工作（导入工具+配置参数）**
```python
# 导入需要的工具（相当于请帮手）
import requests # 用来上网抓网页
from pyquery import PyQuery as pq # 用来解析网页内容
from pymongo import MongoClient # 用来连接数据库
import time # 用来控制时间（比如让程序歇一会儿）
import random # 用来生成随机数（比如随机歇1-3秒）
from urllib.parse import urljoin # 用来拼接完整网址
import re # 用来处理文字（比如提取电影名）
# 配置信息（相当于给爬虫定规则）
BASE_URL = "https://movie.douban.com/review/best/" # 要爬的网页地址（豆瓣最受欢迎影评）
MONGO_URI = "mongodb://localhost:27017/" # 数据库地址（本地的MongoDB）
MONGO_DB = "test_database" # 数据库名字（相当于一个文件夹）
MONGO_COLLECTION = "demo1" # 集合名字（相当于文件夹里的一个文件）
HEADERS = { ... } # 模拟浏览器的身份信息（让豆瓣以为是真人在访问）
MAX_PAGES = 100 # 最多爬100页
```
**小白理解**：
- 这里就像「准备工具包」：先把需要的工具（库）准备好，再设定好爬取的目标（网址）、存数据的地方（数据库）、访问规则（身份信息、爬多少页）。
- `HEADERS` 很重要：里面的 `User-Agent` 告诉豆瓣“我是浏览器”，`Cookie` 告诉豆瓣“我是登录用户”，避免被当成机器人拦截。
### **模块2：连接数据库（打开存放数据的文件夹）**
```python
def init_mongo():
"""初始化MongoDB连接，相当于打开存放数据的文件夹"""
try:
# 连接数据库（相当于打开文件夹）
client = MongoClient(MONGO_URI)
client.admin.command('ping') # 测试连接是否成功（相当于敲敲门：有人吗？）
print("MongoDB连接成功")
# 选择具体的数据库和集合（相当于打开文件夹里的某个文件）
db = client[MONGO_DB]
collection = db[MONGO_COLLECTION]
# 给"影评链接"做个标记：同一个链接只存一次（避免重复存储）
collection.create_index("review_url", unique=True)
return collection
except Exception as e:
# 如果连接失败，告诉我们原因并退出程序
print(f"MongoDB连接失败: {str(e)}")
exit(1)
```
**小白理解**：
- 数据库就像一个「电子文件夹」，我们爬来的影评需要存在这里。
- 这个函数的作用是：先确认文件夹能打开（连接成功），然后准备好一个“笔记本”（集合），并约定“同一篇影评不重复记”（唯一索引）。
### **模块3：爬取工具函数（具体干活的工具）**
这部分是爬虫的「核心工具」，负责具体的“上网-提取信息”工作。
#### 工具1：`fetch_page`（上网抓网页）
```python
def fetch_page(url, retry=3):
"""模拟浏览器打开网页，把网页内容抓下来"""
try:
# 随机歇1-3秒（避免频繁访问被豆瓣封IP，像真人浏览一样）
time.sleep(random.uniform(1, 3))
# 用requests打开网页（相当于在浏览器输入网址）
response = requests.get(url, headers=HEADERS, timeout=10)
if response.status_code == 200: # 200表示成功打开
response.encoding = "utf-8" # 确保中文显示正常
return response.text # 返回网页内容（HTML代码）
else:
# 如果打开失败，重试最多3次
print(f"请求失败，状态码：{response.status_code}，URL：{url}")
if retry > 0:
return fetch_page(url, retry - 1)
return None
except Exception as e:
# 遇到错误（比如网络断了），也重试
print(f"请求异常：{str(e)}，URL：{url}")
if retry > 0:
return fetch_page(url, retry - 1)
return None
```
**小白理解**：
- 这个函数就像一个「自动浏览器」，负责按网址打开网页，把网页上的内容（文字、图片等的代码）抓回来。
- 加了「随机休息」和「重试机制」，是为了更像真人操作，避免被网站拉黑。
#### 工具2：`parse_review_list`（从列表页提取影评链接）
```python
def parse_review_list(html):
"""从影评列表页（一页有多个影评）中，提取每篇影评的标题和详情页链接"""
doc = pq(html) # 用pyquery解析网页（相当于把HTML代码转换成可操作的结构）
review_items = doc(".review-item").items() # 找到所有影评项（每篇影评的容器）
# 如果没找到影评，说明可能到最后一页了
if not any(review_items):
print(" 此页没有找到影评项，可能已到达最后一页")
return []
# 遍历每篇影评，提取信息
for item in doc(".review-item").items():
title_elem = item(".main-bd h2 a") # 找到影评标题的位置
review_title = title_elem.text().strip() # 提取标题文字
# 提取详情页链接（可能是相对路径，需要拼接成完整网址）
review_url = urljoin(BASE_URL, title_elem.attr("href") or "")
# 返回提取的信息（生成器，一次返回一个）
yield {
"review_title": review_title,
"movie_name": "待提取", # 电影名在详情页里，先占位
"review_url": review_url
}
```
**小白理解**：
- 列表页就像「目录页」，上面有很多影评的标题和“查看全文”的链接。
- 这个函数的作用是：从目录页中，把每篇影评的标题和“查看全文”的链接抄下来，方便后续去详情页看完整内容。
#### 工具3：`parse_review_detail`（从详情页提取完整信息）
```python
def parse_review_detail(html, basic_info):
"""从影评详情页中，提取电影名、影评内容、发布时间等完整信息"""
doc = pq(html) # 解析详情页HTML
# 1. 提取电影名（在详情页的“影片信息”区域）
movie_name_elem = doc(".subject-title a") # 找到电影名的位置
movie_name = movie_name_elem.text().strip() or "未知电影" # 提取文字，没找到就标“未知”
# 2. 提取发布时间（作者什么时候发的影评）
publish_time = doc(".main-hd .time").text().strip()
# 3. 提取影评内容（去掉图片，只保留文字）
content_elem = doc(".review-content") # 找到影评内容的位置
content_elem.remove("img") # 移除图片标签（我们只需要文字）
review_content = content_elem.text().strip() # 提取文字内容
# 整合所有信息（把列表页的信息和详情页的信息合并）
return {
**basic_info, # 包含标题、链接等列表页信息
"movie_name": movie_name,
"publish_time": publish_time,
"review_content": review_content,
"crawl_time": time.strftime("%Y-%m-%d %H:%M:%S") # 记录爬取时间
}
```
**小白理解**：
- 详情页就是每篇影评的“全文页”，这里有我们需要的所有信息：电影名、具体影评内容、发布时间等。
- 这个函数的作用是：从全文页中，把这些信息一一提取出来，整理成一个完整的“记录”。
###** 模块4：主函数（总指挥，控制整个流程）**```python
def main():
"""主函数：控制整个爬取流程（从连接数据库，到一页页爬取，再到存数据）"""
collection = init_mongo() # 第一步：连接数据库（打开文件夹）
print(f"开始爬取豆瓣最受欢迎影评，将爬取{MAX_PAGES}页...")
# 循环爬取每一页（从第1页到第MAX_PAGES页）
for page_num in range(MAX_PAGES):
# 计算当前页的URL（豆瓣分页用start参数，每页20条，第1页start=0，第2页start=20...）
start = page_num * 20
page_url = f"{BASE_URL}?start={start}"
print(f"\n正在爬取第{page_num+1}/{MAX_PAGES}页: {page_url}")
# 1. 爬取当前页的列表页内容
list_html = fetch_page(page_url)
if not list_html: # 如果没抓到内容，跳过这一页
print(f"获取第{page_num+1}页失败，跳过")
continue
# 2. 解析列表页，得到这一页所有影评的基本信息（标题和链接）
review_list = list(parse_review_list(list_html))
# 如果这一页没有影评，说明爬完了，提前结束
if not review_list:
print(f"第{page_num+1}页没有影评，已到达最后一页，终止爬取")
break
print(f" 本页找到{len(review_list)}条影评")
# 3. 遍历每篇影评，爬详情页并存储
for review in review_list:
if not review["review_url"]: # 跳过没有链接的无效影评
print(" 跳过无效影评（URL为空）")
continue
print(f" 处理影评：{review['review_title']}")
# 3.1 爬取影评详情页
detail_html = fetch_page(review["review_url"])
if not detail_html:
print(" 详情页爬取失败，跳过")
continue
# 3.2 解析详情页，得到完整信息
try:
full_data = parse_review_detail(detail_html, review)
print(f" 解析成功，电影名：{full_data['movie_name']}")
except Exception as e:
print(f" 解析失败：{str(e)}，跳过")
continue
# 3.3 把完整信息存到数据库
try:
collection.insert_one(full_data)
print(" 已存入MongoDB")
except Exception as e:
if "duplicate key error" in str(e):
print(" 该影评已存在，跳过")
else:
print(f" 存储失败：{str(e)}")
# 爬完一页后，歇2-5秒再爬下一页（更像真人浏览）
time.sleep(random.uniform(2, 5))
print(f"\n爬取完成！共处理{page_num+1}页")
```
**小白理解**：
- 主函数就像「总指挥」，按步骤协调所有工具工作：
1. 先打开数据库（文件夹）；
2. 一页一页地爬：先爬列表页（目录），再根据目录里的链接爬每篇影评的详情页；
3. 每篇影评的完整信息提取后，存到数据库里；
4. 遇到错误（比如页面打不开、解析失败）就跳过，保证程序能继续跑。
### **模块5：程序入口（启动开关）**
```python
if __name__ == "__main__":
main() # 启动主函数，开始爬取
```
**小白理解**：
- 这行代码是程序的「启动开关」。当你运行这个Python文件时，它会自动调用`main()`函数，开始整个爬取流程。
### **总结：整个流程像这样**
1. 准备工具（导入库）和配置（目标网址、数据库地址等）；
2. 打开数据库（准备好存放数据的地方）；
3. 一页一页地爬：
- 爬列表页（目录），拿到每篇影评的标题和详情页链接；
- 逐个打开详情页，提取电影名、影评内容等信息；
- 把信息存到数据库，跳过重复或无效的内容；
4. 爬完设定的页数后，结束工作。
这样，你就有了一个自动收集豆瓣影评的小工具啦！
ajax 案例
这个爬虫程序采用模块化设计，主要分为配置、日志、存储、核心爬取和主控制五个模块。下面我将从逻辑和语法两方面进行详细讲解：
### 一、配置模块
```python
AJAX_URL = "https://movie.douban.com/j/chart/top_list"
PARAMS = {
"type": 24, # 喜剧片
"interval_id": "100:90", # 9分以上
"action": "",
"start": 0,
"limit": 20
}
COOKIE_TEMPLATE = "bid=b63PF17eImM; ..." # 省略部分内容
HEADERS = {
"User-Agent": "Mozilla/5.0 ...",
"Accept": "application/json",
"X-Requested-With": "XMLHttpRequest",
"Cookie": COOKIE_TEMPLATE
}
MAX_PAGES = 7
OUTPUT_FILE = "demo2.json"
```
**逻辑分析**：
- 定义爬虫的基本参数，包括目标URL、请求参数、请求头和输出配置
- 使用常量命名规范（全大写）提高代码可读性
- `COOKIE_TEMPLATE`需要替换为真实有效的Cookie
**语法亮点**：
- 使用字典结构组织请求参数和请求头
- 利用`urllib.parse.quote`处理可能的非ASCII字符（在`get_encoded_cookie`中）
### 二、日志模块
```python
def init_logging():
formatter = logging.Formatter('%(asctime)s - %(levelname)s - %(module)s - %(message)s')
console_handler = logging.StreamHandler()
console_handler.setFormatter(formatter)
console_handler.setLevel(logging.INFO)
file_handler = RotatingFileHandler(
'douban_spider.log',
maxBytes=10*1024*1024,
backupCount=3,
encoding='utf-8'
)
file_handler.setFormatter(formatter)
file_handler.setLevel(logging.DEBUG)
logger = logging.getLogger()
logger.setLevel(logging.DEBUG)
logger.addHandler(console_handler)
logger.addHandler(file_handler)
return logger
```
**逻辑分析**：
- 实现日志的多目的地输出（控制台和文件）
- 控制台只输出INFO及以上级别，文件保存所有级别（包括DEBUG）
- 使用`RotatingFileHandler`实现日志滚动，避免单个文件过大
**语法亮点**：
- 配置`encoding='utf-8'`确保中文日志正常显示
- 通过设置不同的`setLevel`实现日志分级
- 使用`%(module)s`自动获取调用日志的模块名
### 三、存储模块
```python
def init_storage(logger):
if not os.path.exists(OUTPUT_FILE):
with open(OUTPUT_FILE, 'w', encoding='utf-8') as f:
json.dump([], f)
logger.info(f"创建新JSON文件: {OUTPUT_FILE}")
else:
try:
with open(OUTPUT_FILE, 'r', encoding='utf-8') as f:
data = json.load(f)
if not isinstance(data, list):
raise ValueError("文件内容不是有效的JSON数组")
except (json.JSONDecodeError, ValueError) as e:
backup_file = f"{OUTPUT_FILE}.bak"
os.rename(OUTPUT_FILE, backup_file)
logger.warning(f"原文件格式错误，已备份至: {backup_file}")
with open(OUTPUT_FILE, 'w', encoding='utf-8') as f:
json.dump([], f)
return OUTPUT_FILE
def save_movies(movies, output_file, logger):
with open(output_file, 'r', encoding='utf-8') as f:
existing_data = json.load(f)
existing_ids = {movie['id'] for movie in existing_data}
new_movies = [movie for movie in movies if movie['id'] not in existing_ids]
if not new_movies:
return
existing_data.extend(new_movies)
with open(output_file, 'w', encoding='utf-8') as f:
json.dump(existing_data, f, ensure_ascii=False, indent=2)
```
**逻辑分析**：
- `init_storage`：初始化JSON文件，处理文件不存在或格式错误的情况
- `save_movies`：实现增量保存，通过电影ID去重
- 使用`ensure_ascii=False`确保中文正常保存
**语法亮点**：
- 使用集合`existing_ids`进行快速去重（O(1)时间复杂度）
- 通过`with open`实现文件的安全操作（自动关闭）
- 异常处理覆盖多种可能的文件错误情况
### 四、核心爬取模块
```python
def fetch_ajax_page(page, output_file, logger):
PARAMS["start"] = page * PARAMS["limit"]
logger.debug(f"爬取第{page+1}页，参数：{PARAMS}")
time.sleep(random.uniform(1, 3)) # 反爬策略
headers = HEADERS.copy()
headers["Cookie"] = get_encoded_cookie(headers["Cookie"])
response = requests.get(
url=AJAX_URL,
params=PARAMS,
headers=headers,
timeout=10
)
if response.status_code != 200:
return False
response.encoding = "utf-8"
try:
movie_list = response.json()
except json.JSONDecodeError as e:
return False
if not movie_list:
return False
processed_movies = []
for movie in movie_list:
try:
movie_info = {
"id": movie["id"],
"title": movie["title"],
"rating": movie["rating"][0],
"release_date": movie["release_date"],
"types": movie["types"],
"regions": movie["regions"],
"actors": movie["actors"],
"vote_count": movie["vote_count"],
"crawl_time": time.strftime("%Y-%m-%d %H:%M:%S")
}
processed_movies.append(movie_info)
except Exception as e:
continue
save_movies(processed_movies, output_file, logger)
return True
```
**逻辑分析**：
- 实现单页数据的爬取和处理流程
- 使用随机延时避免被反爬机制拦截
- 处理请求异常、JSON解析异常和数据处理异常
- 数据标准化处理（提取需要的字段）
**语法亮点**：
- 使用字典推导式和列表推导式简化代码
- 通过`response.encoding = "utf-8"`强制指定编码
- 多层异常处理确保程序健壮性
### 五、主控制模块
```python
def main():
logger = init_logging()
logger.info("===== 豆瓣喜剧片爬虫启动 =====")
output_file = init_storage(logger)
success_count = 0
for page in range(MAX_PAGES):
logger.info(f"开始爬取第{page+1}/{MAX_PAGES}页...")
success = fetch_ajax_page(page, output_file, logger)
if not success:
logger.info(f"第{page+1}页爬取失败，尝试重试...")
success = fetch_ajax_page(page, output_file, logger)
if not success:
logger.warning(f"第{page+1}页重试失败，跳过")
else:
success_count += 1
else:
success_count += 1
try:
with open(output_file, 'r', encoding='utf-8') as f:
total_movies = len(json.load(f))
logger.info(f"===== 爬虫结束 =====")
logger.info(f"成功爬取: {success_count}/{MAX_PAGES} 页")
logger.info(f"共获取: {total_movies} 部电影")
logger.info(f"数据已保存至: {output_file}")
except Exception as e:
logger.error(f"读取最终结果失败: {e}", exc_info=True)
```
**逻辑分析**：
- 实现整体控制流程：初始化→分页爬取→结果统计
- 实现失败重试机制（每个页面最多尝试2次）
- 统计并输出爬取结果摘要
**语法亮点**：
- 使用`success_count`计数器统计成功页数
- 嵌套的条件判断实现重试逻辑
- 最终结果的统计和展示
### 六、关键语法与设计模式
1. **异常处理模式**：
```python
try:
# 可能出错的代码
except ExceptionType as e:
# 错误处理逻辑
logger.error(f"错误信息: {e}")
finally:
# 无论是否出错都执行的代码
```
2. **文件操作最佳实践**：
```python
with open(file_path, 'r', encoding='utf-8') as f:
data = json.load(f)
# 文件自动关闭
```
3. **日志使用规范**：
```python
logger.debug("调试信息")
logger.info("正常运行信息")
logger.warning("警告信息")
logger.error("错误信息")
```
4. **配置与代码分离**：
将常量配置集中在文件开头，便于修改和维护
### 七、总结
这个爬虫程序通过模块化设计实现了功能的解耦，主要特点包括：
1. 健壮的错误处理机制，确保程序稳定运行
2. 完善的日志系统，便于问题追踪
3. 增量存储和数据去重，避免重复工作
4. 遵守反爬规则，使用随机延时
5. 数据标准化处理，便于后续分析
在语法层面，充分利用了Python的高级特性（如列表推导式、集合操作、with语句），同时保持了代码的可读性和可维护性。
hashtable实现
以下是为你添加详细注释后的 `HashTable` 类代码，逐行解释了每个方法和关键逻辑的作用、实现思路以及设计考量，帮助理解哈希表（散列表）的核心原理和代码运行流程：
```java
public class HashTable {
// 节点类，用于表示哈希表中链表的每个节点，存储键值对及链表连接信息
static class Entry {
int hash; // 哈希码，用于快速确定元素在哈希表中的位置，辅助哈希运算
Object key; // 键，作为查找元素的依据，要求具有唯一性（逻辑上）
Object value; // 值，存储对应键关联的数据
Entry next; // 指向下一个节点的引用，用于处理哈希冲突（拉链法）
public Entry(int hash, Object key, Object value) {
this.hash = hash;
this.key = key;
this.value = value;
}
}
// 哈希表的底层存储结构，是一个 Entry 类型的数组，每个元素对应一条链表，用于处理哈希冲突
Entry[] table = new Entry[16];
// 哈希表中当前存储的键值对元素个数，用于判断是否需要扩容
int size = 0;
// 负载因子，用于计算扩容阈值，平衡哈希表的空间利用率和查询效率，默认取 0.75 是经验值
float loadFactor = 0.75f;
// 扩容阈值，当元素个数 size 超过该值时，触发哈希表扩容
int threshold = (int) (loadFactor * table.length);
/*
* 求模运算替换为位运算的说明：
* - 前提：数组长度是 2 的 n 次方（这里初始长度 16 是 2^4 ，扩容也是按 2 倍扩容，保证一直是 2 的幂）
* - 原理：hash % 数组长度 等价于 hash & (数组长度 - 1) ，位运算效率比取模运算高很多
*/
// 根据哈希码和键从哈希表中获取对应的值
Object get(int hash, Object key) {
// 通过位运算计算元素在哈希表数组中的索引位置，利用数组长度是 2 的幂的特性提升效率
int idx = hash & (table.length - 1);
// 如果该索引位置对应的链表为空，说明没有对应的元素，直接返回 null
if (table[idx] == null) {
return null;
}
// 从该索引位置的链表头开始遍历查找
Entry p = table[idx];
while (p != null) {
// 如果当前节点的键与要查找的键相等，说明找到对应元素，返回其值
if (p.key.equals(key)) {
return p.value;
}
// 继续遍历链表的下一个节点
p = p.next;
}
// 遍历完链表都没找到，返回 null
return null;
}
// 向哈希表中存入键值对，如果键已存在则更新对应的值；如果不存在则新增键值对
void put(int hash, Object key, Object value) {
// 计算元素要存入的索引位置
int idx = hash & (table.length - 1);
if (table[idx] == null) {
// 1. 如果该索引位置对应的链表为空，直接创建新节点存入
table[idx] = new Entry(hash, key, value);
} else {
// 2. 该索引位置对应的链表不为空，沿链表查找是否有重复键
Entry p = table[idx];
while (true) {
// 如果找到键相同的节点，更新其值并返回（结束方法）
if (p.key.equals(key)) {
p.value = value;
return;
}
// 如果当前节点是链表的最后一个节点（下一个节点为空），跳出循环准备新增节点
if (p.next == null) {
break;
}
// 继续遍历链表的下一个节点
p = p.next;
}
// 遍历到链表末尾都没找到重复键，新增节点到链表末尾
p.next = new Entry(hash, key, value);
}
// 新增元素后，更新元素个数
size++;
// 判断是否需要扩容：当元素个数超过扩容阈值时，进行扩容操作
if (size > threshold) {
resize();
}
}
// 哈希表扩容方法，将哈希表的容量翻倍（变为原来的 2 倍），并重新分布原有元素
private void resize() {
// 创建新的哈希表数组，容量是原数组的 2 倍
Entry[] newTable = new Entry[table.length << 1];
// 遍历原哈希表数组中的每个索引位置
for (int i = 0; i < table.length; i++) {
// 获取当前索引位置对应的链表头节点
Entry p = table[i];
if (p != null) {
/*
* 拆分链表，移动到新数组，拆分规律：
* 一个链表最多拆成两个子链表，依据是节点哈希码与原数组长度按位与的结果：
* - hash & table.length == 0 的节点为一组（子链表 a ）
* - hash & table.length != 0 的节点为一组（子链表 b ）
* 这样拆分的原因是扩容后新索引位置的计算方式变化（新长度是原长度的 2 倍 ），
* 可以利用位运算快速确定元素在新数组中的位置，提升效率
*/
Entry a = null; // 用于构建子链表 a 的指针
Entry b = null; // 用于构建子链表 b 的指针
Entry aHead = null; // 子链表 a 的头节点
Entry bHead = null; // 子链表 b 的头节点
while (p != null) {
if ((p.hash & table.length) == 0) {
if (a != null) {
a.next = p;
} else {
aHead = p;
}
a = p; // 将当前节点分配到子链表 a
} else {
if (b != null) {
b.next = p;
} else {
bHead = p;
}
b = p; // 将当前节点分配到子链表 b
}
// 继续遍历原链表的下一个节点
p = p.next;
}
// 规律：子链表 a 保持在新数组中的原索引位置；子链表 b 的索引位置为原索引 + 原数组长度
if (a != null) {
a.next = null; // 断开子链表 a 的末尾连接，避免循环引用
newTable[i] = aHead; // 将子链表 a 放入新数组的原索引位置
}
if (b != null) {
b.next = null; // 断开子链表 b 的末尾连接，避免循环引用
// 将子链表 b 放入新数组的 i + table.length 索引位置
newTable[i + table.length] = bHead;
}
}
}
// 将哈希表的底层存储数组替换为新数组
table = newTable;
// 重新计算扩容阈值
threshold = (int) (loadFactor * table.length);
}
// 根据哈希码和键从哈希表中删除对应的键值对，返回被删除的值；如果不存在则返回 null
Object remove(int hash, Object key) {
// 计算要删除元素所在的索引位置
int idx = hash & (table.length - 1);
// 如果该索引位置对应的链表为空，说明没有要删除的元素，返回 null
if (table[idx] == null) {
return null;
}
// 记录当前遍历的节点
Entry p = table[idx];
// 记录当前节点的前一个节点，用于删除操作时调整链表连接
Entry prev = null;
while (p != null) {
// 如果找到键匹配的节点，执行删除操作
if (p.key.equals(key)) {
if (prev == null) {
// 要删除的是链表头节点，直接将链表头指向下一个节点
table[idx] = p.next;
} else {
// 要删除的是非链表头节点，将前一个节点的 next 指向当前节点的 next
prev.next = p.next;
}
// 删除元素后，更新元素个数
size--;
// 返回被删除节点的值
return p.value;
}
// 更新前一个节点为当前节点
prev = p;
// 继续遍历链表的下一个节点
p = p.next;
}
// 遍历完链表都没找到要删除的元素，返回 null
return null;
}
}
```
### 关键逻辑补充说明
1. **哈希冲突处理**：采用**拉链法**（链地址法），当不同键的哈希运算结果对应到哈希表数组的同一个索引时，会在该索引位置形成一条链表，依次存储这些键值对节点。这样处理可以在一定程度上解决哈希冲突问题，但也要注意链表过长会影响查询效率，所以需要通过扩容等机制来平衡。
2. **扩容机制**：当哈希表中元素个数 `size` 超过扩容阈值 `threshold`（由负载因子和当前数组长度计算得到 ）时，会触发扩容。扩容时新建一个容量为原数组 2 倍的数组，然后将原数组中每个链表的节点按照新的规则（依据节点哈希码与原数组长度的位与结果 ）拆分到新数组的对应位置，以此保证哈希表在扩容后仍能高效工作，避免链表过长导致查询性能下降。
3. **位运算优化**：利用数组长度是 2 的幂这一特点，将原本的取模运算 `hash % table.length` 替换为位运算 `hash & (table.length - 1)` ，因为位运算在计算机底层执行效率更高，能提升哈希表的整体性能。
通过这样详细的注释，相信你能更清晰地理解这个哈希表实现的每一处细节和背后的设计思想，有助于学习哈希表的数据结构原理以及在 Java 中的手动实现方式。
好的！我将从**哈希表核心原理**、**代码实现细节**、**性能优化**、**潜在问题**四个维度深入剖析这个 `HashTable` 实现。
### 一、哈希表核心原理
#### 1. 基本概念
- **哈希表**（Hash Table）：通过**哈希函数**将键（Key）映射到数组索引位置，实现O(1)时间复杂度的插入、查询、删除操作。
- **哈希冲突**（Hash Collision）：不同的键通过哈希函数计算出相同的索引位置。
- **负载因子**（Load Factor）：元素数量/数组长度，控制哈希表的空间利用率和性能。
#### 2. 解决哈希冲突的两种主流方法
1. **拉链法**（Chaining）：数组每个位置存储链表，冲突的元素添加到链表中。
（如代码中的 `Entry` 链表结构）
2. **开放寻址法**（Open Addressing）：冲突时寻找下一个空闲位置。
（如线性探测、二次探测等）
#### 3. 为什么选择拉链法？
- **优势**：实现简单，无需频繁扩容，适合冲突较多的场景。
- **劣势**：链表过长时查询效率下降（O(n)），需通过扩容优化。
### 二、代码实现细节
#### 1. 哈希函数与索引计算
```java
int idx = hash & (table.length - 1);
```
- **前提条件**：数组长度必须是 **2的幂次方**（如16、32、64...）。
- **原理**：当数组长度为 `2^n` 时，`hash % 2^n` 等价于 `hash & (2^n - 1)`。
例如：`hash % 16` 等价于 `hash & 15`（15的二进制是 `0000 1111`）。
- **优势**：位运算比取模运算快得多（CPU直接支持）。
#### 2. 扩容机制（Resize）
```java
private void resize() {
Entry[] newTable = new Entry[table.length << 1]; // 容量翻倍
// ... 重新分配元素到新数组 ...
}
```
- **触发条件**：元素数量超过阈值（`size > threshold`）。
- **阈值计算**：`threshold = 数组长度 × 负载因子`（默认 `16 × 0.75 = 12`）。
- **扩容步骤**：
1. 创建新数组（容量翻倍）。
2. **重新分配元素**：将原数组每个链表拆分为两个子链表（优化点！）。
#### 3. 链表拆分优化（Resize中的核心逻辑）
```java
// 原链表：0->8->16->24->32->40->48->null
// 拆分后：
// a链：0->16->32->48->null（索引位置不变）
// b链：8->24->40->null（索引位置+原数组长度）
```
- **拆分规则**：根据 `hash & 原数组长度` 的结果是否为0，将链表拆分为两个子链表。
- **数学原理**：扩容后，元素的新索引位置要么保持不变，要么变为 **原索引 + 原数组长度**。
例如：原数组长度16，扩容后为32：
- 若 `hash & 16 == 0`，则新索引 `hash & 31` 等于原索引 `hash & 15`。
- 若 `hash & 16 != 0`，则新索引为 `原索引 + 16`。
- **优势**：避免遍历所有元素重新计算哈希，时间复杂度从O(n)优化到O(1)。
### 三、性能优化点
#### 1. 位运算替代取模
- **取模运算**：`hash % table.length`（耗时：约10个CPU周期）。
- **位运算**：`hash & (table.length - 1)`（耗时：1个CPU周期）。
- **适用条件**：数组长度必须是2的幂次方。
#### 2. 负载因子的选择
- **默认值0.75**：是时间和空间效率的平衡。
- 负载因子过大（如1.0）：空间利用率高，但链表变长，查询变慢。
- 负载因子过小（如0.5）：链表更短，但频繁扩容浪费空间。
#### 3. 扩容时的链表拆分
- **传统方法**：遍历每个元素，重新计算哈希和索引（时间复杂度O(n)）。
- **优化方法**：利用位运算直接拆分链表（时间复杂度O(1)）。
### 四、潜在问题与改进方向
#### 1. 线程安全问题
- **当前实现**：非线程安全，多线程环境下可能出现数据不一致（如链表成环）。
- **改进方案**：
- 使用 `synchronized` 关键字（如 `Hashtable` 的实现）。
- 分段锁（如早期 `ConcurrentHashMap` 的实现）。
- CAS操作（如JDK8+ `ConcurrentHashMap` 的实现）。
#### 2. 哈希码分布不均
- **问题**：若哈希码分布不均匀，会导致链表长度差异大，部分查询退化为O(n)。
- **改进方案**：
- 对哈希码进行二次哈希（如JDK中 `HashMap` 的 `hash()` 方法）。
- 使用高质量的哈希函数（如MurmurHash）。
#### 3. 链表过长的性能问题
- **JDK8+的优化**：当链表长度超过8时，转换为红黑树（查询时间O(log n)）。
- **当前代码改进**：可添加类似逻辑，避免链表过长。
### 五、与JDK中HashMap的对比
| 特性 | 当前实现 | JDK HashMap (JDK8+) |
|--------------------|------------------------|-----------------------|
| 冲突解决方式 | 拉链法（链表） | 拉链法（链表+红黑树） |
| 扩容时链表处理 | 位运算直接拆分 | 遍历并重新计算哈希 |
| 线程安全 | 非线程安全 | 非线程安全 |
| 负载因子默认值 | 0.75 | 0.75 |
| 数组长度要求 | 必须为2的幂次方 | 自动调整为2的幂次方 |
### 六、面试高频问题
1. **为什么哈希表数组长度需要是2的幂次方？**
答：为了用位运算 `hash & (length-1)` 替代取模运算 `hash % length`，提升性能。
2. **HashMap在JDK7和JDK8中的区别？**
答：JDK8引入红黑树优化链表过长问题，扩容时链表拆分逻辑更高效（位运算直接拆分）。
3. **如何实现线程安全的哈希表？**
答：`Hashtable`（全量锁）、`ConcurrentHashMap`（分段锁/CAS）。
4. **负载因子为什么默认是0.75？**
答：通过泊松分布计算，0.75时哈希冲突概率和空间利用率达到较好平衡。
### 总结
这个 `HashTable` 实现通过**拉链法处理冲突**、**位运算优化索引计算**、**链表拆分优化扩容**，基本覆盖了哈希表的核心原理。但相比JDK中的 `HashMap`，缺少红黑树优化和更完善的线程安全支持。理解这些细节有助于掌握哈希表的底层原理，在面试和实际开发中灵活应用。
今日总结
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
22
0- 0
已为社区贡献5条内容
所有评论(0)