一文带你快速入门【哈希表】

2022 年 9 月 18 日
浙江
本文字数：3507 字
阅读完需：约 12 分钟

最近开始学习哈希表，为此特写一遍文章介绍一下哈希表，带大家快速入门哈希表:mortar_board:

@[TOC](数据结构 —— 哈希表)

一、什么是哈希表？

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值==映射==到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做==散列函数==，存放记录的数组叫做散列表。来源百度百科

不过看了这么一段，也不是很清楚什么是哈希表，简单点用一句话来说

哈希表是根据关键码的值而直接进行访问的数据结构:wave:

但我和身边的朋友讲了这么一句话，但是他还是不太理解，那我便又说

直白来讲其实数组就是一张哈希表，就如下图所示

二、怎么实现哈希表？需要注意什么？

对于哈希表，最多的就是去一堆数据中寻找那一两个数据，比方说在学生信息管理系统中查找一个学生的信息，就需要通过索引值去寻找，但是如何搭建它们之间的桥梁:bridge:呢？这时我们就需要用到哈希函数了（hash function），将学生的学号映射到哈希表上

1、哈希函数

哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数百度百科

通过哈希函数，把学生的学号直接映射为哈希表上的索引，然后通过此索引下标就可以快速知道这位同学是否在这所学校:school:里了
这里的 Key 值和 Value 值叫做==键值对==，在 JDK 中有专业叫法叫做 Entry，这个我在C++STL【容器】详解中的有做过详细介绍，大家可以去看看
对于哈希函数的内部实现，它是基于一种叫哈希码（HashCode）的编码，把学号转换为数值，它的原理是【通过特定编码方式，可以将其他数据格式转化为不同的数值】，这样就把学生名字映射为哈希表上的索引数字了
最后通过这个索引值，找到了 Key 值所对应的 Value 值，也就显示出了小明在学生管理系统中的基本信息
以下是具体映射结构原理图:point_down:

2、哈希碰撞（哈希冲突）

说到哈希表，那除了哈希函数一定要讲哈希碰撞，因为如果哈希函数设计的不是很好，就会经常出现哈希碰撞的现象，这么说说不太形象，大概是这么个碰撞:point_down:

可以看出，此哈希表中还是存在蛮严重的哈希碰撞，有两个学生或三个学生都对应这同一个索引值，当然这只是为了讲解而画的假设，现实编程中如果设计的不严谨确实可能会出现这样的情况，那如何去解决这一碰撞呢？接下来介绍两种常见的方法

方法一：拉链法

所谓拉链法，==字面意思==就是将冲突的数据拉开，“链”就是【链表】的意思，将指向索引 1 的第一个学生的键值之后再设计一个 next 指针，指向下一个学生也是指向索引 1 的键值，这就形成了一个链表的形状，具体看下图即可:point_down:

方法二：线性探测法

何所谓线性探测法，也就是成一个线状的趋势去探测，是否有==下一个空位置==给冲突的数据暂时存放，如果表中有空位子，就不用将他们一定要挤在一起形成一个链状了，因为链表太长是会浪费空间的，

讲得通俗一点，也就是你去一个食堂打菜，大家都喜欢在 5 号窗口打菜，可能是因为这个阿姨手不抖，但旁边的 4 号窗却只有两三人而已，有时候也会出现空位，那为什么一定要把队伍排得那么长呢，饭有的吃就不错了，万一那个阿姨手也不抖呢，何不去尝试一下:heart_eyes_cat:

一样，也以图的形式展示给大家，这里要注意，只能往后找，不能往前找，可以看出下标 0 位置是空着的

三、有哪些哈希结构？

常见的三种哈希结构

数组
set
map

数组没什么好说的，我们主要来说一说 set 和 map，均以表格的形式呈现:clipboard:

1、set

我们可以看到 unordered_set 它是无序的，但是 set 和 multiset 确实有序的，这个我在C++STL【容器】详解中也做过介绍:pencil2:，因为它们和 map 一样，底层实现都是红黑树，即所谓的平衡二叉搜索树，所以其 key 值是有序的，但不可以修改，否则会导致整棵树的错乱，所以只能删除和增加

2、map

四、哈希表有哪些优势和劣势？

1、优势（advantage）

如果你需要在 1-10 这 10 个数中寻找 5 很容器，但是让你在 1-4,294,967,296 中找一个数却很是困难，但是哈希表可以做到，加入你用枚举去实现的话，时间复杂度可能要**O(n)，但是如果用哈希表去实现的话，时间复杂度却只需要 O(1)**，大家说是不是更加优化了呢。其实现的原理便是==快速判断一个元素是否出现集合里==

2、劣势（disadvantage）

哈希表它虽然查找很快，但是它的空间复杂度却不低，因为需要用 set 或 map 来存放数据，才能实现快速的查找，换句话来说就是牺牲了:scissors:空间换取了时间

五、在实际问题中怎么解决有关哈希表的问题？

1、干货讲解

什么时候用哈希表呢？【当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法，因其可以快速判断一个元素是否出现集合里】

教大家一个小秘诀，在实际的问题中，如果您碰到了使用集合解决哈希问题的时候，优先使用==unordered_set==，因其查、增删的效率是最高的；如果集合是有序的，那就使用==set==；不仅是有序而且要重复数据的话，那就使用==multiset==

那么再来看一下 map ，map 是一个 key value 的数据结构，map 中，对 key 是有限制，我们从上表中也可以看出对 value 没有限制的，因为 key 的存储方式使用红黑树实现的，所以在做题的时候如果遇到需要使用 key value 结构来对应寻找数据时，就可以使用 map 相关的哈希表结构

之前有讲过一道题电话号码的字母组合，就是用 map 去存储每个数字所对应的字符串，这样就可以根据具体的数字去迅速对应到与之相对应的数据了，但是 set 集合却做不到这个，因为 set 里面放的元素只能是一个 key 值，当需要两数据相对应时就不要使用 set 了,使用 map 更为合适，但是选择==map==、==multimap==还是==unordered_map==呢，这就需要大家自己思考并根据实际题目看 key 值是否有序还是无序了

虽然我们没有讲数组，但设计哈希表的题目中利用数组解题的还是有，因为使用数组就不需要利用哈希映射了，这样便可以节省空间复杂度，一般数组用在数据量较小的题目中

2、具体题目简述

光说不练假把式，我们到具体题目中看个两题感受一下:card_index:

第一题

看题，求两个数组的交集，很明显这是两个集合，而且没有所谓的 key value 接口果断选择效率最高的 unordered_set，但是看下面的数据量并不是成千上亿那么大:raised_hands:，所以这题用数组其实更为合适，具体思路不做讲解，后续会更新，给一下代码

 vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {     unordered_set<int> result;     unordered_set<int> num(nums1.begin(),nums1.end());    //把nums1中数放入num集合
     //遍历nums2数组，与num集合做比较     for(int i : nums2)     {         if(num.find(i) != num.end())             //没有到num的结尾就发现了异常情况             result.insert(i);   //将交集元素放入result集合     }     //最后以一个vector容器的形式返回     return vector<int>(result.begin(),result.end()); }

复制代码

第二题

这是力扣的第一题，相信大家都做过，不知你是否试过用哈希表来做呢，看题，很明显，这是一个==key value 结构==，求出两个目标整数相加为目标数 target，返回这两个数所对应的下标，所以我们应该使用 map，看示例，并不是有序的，因此果断选择 unordered_map，相信很多小伙伴之前都是用的暴力枚举，采用数组的形式来解出这道题的，但是我们通过观察这道题的数据，是不是很大，10^4^，10^9^，所以时间复杂度直奔 O(n^2^)，哈希表就是题目最下方的进阶做法，**时间复杂度为 O(n)，空间复杂度也为 O(n)**，因为需要额外的数组来存放数据。一样不做细接，只给代码

 vector<int> twoSum(vector<int>& nums, int target) {     std::unordered_map <int,int> map;     for(int i = 0; i < nums.size(); i++) {         // 遍历当前元素，并在map中寻找是否有匹配的key         auto iter = map.find(target - nums[i]);          if(iter != map.end()) {             return {iter->second, i};         }         // 如果没找到匹配对，就把访问过的元素和下标加入到map中         map.insert(pair<int, int>(nums[i], i));      }     return {}; }