Hello 算法 1.2.0 繁体中文 C++ 版

• 语言: 中文（繁体）
• 格式: .pdf
• 来源: github.com/krahets

摘要

文档主要介绍了雜湊表的基本原理和实现方法。雜湊表通过雜湊函式将键映射到数组索引，从而实现快速查找。常见的雜湊衝突处理方法包括鏈式地址和開放定址。鏈式地址通过链表存储冲突元素，而開放定址则通过多次探測来解决冲突。不同程式語言如Java和Python在實現雜湊表时采用不同的方法。此外，文档还提到雜湊演算法在密碼學中的应用，如MD5和SHA-1，用于保证数据完整性和安全性。

AI总结

# 文档总结

## 《Hello 算法 1.2.0 繁体中文 C++ 版》 第 6 章：雜湊表

### 6.1 雜湊表
- 雜湊表是一種數據結構，能夠在 $ O(1) $ 時間內完成查詢操作，效率極高。
- 常見操作包括查詢、新增鍵值對、刪除鍵值對和走訪雜湊表等。
- 雜湊函式將 `key` 映射為數組索引，用於訪問對應桶並獲取 `value`。

### 6.2 雜湊衝突
- 不同的 `key` 可能會被雜湊函式映射到相同的索引，導致雜湊衝突。
- 雜湊表容量越大，衝突機率越低，但扩容開銷較大。
- 負載因子（雜湊表中元素數量除以桶數量）反映了衝突的嚴重程度，常用於觸發扩容。

### 6.3 雜湊衝突的處理
1. **鏈式位址**：
- 將衝突元素存儲在鏈結串列中。
- 鏈結串列過長會降低查詢效率，可進一步轉換為紅黑樹以提升效率。
2. **開放定址**：
- 通過多次探測來處理衝突。
- 線性探查 simplicity but poor performance；多重雜湊效果更好但計算量增加。

### 6.4 不同語言的雜湊表實現
- **Java**：`HashMap` 使用鏈式位址。
- **Python**：`Dict` 使用開放定址。
- **C++**：內建 `std::hash()` 仅提供基本資料型別的雜湊值計算，物件和陣列的雜湊值需自訂實現。

### 6.5 雜湊演算法
- 雜湊演算法應該具有確定性、高效率和均勻分佈的特點。
- 雜湊演算法通常使用大質數作為模數，以最大化均勻分佈。
- 常見的雜湊演算法包括 MD5、SHA-1、SHA-2 和 SHA-3 等，主要用於校驗檔案完整性和安全應用。

### 6.6 程式碼示例

string str = "Hello 演算法";
size_t hashStr = hash()(str);

### 6.7 小結
- 雜湊表核心在於高效的查找和存儲。
- 雜湊衝突是設計和實現雜湊表時需要重點考慮的問題。
- 不同程式語言的雜湊表實現各有特色，需根據具體場景選擇合適的方案。

---

**本書特色**：
- 提供動畫圖解和可一鍵執行的程式碼示例，便於理解理論與實踐。
- 強調手腦並用的學習方式，幫助讀者掌握資料結構與演算法的核心思想。

**本書亮點**：
- 作者為靳宇棟 (@krahets)，並有多位貢獻者參與程式碼審閱。
- 附帶 GitHub 約儲 `github.com/krahets/hello-algo`，提供完整的原始碼和更多資源。

---

**本書目錄**：
- 第 0 章：前言
- 第 1 章：初識演算法
- 第 2 章：複雜度分析
- 第 3 章：資料結構
- 第 4 章：陣列與鏈結串列
- 第 5 章：堆疊與佇列
- 第 6 章：雜湊表
- 第 7 章：樹