现代编程思想 哈希表与闭包 Hongbo Zhang ## 回顾 ## · 表 键值对的集合，其中键不重复 简单实现：二元组列表 - 添加时向队首添加 - 查询时从队首遍历 树实现：二叉平衡树 - 基于第五节课介绍的二叉平衡树，每个节点的数据为键值对 - 对树操作时比较第一个参数 ## 哈希表 - 哈希函数/散列函数 Hash function ◦ hash() == -900478401 ## · 哈希表 ◦ 利用哈希函数，将数据映射到数组索引中，进行快速的添加、查询、修改 1. // 对于 a: Array[(Key, Value)], key: Key, value: Value 2. let index = key.hash().mod_u(a.length()) // 键值--哈希-->哈希值-->取模--->数组索引 3 ## 哈希冲突 • 根据抽屉原理/鸽巢原理/生日问题 ☐ 不同数据的哈希可能相同 不同的哈希映射为数组索引时可能相同 - 解决哈希表的冲突 ◦ 直接寻址（分离链接）：同一索引下用另一数据结构存储 列表 二叉平衡搜索树等 ☐ 开放寻址 ■ 线性探查：当发现冲突后，索引递增，直到查找空位放入 ■ 二次探查（索引递增 $ 1^{2}2^{2}3^{2} $ ）等 ## 哈希表：直接寻址

列表 4.4 内存与缓存* 4.5 小结 第5章 栈与队列 5.1 栈 5.2 队列 5.3 双向队列 5.4 小结 第6章 哈希表 6.1 哈希表 6.2 哈希冲突 6.3 哈希算法 6.4 小结 第7章 树 7.1 二叉树 7.2 二叉树遍历 7.3 二叉树数组表示 7.4 二叉搜索树 7.5 AVL树* 9.1 图 9.2 图的基础操作 9.3 图的遍历 9.4 小结 第10章 搜索 10.1 二分查找 10.2 二分查找插入点 10.3 二分查找边界 10.4 哈希优化策略 10.5 重识搜索算法 10.6 小结 第11章 排序 11.1 排序算法 11.2 选择排序 11.3 冒泡排序 11.4 插入排序 11.5 快速排序 .. 359 15.5 小结 ..... 362 第 16 章 附录 16.1 编程环境安装 ..... 365 16.2 一起参与创作 ..... 367 16.3 术语表 ..... 369 ## 第 0 章 前言 

4.3. 列表 4.4. 小结 5. 栈与队列 5.1. 栈 5.2. 队列 5.3. 双向队列 5.4. 小结 6. 散列表 6.1. 哈希表 6.2. 哈希冲突 6.3. 哈希算法 6.4. 小结 7. 树 7.1. 二叉树 7.2. 二叉树遍历 7.3. 二叉树数组表示 7.4. 二叉搜索树 7.5. AVL树 $ ^{*} 165 9.4. 小结 ..... 171 10. 搜索 ..... 173 10.1. 二分查找 ..... 173 10.2. 二分查找边界 ..... 176 10.3. 哈希优化策略 ..... 180 10.4. 重识搜索算法 ..... 182 10.5. 小结 ..... 185 11. 排序 ..... 186 11.1. 排序算法 ..... 186 音，而字典是按照拼音的英文字母顺序排列的。假设我们需要查找一个拼音首字母为 r 的字，通常会这样操作： 1. 翻开字典约一半的页数，查看该页首字母是什么，假设首字母为 m。 2. 由于在英文字母表中 r 位于 m 之后，所以排除字典前半部分，查找范围缩小到后半部分。 3. 不断重复步骤 1-2，直至找到拼音首字母为 r 的页码为止。 ![Image](/uploads/documents/

2 链表 4.3 列表 4.4 小结 第5章 栈与队列 5.1 栈 5.2 队列 5.3 双向队列 5.4 小结 第6章 哈希表 6.1 哈希表 6.2 哈希冲突 6.3 哈希算法 6.4 小结 第7章 树 7.1 二叉树 7.2 二叉树遍历 7.3 二叉树数组表示 7.4 二叉搜索树 7.5 AVL树* 9.1 图 9.2 图基础操作 9.3 图的遍历 9.4 小结 第10章 搜索 10.1 二分查找 10.2 二分查找插入点 10.3 二分查找边界 10.4 哈希优化策略 10.5 重识搜索算法 10.6 小结 第11章 排序 11.1 排序算法 11.2 选择排序 11.3 冒泡排序 11.4 插入排序 11.5 快速排序 本书主要内容如图 0-1 所示。 复杂度分析：数据结构和算法的评价维度与方法。时间复杂度、空间复杂度的推算方法、常见类型、示例等。 数据结构：基本数据类型，数据结构的分类方法。数组、链表、栈、队列、哈希表、树、堆、图等数据结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。 · 算法：搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤、示例题目等。 ![

系统都可以建模为“图”；大到一个国家，小到一个家庭，社会的主要组织形式呈现出“树”的特征；冬天的衣服就像“栈”，最先穿上的最后才能脱下；羽毛球筒则如同“队列”，一端放入、另一端取出；字典就像一个“哈希表”，能够快速查找目标词条。 本书旨在通过清晰易懂的动画图解和可运行的代码示例，使读者理解算法和数据结构的核心概念，并能够通过编程来实现它们。在此基础上，本书致力于揭示算法在复杂世界中的生动体现，展现算法之美。希望本书能够帮助到你！ 4.4 内存与缓存 * 4.5 小结 第5章 栈与队列 5.1 栈 5.2 队列 5.3 双向队列 5.4 小结 第6章 哈希表 6.1 哈希表 6.2 哈希冲突 6.3 哈希算法 6.4 小结 第7章 树 7.1 二叉树 7.2 二叉树遍历 7.3 二叉树数组表示 7.4 二叉搜索树 7.5 AVL树 * 9.1 图 9.2 图的基础操作 9.3 图的遍历 9.4 小结 第10章 搜索 10.1 二分查找 10.2 二分查找插入点 10.3 二分查找边界 10.4 哈希优化策略 10.5 重识搜索算法 10.6 小结 第11章 排序 11.1 排序算法 11.2 选择排序 11.3 冒泡排序 11.4 插入排序 11.5 快速排序

統都可以建模為“圖”；大到一個國家，小到一個家庭，社會的主要組織形式呈現出“樹”的特徵；冬天的衣服就像“堆疊”，最先穿上的最後才能脫下；羽毛球簡則如同“佇列”，一端放入、一端取出；字典就像一個“雜湊表”，能夠快速查找目標詞條。 本書旨在透過清晰易懂的動畫圖解與可執行的程式碼範例，使讀者理解演算法和資料結構的核心概念，並能夠透過程式設計來實現它們。在此基礎上，本書致力於揭示演算法在複雜世界中的生動 4.3 串列 4.4 記憶體與快取* 4.5 小結 第5章 堆疊與佇列 5.1 堆疊 5.2 佇列 5.3 雙向佇列 5.4 小結 第6章 雜湊表 6.1 雜湊表 6.2 雜湊衝突 6.3 雜湊演算法 6.4 小結 第7章 樹 7.1 二元樹 7.2 二元樹走訪 7.3 二元樹陣列表示 7.4 二元搜尋樹 7 15.4 最大切分乘積問題 366 15.5 小結 370 第 16 章 附錄 371 16.1 程式設計環境安裝 372 16.2 一起參與創作 375 16.3 術語表 376 ## 第 0 章 前言  ##

系统都可以建模为“图”；大到一个国家，小到一个家庭，社会的主要组织形式呈现出“树”的特征；冬天的衣服就像“栈”，最先穿上的最后才能脱下；羽毛球简则如同“队列”，一端放入、另一端取出；字典就像一个“哈希表”，能够快速查找目标词条。 本书旨在通过清晰易懂的动画图解和可运行的代码示例，使读者理解算法和数据结构的核心概念，并能够通过编程来实现它们。在此基础上，本书致力于揭示算法在复杂世界中的生动体现，展现算法之美。希望本书能够帮助到你！ 列表 4.4 内存与缓存* 4.5 小结 第5章 栈与队列 5.1 栈 5.2 队列 5.3 双向队列 5.4 小结 第6章 哈希表 6.1 哈希表 6.2 哈希冲突 6.3 哈希算法 6.4 小结 第7章 树 7.1 二叉树 7.2 二叉树遍历 7.3 二叉树数组表示 7.4 二叉搜索树 7.5 AVL树* 9.1 图 9.2 图的基础操作 9.3 图的遍历 9.4 小结 第10章 搜索 10.1 二分查找 10.2 二分查找插入点 10.3 二分查找边界 10.4 哈希优化策略 10.5 重识搜索算法 10.6 小结 第11章 排序 11.1 排序算法 11.2 选择排序 11.3 冒泡排序 11.4 插入排序 11.5 快速排序

系统都可以建模为“图”；大到一个国家，小到一个家庭，社会的主要组织形式呈现出“树”的特征；冬天的衣服就像“栈”，最先穿上的最后才能脱下；羽毛球简则如同“队列”，一端放入、另一端取出；字典就像一个“哈希表”，能够快速查找目标词条。 本书旨在通过清晰易懂的动画图解和可运行的代码示例，使读者理解算法和数据结构的核心概念，并能够通过编程来实现它们。在此基础上，本书致力于揭示算法在复杂世界中的生动体现，展现算法之美。希望本书能够帮助到你！ 列表 4.4 内存与缓存* 4.5 小结 第5章 栈与队列 5.1 栈 5.2 队列 5.3 双向队列 5.4 小结 第6章 哈希表 6.1 哈希表 6.2 哈希冲突 6.3 哈希算法 6.4 小结 第7章 树 7.1 二叉树 7.2 二叉树遍历 7.3 二叉树数组表示 7.4 二叉搜索树 7.5 AVL树* 9.1 图 9.2 图的基础操作 9.3 图的遍历 9.4 小结 第10章 搜索 10.1 二分查找 10.2 二分查找插入点 10.3 二分查找边界 10.4 哈希优化策略 10.5 重识搜索算法 10.6 小结 第11章 排序 11.1 排序算法 11.2 选择排序 11.3 冒泡排序 11.4 插入排序 11.5 快速排序

統都可以建模為“圖”；大到一個國家，小到一個家庭，社會的主要組織形式呈現出“樹”的特徵；冬天的衣服就像“堆疊”，最先穿上的最後才能脫下；羽毛球簡則如同“佇列”，一端放入、一端取出；字典就像一個“雜湊表”，能夠快速查找目標詞條。 本書旨在透過清晰易懂的動畫圖解與可執行的程式碼範例，使讀者理解演算法和資料結構的核心概念，並能夠透過程式設計來實現它們。在此基礎上，本書致力於揭示演算法在複雜世界中的生動 4.3 串列 4.4 記憶體與快取* 4.5 小結 第5章 堆疊與佇列 5.1 堆疊 5.2 佇列 5.3 雙向佇列 5.4 小結 第6章 雜湊表 6.1 雜湊表 6.2 雜湊衝突 6.3 雜湊演算法 6.4 小結 第7章 樹 7.1 二元樹 7.2 二元樹走訪 7.3 二元樹陣列表示 7.4 二元搜尋樹 7 15.4 最大切分乘積問題 357 15.5 小結 360 第 16 章 附錄 362 16.1 程式設計環境安裝 363 16.2 一起參與創作 366 16.3 術語表 367 ## 第 0 章 前言  ##

A。原因是其它三个都吃过，可是香蕉，我家那种野香蕉树，香蕉就只有拇指大小，还特别涩，哪能吃啊。 长大了之后，也会觉得过得很苦逼，比如填表格的时候 请问你的婚姻状况是？ A. 未婚 B 已婚 C 离异 都填了二十几年的表了，选择永远是 A。 上面两个问题有啥共同点么？ 都是很傻逼...？ 哈哈，不是的，它们的共同点都是提供了 ABCD 让我们选择。 编程时我们要如何保存 A B C D 这种选择题和答案呢？ V2EX 上问了下，马上就有好心人来告诉我，可以把 collection 翻译成 容器，谢谢了 Rust 语言的容器标准库提供了最常见的通用的数据结构的实现。包括 向量（Vector）、哈希表（HashMap）、哈希集合（HashSet）等等。 Rust 容器库提供的数据结构没有 C++ 或 Java 那么多那么细致，但上面三个也足够使用了。 本章节我们将会详细的介绍上面提到的三个数据结构。 ### 20 30 40 500 [20, 30, 40, 500] ### 20.2 哈希表 HashMap 哈希表 HashMap 就是 键值对的集合。哈希表中不允许有重复的键，但允许不同的键有相同的值。 从另一方面说，哈希表有点像查找表。键用于查找值。 Rust 语言使用 HashMap 结构体来表示哈希表。 HashMap 结构体在 Rust 语言标准库中的 std::collections