字节，在大多数编程语言中取决于特定的字符编码方法，详见“字 符编码”章节。 ‧ 即使表示布尔量仅需 1 位（0 或 1），它在内存中通常也存储为 1 字节。这是因为现代计算机 CPU 通常 将 1 字节作为最小寻址内存单元。 那么，基本数据类型与数据结构之间有什么联系呢？我们知道，数据结构是在计算机中组织与存储数据的方 式。这句话的主语是“结构”而非“数据”。 如果想表示“一排数字”，我们自然会想到使用数 以采用以下策略。 1. 改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。 2. 仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。 哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。 第 6 章 哈希表 hello‑algo.com 120 6.2.1 链式地址 在原始哈希表中，每个桶仅能存储一个键值对。链式地址（separate chaining）将单个元素转换为链表，将键 很差。此时可以将链表转换为“AVL 树”或“红黑树”，从而 将查询操作的时间复杂度优化至 ?(log ?) 。 6.2.2 开放寻址 开放寻址（open addressing）不引入额外的数据结构，而是通过“多次探测”来处理哈希冲突，探测方式主 要包括线性探测、平方探测和多次哈希等。 下面以线性探测为例，介绍开放寻址哈希表的工作机制。 1. 线性探测 线性探测采用固定步长的线性搜索来进行探测，其操作方法与普通哈希表有所不同。

字节，在大多数编程语言中取决于特定的字符编码方法，详见“字 符编码”章节。 ‧ 即使表示布尔量仅需 1 位（0 或 1），它在内存中通常也存储为 1 字节。这是因为现代计算机 CPU 通常 将 1 字节作为最小寻址内存单元。 那么，基本数据类型与数据结构之间有什么联系呢？我们知道，数据结构是在计算机中组织与存储数据的方 式。这句话的主语是“结构”而非“数据”。 如果想表示“一排数字”，我们自然会想到使用数 以采用以下策略。 1. 改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。 2. 仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。 哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。 第 6 章 哈希表 www.hello‑algo.com 120 6.2.1 链式地址 在原始哈希表中，每个桶仅能存储一个键值对。链式地址（separate chaining）将单个元素转换为链表，将键 很差。此时可以将链表转换为“AVL 树”或“红黑树”，从而 将查询操作的时间复杂度优化至 ?(log ?) 。 6.2.2 开放寻址 开放寻址（open addressing）不引入额外的数据结构，而是通过“多次探测”来处理哈希冲突，探测方式主 要包括线性探测、平方探测和多次哈希等。 下面以线性探测为例，介绍开放寻址哈希表的工作机制。 1. 线性探测 线性探测采用固定步长的线性搜索来进行探测，其操作方法与普通哈希表有所不同。

字节，在大多数编程语言中取决于特定的字符编码方法，详见“字 符编码”章节。 ‧ 即使表示布尔量仅需 1 位（0 或 1），它在内存中通常也存储为 1 字节。这是因为现代计算机 CPU 通常 将 1 字节作为最小寻址内存单元。 那么，基本数据类型与数据结构之间有什么联系呢？我们知道，数据结构是在计算机中组织与存储数据的方 式。这句话的主语是“结构”而非“数据”。 如果想表示“一排数字”，我们自然会想到使用数 以采用以下策略。 1. 改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。 2. 仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。 哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。 6.2.1 链式地址 在原始哈希表中，每个桶仅能存储一个键值对。「链式地址 separate chaining」将单个元素转换为链表，将 键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表中。图 很差。此时可以将链表转换为“AVL 树”或“红黑树”，从而 将查询操作的时间复杂度优化至 ?(log ?) 。 6.2.2 开放寻址 「开放寻址 open addressing」不引入额外的数据结构，而是通过“多次探测”来处理哈希冲突，探测方式主 要包括线性探测、平方探测和多次哈希等。 下面以线性探测为例，介绍开放寻址哈希表的工作机制。 1. 线性探测 线性探测采用固定步长的线性搜索来进行探测，其操作方法与普通哈希表有所不同。

字节，在大多数编程语言中取决于特定的字符编码方法，详见“字 符编码”章节。 ‧ 即使表示布尔量仅需 1 位（0 或 1），它在内存中通常被存储为 1 字节。这是因为现代计算机 CPU 通常 将 1 字节作为最小寻址内存单元。 那么，基本数据类型与数据结构之间有什么联系呢？我们知道，数据结构是在计算机中组织与存储数据的方 式。它的主语是“结构”而非“数据”。 如果想要表示“一排数字”，我们自然会想到使用数 以采用以下策略。 1. 改良哈希表数据结构，使得哈希表可以在存在哈希冲突时正常工作。 2. 仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。 哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。 6.2.1 链式地址 在原始哈希表中，每个桶仅能存储一个键值对。「链式地址 separate chaining」将单个元素转换为链表，将 键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表中。图 } } 值得注意的是，当链表很长时，查询效率 ?(?) 很差。此时可以将链表转换为“AVL 树”或“红黑树”，从而 将查询操作的时间复杂度优化至 ?(log ?) 。 6.2.2 开放寻址 「开放寻址 open addressing」不引入额外的数据结构，而是通过“多次探测”来处理哈希冲突，探测方式主 要包括线性探测、平方探测、多次哈希等。 1. 线性探测 线性探测采用固定步长的线

扩容来减小冲突概率。极端情况下，当输入空间和输出空间 大小相等时，哈希表就等价于数组了，可谓“大力出奇迹”。 另一方面，考虑通过优化哈希表的表示方式以缓解哈希冲突，常见的方法有「链式地址」和「开放寻址」。 6. 散列表 hello‑algo.com 90 6.2.1. 哈希表扩容 「负载因子 Load Factor」定义为 哈希表中元素数量除以桶槽数量（即数组大小），代表哈希冲突的严重程度。 为了提升操作效率，可以把「链表」转化为「AVL 树」或「红黑树」，将查询操作的时间复杂度优化至 ?(log ?) 。 6. 散列表 hello‑algo.com 91 6.2.3. 开放寻址 「开放寻址」不引入额外数据结构，而是通过“多次探测”来解决哈希冲突。根据探测方法的不同，主要分为 线性探测、平方探测、多次哈希。 线性探测 「线性探测」使用固定步长的线性查找来解决哈希冲突。 工业界方案 Java 采用「链式地址」。在 JDK 1.8 之后，HashMap 内数组长度大于 64 时，长度大于 8 的链 表会被转化为「红黑树」，以提升查找性能。 Python 采用「开放寻址」。字典 dict 使用伪随机数进行探测。 6.3. 小结 ‧ 向哈希表中输入一个键 key ，查询到值 value 的时间复杂度为 ?(1) ，非常高效。 ‧ 哈希表的常用操作包括查询、添加与删除键值对、遍历键值对等。

大小相等时，哈希表就等价于数组了，每个 key 都对应唯一的数组索引，可谓“大力出奇迹”。 另一方面，考虑通过优化哈希表的表示来缓解哈希冲突，常见的方法有「链式地址 Separate Chaining」和 「开放寻址 Open Addressing」。 6.2.1. 哈希表扩容 哈希函数的最后一步往往是对桶数量 ? 取余，以将哈希值映射到桶的索引范围，从而将 key 放入对应的桶中。 当哈希表容量越大（即 查询效率降低，因为需要线性遍历链表来查找对应元素； 为了提升操作效率，可以把「链表」转化为「AVL 树」或「红黑树」，将查询操作的时间复杂度优化至 ?(log ?) 。 6.2.3. 开放寻址 「开放寻址」不引入额外数据结构，而是通过“多次探测”来解决哈希冲突。根据探测方法的不同，主要分为 线性探测、平方探测、多次哈希。 线性探测 「线性探测」使用固定步长的线性查找来解决哈希冲突。 工业界方案 Java 采用「链式地址」。在 JDK 1.8 之后，HashMap 内数组长度大于 64 时，长度大于 8 的链 表会被转化为「红黑树」，以提升查找性能。 Python 采用「开放寻址」。字典 dict 使用伪随机数进行探测。 Golang 采用「链式地址」。Go 规定每个桶最多存储 8 个键值对，超出容量则连接一个溢出桶； 当溢出桶过多时，会执行一次特殊的等量扩容操作，以保证性能。

雜湊函式 hash collision 哈希冲突 雜湊衝突 load factor 负载因子 負載因子 separate chaining 链式地址 鏈結位址 open addressing 开放寻址 開放定址 linear probing 线性探测 線性探查 lazy deletion 懒删除 懶刪除 binary tree 二叉树 二元樹 tree node 树节点 樹節點 left‑child