1. 什么是哈希表哈希表Hash Table是一种通过键值映射存储数据的数据结构。它的核心思想是通过一个哈希函数把任意数据映射到一个有限范围的位置从而实现快速查找。例如我们想存储学生编号到姓名的映射学生编号 - 姓名 1001 - 张三 1002 - 李四 1003 - 王五如果使用数组我们需要声明name[1003]这样的数组。但如果编号很大比如1000000000数组就无法开这么大空间。于是使用哈希函数1000000000 | v 哈希函数 | v 数组下标例如使用取模运算index key % 1000;那么1000000000 % 1000 0数据就存到hash[0]的位置。2. 哈希表的核心组成一个哈希表包含三个核心部分① 哈希函数作用把 key 转换成数组下标。例如int hash(int key) { return key % 1000; }当key 12345时12345 % 1000 345数据就存到table[345]。② 哈希数组真正存储数据的位置。int hash[1000];③ 冲突处理这是哈希表最重要的问题。3. 哈希冲突什么叫冲突例如哈希函数key % 10两个数据15和25计算15 % 10 5 25 % 10 5两个数据都想放到hash[5]的位置这就产生了哈希冲突。4. 解决哈希冲突的方法方法1开放寻址法竞赛常用思想如果当前位置被占用就继续往后找空位置。例如先存15位置是5hash[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] ↑ 15再存25位置也是5发现有人往后找到6hash[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] ↑ ↑ 15 25代码实现while (hash[pos] ! 0) { pos; } hash[pos] value;方法2链地址法工程常用每个位置挂一个链表冲突的元素都放在同一个链表中。例如hash[5] → 15 → 25 → 35Java 中的HashMap早期就是采用这种思想。5. C语言实现哈希表存整数示例判断一个数字是否出现过int hash[100000]; // 插入 hash[x] 1; // 查询 if (hash[x]) { printf(出现过); }这是最简单的哈希表应用。6. 哈希表常见应用应用1判断重复元素题目给数组[1, 3, 5, 3]找重复元素。暴力解法两层循环时间复杂度O(n²)。哈希解法记录出现次数。遍历过程 1 → hash[1] 1 3 → hash[3] 1 5 → hash[5] 1 3 → hash[3] 2发现重复时间复杂度O(n)。应用2统计次数频率统计例如统计单词出现次数apple banana apple哈希统计apple → 2 banana → 1代码map[key]常见场景字符出现次数数字出现次数投票统计应用3两数之和经典问题数组[2, 7, 11, 15]目标值9。暴力解法枚举两个数时间复杂度O(n²)。哈希解法遍历过程 当前值2需要9-27哈希中没有7存入2 当前值7需要9-72哈希中有2找到答案27时间复杂度O(n)。应用4坐标哈希二维坐标(x, y)不能直接开大数组a[200000][200000]。转换方法x * 1000000 y例如(10, 20) → 10000020存到hash[10000020]应用场景棋盘问题地图问题二维点集合稀疏矩阵应用5字符串哈希将字符串转换成数字。例如hello转换成哈希值。用于判断字符串是否相同快速匹配字符串查找字符串哈希可以在O(1)时间内比较两个字符串是否相等。应用6前缀和 哈希经典问题和为0的最长子数组。例如数组[1, -1, 2, -2]前缀和[1, 0, 2, 0]如果两个前缀和相同中间区间和就为0。哈希记录前缀和第一次出现的位置。应用7离散化有时候数字很大1000000000但是数量很少。例如[100, 500000, 999999999]不用开这么大数组排序后映射100 → 1 500000 → 2 999999999 → 3这叫做离散化本质也是一种映射思想。7. 哈希表和数组区别数组哈希表访问O(1)平均 O(1)空间连续不连续范围要求小可以很大下标整数任意 key查找需要知道位置通过 key 找8. 哈希表优缺点优点快平均时间复杂度O(1)灵活key 可以是数字、字符串、坐标、对象等缺点冲突必须处理无序不能保证插入顺序最坏情况如果大量冲突可能退化到O(n)9. 算法题什么时候想到哈希看到这些关键词① 快速判断是否存在例如是否出现过想到哈希集合② 统计次数例如出现次数最多的数字想到map[key]③ 两个集合匹配例如找对应关系想到key → value④ 坐标很大但是点很少例如x, y ≤ 1e9点 ≤ 2e5想到坐标哈希⑤ 暴力枚举两个元素例如O(n²)优化为O(n)想到哈希查找另一个元素10. 一句话总结哈希表的本质就是利用一个映射函数把复杂的数据映射到一个小范围从而实现快速查找。算法题中最常见的三个方向查存在性set统计次数map[key]二维坐标/大范围数据压缩(x, y) → key国际象棋马的问题就是典型的二维坐标哈希 反向枚举候选点这类题在竞赛里非常常见。 哈希表（Hash Table）知识总结：从原理到实战应用
1. 什么是哈希表哈希表Hash Table是一种通过键值映射存储数据的数据结构。它的核心思想是通过一个哈希函数把任意数据映射到一个有限范围的位置从而实现快速查找。例如我们想存储学生编号到姓名的映射学生编号 - 姓名 1001 - 张三 1002 - 李四 1003 - 王五如果使用数组我们需要声明name[1003]这样的数组。但如果编号很大比如1000000000数组就无法开这么大空间。于是使用哈希函数1000000000 | v 哈希函数 | v 数组下标例如使用取模运算index key % 1000;那么1000000000 % 1000 0数据就存到hash[0]的位置。2. 哈希表的核心组成一个哈希表包含三个核心部分① 哈希函数作用把 key 转换成数组下标。例如int hash(int key) { return key % 1000; }当key 12345时12345 % 1000 345数据就存到table[345]。② 哈希数组真正存储数据的位置。int hash[1000];③ 冲突处理这是哈希表最重要的问题。3. 哈希冲突什么叫冲突例如哈希函数key % 10两个数据15和25计算15 % 10 5 25 % 10 5两个数据都想放到hash[5]的位置这就产生了哈希冲突。4. 解决哈希冲突的方法方法1开放寻址法竞赛常用思想如果当前位置被占用就继续往后找空位置。例如先存15位置是5hash[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] ↑ 15再存25位置也是5发现有人往后找到6hash[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] ↑ ↑ 15 25代码实现while (hash[pos] ! 0) { pos; } hash[pos] value;方法2链地址法工程常用每个位置挂一个链表冲突的元素都放在同一个链表中。例如hash[5] → 15 → 25 → 35Java 中的HashMap早期就是采用这种思想。5. C语言实现哈希表存整数示例判断一个数字是否出现过int hash[100000]; // 插入 hash[x] 1; // 查询 if (hash[x]) { printf(出现过); }这是最简单的哈希表应用。6. 哈希表常见应用应用1判断重复元素题目给数组[1, 3, 5, 3]找重复元素。暴力解法两层循环时间复杂度O(n²)。哈希解法记录出现次数。遍历过程 1 → hash[1] 1 3 → hash[3] 1 5 → hash[5] 1 3 → hash[3] 2发现重复时间复杂度O(n)。应用2统计次数频率统计例如统计单词出现次数apple banana apple哈希统计apple → 2 banana → 1代码map[key]常见场景字符出现次数数字出现次数投票统计应用3两数之和经典问题数组[2, 7, 11, 15]目标值9。暴力解法枚举两个数时间复杂度O(n²)。哈希解法遍历过程 当前值2需要9-27哈希中没有7存入2 当前值7需要9-72哈希中有2找到答案27时间复杂度O(n)。应用4坐标哈希二维坐标(x, y)不能直接开大数组a[200000][200000]。转换方法x * 1000000 y例如(10, 20) → 10000020存到hash[10000020]应用场景棋盘问题地图问题二维点集合稀疏矩阵应用5字符串哈希将字符串转换成数字。例如hello转换成哈希值。用于判断字符串是否相同快速匹配字符串查找字符串哈希可以在O(1)时间内比较两个字符串是否相等。应用6前缀和 哈希经典问题和为0的最长子数组。例如数组[1, -1, 2, -2]前缀和[1, 0, 2, 0]如果两个前缀和相同中间区间和就为0。哈希记录前缀和第一次出现的位置。应用7离散化有时候数字很大1000000000但是数量很少。例如[100, 500000, 999999999]不用开这么大数组排序后映射100 → 1 500000 → 2 999999999 → 3这叫做离散化本质也是一种映射思想。7. 哈希表和数组区别数组哈希表访问O(1)平均 O(1)空间连续不连续范围要求小可以很大下标整数任意 key查找需要知道位置通过 key 找8. 哈希表优缺点优点快平均时间复杂度O(1)灵活key 可以是数字、字符串、坐标、对象等缺点冲突必须处理无序不能保证插入顺序最坏情况如果大量冲突可能退化到O(n)9. 算法题什么时候想到哈希看到这些关键词① 快速判断是否存在例如是否出现过想到哈希集合② 统计次数例如出现次数最多的数字想到map[key]③ 两个集合匹配例如找对应关系想到key → value④ 坐标很大但是点很少例如x, y ≤ 1e9点 ≤ 2e5想到坐标哈希⑤ 暴力枚举两个元素例如O(n²)优化为O(n)想到哈希查找另一个元素10. 一句话总结哈希表的本质就是利用一个映射函数把复杂的数据映射到一个小范围从而实现快速查找。算法题中最常见的三个方向查存在性set统计次数map[key]二维坐标/大范围数据压缩(x, y) → key国际象棋马的问题就是典型的二维坐标哈希 反向枚举候选点这类题在竞赛里非常常见。