哈希Hash也叫散列是算法中最核心的「空间换时间」思想之一核心目标是将查找操作的平均时间复杂度从 O (n) 降到 O (1)是牛客、LeetCode 笔试面试的高频考点。一、哈希的核心本质1. 传统查找的痛点数组按下标访问是 O (1)但按值查找需要遍历O (n)。链表无论按位置还是按值查找都需要遍历O (n)。很多场景下我们需要「快速判断一个元素是否存在、快速读取元素对应的值」这时候就需要哈希。2. 哈希的核心思路设计一个映射规则把要查找的「关键字 key」直接转换成数组的下标 index然后通过下标直接定位存储位置。公式化表达plaintext存储位置下标 hash(关键字 key)这样无论数据量多大理论上一次计算就能定位到目标位置平均查找效率为 O (1)。3. 最简单的哈希例子统计字符串中每个小写字母出现的次数cpp运行int cnt[26] {0}; for (char c : s) { cnt[c - a]; // c-a 就是最简单的哈希函数 }这里c - a把字符a~z映射成了数组下标0~25这就是最朴素的哈希思想。二、哈希函数哈希函数是哈希表的核心负责把任意类型的 key数字、字符串、结构体等转换成合法的数组下标。1. 优秀哈希函数的标准一致性相同的 key 必须得到完全相同的哈希值。均匀性哈希值尽可能均匀分布在数组空间中最大程度减少冲突。高效性计算速度快额外开销小。2. 常见的哈希函数构造方法直接定址法直接用 key 本身或其线性函数作为下标hash(key) key或hash(key) a * key b。适用场景key 取值范围小且连续比如统计 0~100 分的成绩分布。优点简单无冲突缺点适用范围极窄。除留余数法最通用、最常用公式hash(key) key % table_size其中table_size是哈希表的数组长度一般选取质数可以显著降低冲突概率。例子key1234table_size101哈希值为 1234 % 101 22。平方取中法先计算 key 的平方再取中间若干位作为哈希值。 适合 key 分布不均匀、位数不长的场景。字符串哈希字符串无法直接取模需要先转为数值。经典的 BKDR 哈希plaintexthash 0 遍历字符串每个字符 c: hash hash * base c 最后 hash hash % modbase 通常取 131、13131 等质数mod 取大质数减少冲突。三、哈希冲突碰撞1. 什么是哈希冲突不同的 key经过同一个哈希函数计算得到了相同的数组下标这就是哈希冲突。例table_size10key13 和 key23 取模后都等于 3两个元素想放在同一个位置就产生了冲突。冲突无法完全避免 —— 因为 key 的取值范围远大于数组下标范围。哈希表的优化方向就是降低冲突概率 高效解决冲突。2. 两大主流冲突解决方案方案一开放定址法闭散列核心思想冲突发生时在数组内部继续寻找下一个空位存放元素所有数据都存在数组里。最常见的是线性探测插入位置 index 被占用就依次检查 index1、index2… 直到找到空位。查找先算哈希值对比元素不匹配就往后找直到找到目标或遇到空位。缺点容易产生数据堆积连续一片位置被占满查找效率大幅下降。删除麻烦不能直接清空位置否则会打断查找链需要做「删除标记」伪删除。进阶优化二次探测步长按 1²、-1²、2²、-2²… 跳跃一定程度缓解堆积。方案二链地址法拉链法 / 开散列核心思想数组的每个位置是一个链表或其他结构所有哈希值相同的元素都挂在对应位置的链表上。结构说明哈希表本质是一个「指针数组」每个元素是对应哈希桶的链表头。插入算哈希值插入到对应链表中。查找算哈希值遍历对应链表匹配。删除算哈希值在链表中删除节点。优点不会产生数据堆积冲突处理简单。删除元素方便空间灵活。适合数据量不确定、元素较多的场景。C STL 中的unordered_map/unordered_set底层就是链地址法实现当单个链表长度超过阈值8时会自动转为红黑树进一步保证查找效率。四、负载因子与扩容1. 负载因子Load Factor公式plaintext负载因子 α 哈希表中元素总数 / 哈希表数组长度α 越大表越满冲突概率越高查找效率越低。α 越小冲突越少但空间浪费越严重。工业界通用阈值0.75。当负载因子超过 0.75 时哈希表会触发扩容。2. 扩容Rehash扩容一般将数组长度扩大到原来的 2 倍或下一个更大的质数然后把所有元素重新计算哈希值迁移到新数组中。 这个过程叫 rehash开销较大因此是低频操作。五、C 中的哈希容器STL 中基于哈希实现的常用容器与红黑树容器对比如下表格容器用途底层结构平均时间复杂度有序性unordered_set存 key用于去重、存在性判断哈希表链地址法O(1)无序unordered_map存 key-value 键值对用于计数、映射哈希表链地址法O(1)无序set存 key有序去重红黑树O(logn)升序有序map存 key-value有序映射红黑树O(logn)升序有序选型原则只需要快速查找、计数不需要有序 → 用unordered_系列哈希需要有序遍历、范围查找、按序输出 → 用set/map红黑树六、算法题中哈希的经典应用场景结合牛客常考题型哈希主要解决四类问题1. 计数统计典型题统计字符 / 数字出现次数、找出现次数最多的元素、第一个只出现一次的字符。cpp运行// 统计字符串字符出现次数 unordered_mapchar, int cnt; for (char c : s) cnt[c];2. 存在性判断 / 去重典型题数组中是否有重复元素、扑克牌顺子判重。 以「扑克牌顺子」为例哈希版本可以替代排序用 set 存储非 0 牌遇到重复直接返回 false记录非 0 牌的最大值和最小值若max - min 5即可构成顺子3. 互补查找两数之和类经典题两数之和。 暴力解法 O (n²)用哈希表存储已遍历过的数每次查询target - nums[i]是否存在整体 O (n) 解决。4. 字符串匹配类典型题字母异位词判断、字符串中所有变位词。 用哈希统计两个字符串的字符频次频次一致即为异位词。七、哈希思想的优缺点优点查找、插入、删除的平均时间复杂度均为 O (1)效率极高。缺点存在冲突极端最坏情况会退化到 O (n)。元素无序不支持范围查找、有序遍历。有额外的空间开销。谢谢
哈希Hash也叫散列是算法中最核心的「空间换时间」思想之一核心目标是将查找操作的平均时间复杂度从 O (n) 降到 O (1)是牛客、LeetCode 笔试面试的高频考点。一、哈希的核心本质1. 传统查找的痛点数组按下标访问是 O (1)但按值查找需要遍历O (n)。链表无论按位置还是按值查找都需要遍历O (n)。很多场景下我们需要「快速判断一个元素是否存在、快速读取元素对应的值」这时候就需要哈希。2. 哈希的核心思路设计一个映射规则把要查找的「关键字 key」直接转换成数组的下标 index然后通过下标直接定位存储位置。公式化表达plaintext存储位置下标 hash(关键字 key)这样无论数据量多大理论上一次计算就能定位到目标位置平均查找效率为 O (1)。3. 最简单的哈希例子统计字符串中每个小写字母出现的次数cpp运行int cnt[26] {0}; for (char c : s) { cnt[c - a]; // c-a 就是最简单的哈希函数 }这里c - a把字符a~z映射成了数组下标0~25这就是最朴素的哈希思想。二、哈希函数哈希函数是哈希表的核心负责把任意类型的 key数字、字符串、结构体等转换成合法的数组下标。1. 优秀哈希函数的标准一致性相同的 key 必须得到完全相同的哈希值。均匀性哈希值尽可能均匀分布在数组空间中最大程度减少冲突。高效性计算速度快额外开销小。2. 常见的哈希函数构造方法直接定址法直接用 key 本身或其线性函数作为下标hash(key) key或hash(key) a * key b。适用场景key 取值范围小且连续比如统计 0~100 分的成绩分布。优点简单无冲突缺点适用范围极窄。除留余数法最通用、最常用公式hash(key) key % table_size其中table_size是哈希表的数组长度一般选取质数可以显著降低冲突概率。例子key1234table_size101哈希值为 1234 % 101 22。平方取中法先计算 key 的平方再取中间若干位作为哈希值。 适合 key 分布不均匀、位数不长的场景。字符串哈希字符串无法直接取模需要先转为数值。经典的 BKDR 哈希plaintexthash 0 遍历字符串每个字符 c: hash hash * base c 最后 hash hash % modbase 通常取 131、13131 等质数mod 取大质数减少冲突。三、哈希冲突碰撞1. 什么是哈希冲突不同的 key经过同一个哈希函数计算得到了相同的数组下标这就是哈希冲突。例table_size10key13 和 key23 取模后都等于 3两个元素想放在同一个位置就产生了冲突。冲突无法完全避免 —— 因为 key 的取值范围远大于数组下标范围。哈希表的优化方向就是降低冲突概率 高效解决冲突。2. 两大主流冲突解决方案方案一开放定址法闭散列核心思想冲突发生时在数组内部继续寻找下一个空位存放元素所有数据都存在数组里。最常见的是线性探测插入位置 index 被占用就依次检查 index1、index2… 直到找到空位。查找先算哈希值对比元素不匹配就往后找直到找到目标或遇到空位。缺点容易产生数据堆积连续一片位置被占满查找效率大幅下降。删除麻烦不能直接清空位置否则会打断查找链需要做「删除标记」伪删除。进阶优化二次探测步长按 1²、-1²、2²、-2²… 跳跃一定程度缓解堆积。方案二链地址法拉链法 / 开散列核心思想数组的每个位置是一个链表或其他结构所有哈希值相同的元素都挂在对应位置的链表上。结构说明哈希表本质是一个「指针数组」每个元素是对应哈希桶的链表头。插入算哈希值插入到对应链表中。查找算哈希值遍历对应链表匹配。删除算哈希值在链表中删除节点。优点不会产生数据堆积冲突处理简单。删除元素方便空间灵活。适合数据量不确定、元素较多的场景。C STL 中的unordered_map/unordered_set底层就是链地址法实现当单个链表长度超过阈值8时会自动转为红黑树进一步保证查找效率。四、负载因子与扩容1. 负载因子Load Factor公式plaintext负载因子 α 哈希表中元素总数 / 哈希表数组长度α 越大表越满冲突概率越高查找效率越低。α 越小冲突越少但空间浪费越严重。工业界通用阈值0.75。当负载因子超过 0.75 时哈希表会触发扩容。2. 扩容Rehash扩容一般将数组长度扩大到原来的 2 倍或下一个更大的质数然后把所有元素重新计算哈希值迁移到新数组中。 这个过程叫 rehash开销较大因此是低频操作。五、C 中的哈希容器STL 中基于哈希实现的常用容器与红黑树容器对比如下表格容器用途底层结构平均时间复杂度有序性unordered_set存 key用于去重、存在性判断哈希表链地址法O(1)无序unordered_map存 key-value 键值对用于计数、映射哈希表链地址法O(1)无序set存 key有序去重红黑树O(logn)升序有序map存 key-value有序映射红黑树O(logn)升序有序选型原则只需要快速查找、计数不需要有序 → 用unordered_系列哈希需要有序遍历、范围查找、按序输出 → 用set/map红黑树六、算法题中哈希的经典应用场景结合牛客常考题型哈希主要解决四类问题1. 计数统计典型题统计字符 / 数字出现次数、找出现次数最多的元素、第一个只出现一次的字符。cpp运行// 统计字符串字符出现次数 unordered_mapchar, int cnt; for (char c : s) cnt[c];2. 存在性判断 / 去重典型题数组中是否有重复元素、扑克牌顺子判重。 以「扑克牌顺子」为例哈希版本可以替代排序用 set 存储非 0 牌遇到重复直接返回 false记录非 0 牌的最大值和最小值若max - min 5即可构成顺子3. 互补查找两数之和类经典题两数之和。 暴力解法 O (n²)用哈希表存储已遍历过的数每次查询target - nums[i]是否存在整体 O (n) 解决。4. 字符串匹配类典型题字母异位词判断、字符串中所有变位词。 用哈希统计两个字符串的字符频次频次一致即为异位词。七、哈希思想的优缺点优点查找、插入、删除的平均时间复杂度均为 O (1)效率极高。缺点存在冲突极端最坏情况会退化到 O (n)。元素无序不支持范围查找、有序遍历。有额外的空间开销。谢谢
双梁正问题 【 torch 实战】（Python代码实现）)
