551-哈希表的理论讲解

- 日理万妓 2022-09-11 04:22 58阅读 0赞

## 哈希表的定义 ##

![在这里插入图片描述][728edbec0e6a4799bfc0670698dbd618.png]  
**哈希表增删查效率非常高，趋近于O(1)**  
**没有办法达到绝对的O(1)**  
**哈希表什么时候用到？在进行大量的查询时会用到，只要是有速度快的查询的需求，都会想到哈希表**

我们想让这一组数据的查询的时间复杂度是O(1)

![在这里插入图片描述][07269260b8c241268b6d7e1e76c710ce.png]  
不管是存到链表还是数组里面，都是线性的查找，从第一个元素开始查，查一个比较一个，时间复杂度都是O(n)  
**最快的方法是**提供一张表，还是数组， 我们在存的时候，并不是挨个存储，而是元素值的本身作为下标存到数组相应的位置

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
我们把数组的每个位置初始化为-1的值。然后把1,2，3,4，5,6，7,8分别存储在数组下标1,2，3,4，5,6，7，8的地方。  
如果是这样存储的话，可能会浪费一些空间。比如说0号位置和7号位置的空间浪费了。这没有关系，关键是它可以提供一个时间复杂度是O(1)的查找的算法。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
比如说，我现在要查找一个值为3的元素。我直接拿val这个值作为数组的下标去访问 ，如果值是-1，则这个元素3在数组中不存在，如果值不为-1，则3找到了。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
**元素的值通过一个映射关系（映射函数）找到元素在表中的存储位置**  
**这张表就称为散列表（哈希表）**  
![在这里插入图片描述][620ad536f82a4239841892f14d0e301e.png]  
**但是，上面的方式存储，空间会浪费，比如说是下面这些数字：**  
![在这里插入图片描述][0e002613c8c04229a80679d8e45e5bc4.png]  
**如果还是用刚才的映射关系，岂不是要开辟1000003个位置的内存空间？**  
**只有4个位置存储有效元素，其他的那么多的空间位置都浪费了！**

**在实际的过程中，我们应该为了节省内存空间，找一个合适的映射关系！**

## 常见的映射方法 ##

![在这里插入图片描述][7425b6c295e0465cb54b7af4639e2cc9.png]

常见的是**除留余数法**

假设我们有这么一组数据：  
![在这里插入图片描述][a844f8f9ae884f1099166f2604e92534.png]

我们定义7个位置大小的数组空间。  
**元素的值作为输入参数，通过哈希函数处理之后，得到一个输出的值，就是在表中的存储位置，这个表就叫做哈希表或者散列表。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
数组的每个位置都初始化为空  
我们存储12的话怎么存？除留余数法，余上一个哈希表的长度  
![在这里插入图片描述][5625c3e9e30a497c8e602e92ee93713a.png]  
12就存在下标为5的位置。下标为5的位置是空的，所以把12存进去。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
我们接下来要存储18  
![在这里插入图片描述][c2addf565c8a412d8d5a54e941068f64.png]  
把18这个元素存储在哈希表下标为4的位置  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
我们接下来存储27  
![在这里插入图片描述][50ab7264296a48c8920eaec1e329bd1c.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
我们接下来存储24  
![在这里插入图片描述][3ac45e7074a7495b9bce4898e26585a4.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
我们接下来存储33  
![在这里插入图片描述][c3ceee343ff14962b06c758c15be9780.png]  
33存储的位置是哈希表下标为5的位置。但是现在哈希表下标为5的位置存储的是12，已经被占用了，而且数组下标这里就这一个位置，这种现象是产生哈希冲突（哈希碰撞）了，怎么办？  
不管选择什么样的哈希函数，都会产生哈希冲突，是无法避免的，只能尽量减小哈希冲突产生的概率。  
不同元素模上一个7很有可能得到的结果是相同的

## 解决哈希冲突的方案是什么？ ##

![在这里插入图片描述][1922487c120f414b8df268333af98b19.png]  
unordered\_set和unordered\_map底层是用链式哈希表实现的，用**链地址法**解决哈希冲突

**线性探测法：**  
就是往后继续探测，有空闲的位置就存放。  
33经过除留余数法被分到哈希表的5号位置，但是5号位置已经有元素占着了，就把33往后走，找一个空闲的位置存放33  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]

假如我们现在要存储45，![在这里插入图片描述][a5c2c392e1d74444b33a68a99112047b.png]  
但是3号位置也有元素占用了，往后走，后面的位置都有元素占着了，然后转回首地址往后走，发现1号位置空闲，就把45放到1号位置。（几乎是把数组遍历了一遍了----哈希冲突导致哈希表在存储元素的时候变慢了）  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]  
**变得有多慢呢？？？**  
我们把一个元素按照哈希函数处理之后，放在某一个位置，这个处理是个常量的时间，哈希表在增加元素，时间复杂度是O(1)的，但是由于产生了哈希冲突，如果是用线性探测法，往后找空闲的位置，基本上是把整个哈希表数组遍历了，所以，哈希冲突越多，增加的元素的时间复杂度就从O(1)慢慢的变到了O(n)  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]  
**现在我们要查询了**  
比如说，我们查询18，![在这里插入图片描述][9eebcb3f0995450db045766c373c8366.png]  
18进行哈希函数（除留余数法）得出是4，然后访问4号位置，是18，就查到了  
为了在哈希表找18，先执行了一次哈希函数采用的除留余数法，是常量时间，然后进行哈希表数组的下标访问，也是一个常量时间 ![在这里插入图片描述][8eb55560de0b4ffe909ce81c860a9dba.png]  
但是同样的，因为哈希冲突的存在，比如我要查45，先进行哈希函数的除留余数法，得出3，访问3号位置，发现3号位置上的元素是24而不是45，肯定当时往哈希表放45的时候已经产生哈希冲突了，所以45并没有在3号位置上放，我们还得知道这个哈希表解决哈希冲突的方案是什么：是线性探测法  
就和环形队列一样，往后遍历，然后走环，最终在1号位置上找到了45，因为哈希冲突及线性探测法的存在，导致搜索的时间复杂度从O(1)–>O(n)

哈希表的删除元素的时间复杂度也是O(1),我们删除18，通过哈希表的除留余数法，得到4,4号位置就是18，所以就直接把18干掉了O(1)的操作  
但是，如果我们要删除45，通过哈希表的除留余数法，得到3,发现3号位置不是45， 得知原来在插入45的时候产生了哈希冲突了，因为是线性探测法解决哈希冲突，又是环形的遍历，然后查到1号位置的元素是45，然后把45删掉。 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]  
**在寻找45的时候发生了哈希冲突，导致删除的时间复杂度从O(1)–>O(n)**  
当我们在哈希表存放的元素越来越多，哈希冲突的发生概率也就越来越大  
在增删查的时间复杂度从O(1)—>O(n)  
**实际上，我们会在多种情况下去优化，去降低哈希冲突的概率，但是是不能杜绝的。**

## 降低哈希冲突的概率 ##

**方法1：我们在哈希函数上去想办法：**  
对于除留余数法来说，我们希望通过模上一个哈希表的长度后， 尽量产生的结果是离散的，而不是经常产生相同值导致哈希冲突 我们尽量让哈希表的长度（哈希桶的长度）**：取素数，只有1和自己能被整除，这样通除留余数产生的结果相同的概率就很低了**  
在C++的容器里，有专门定义一张素数表，在进行扩容的时候，采用的哈希函数是除留余数法的话，会采用素数 ，把所有的素数都枚举了一下  
哈希表在扩容的时候，取的下一个长度就是在素数表里面的下一个素数

**方法2**：**哈希表的装载因子 loadfactor**  
装载因子：以占用位置（桶）的个数除以桶的总个数。  
Java中或者C++链式哈希表实现的容器或者集合，装载因子值取的默认值是0.75或者四分之三

![在这里插入图片描述][e8ab6ebfc55b4b37ae32fe6f08e2c030.png]

如果已占用桶的个数占到总的桶个数的四分之三的话，我们就说，此时这个哈希表放的元素已经比较多了，再继续放元素，产生的哈希冲突的概率就大 ，进而导致哈希表的增删查的时间复杂度变大，效率越来越低了。  
此时如果是下面这个情况，哈希表就需要扩容了：  
![在这里插入图片描述][eef140a495ea4882b07326ddfa1e7ce8.png]  
哈希表扩容以后，相当于数组的扩容，造价还是很大的，需要开辟更大长度的空间，采用素数的长度开辟更长的哈希表。  
这时候，原来的元素就要放在新的哈希表里面了。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]  
如果这个21原来放在旧的哈希表是0号位置，那么它在新的哈希表存放的也是一定在0号位置吗？  
这个当然是不能确定的。  
比如说当时哈希表的桶的个数是7，扩容之后，新的哈希表的桶的个数是23，那么除留余数法的模的数就不一样了，得到的值就不一定和原来一样了。  
所以，对于哈希表的扩容来说，造价还是挺大的  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16]  
**扩容的时间复杂度是O(n)**

**哈希表的增删查时间复杂度：**  
![在这里插入图片描述][3fa9081194094792a39a630db60af5c3.png]  
因为并不是每次增加哈希表的元素都会触发哈希表的扩容，可能在第n次才触发到。

![在这里插入图片描述][258696cfccda479b856452b3581ef092.png]  
包括之间的vector的扩容，末尾元素增加，本身是O(1)，但是如果末尾元素增加没有空间了， 导致数组需要先扩容了，扩容的话就是O(n)，但是并不是每次末尾元素增加都会导致扩容啊，所以vector的末尾元素的增加的均摊时间复杂度是O(1)

[728edbec0e6a4799bfc0670698dbd618.png]: /images/20220828/c5054039c3a34c29a1cb1327549d955a.png
[07269260b8c241268b6d7e1e76c710ce.png]: /images/20220828/dff18ceaf4054746bb51befa8344d9f8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c01a03e6add8493ea0342e16d0764c6d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/e09d7e5e3dc9492d92f8743b6b60889a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/c392c52f826848efb12802df2fb61cca.png
[620ad536f82a4239841892f14d0e301e.png]: /images/20220828/7bd1103d1b6b401fbb3c7b827f103a1f.png
[0e002613c8c04229a80679d8e45e5bc4.png]: /images/20220828/a2ef7fc020fb44438d5eb3c0789dd92a.png
[7425b6c295e0465cb54b7af4639e2cc9.png]: /images/20220828/032ea38e7aa649b193aea5bae815bdc1.png
[a844f8f9ae884f1099166f2604e92534.png]: /images/20220828/5ebbaf88be5a44e18612289c442d9761.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/2d238d3ad76f4c5389f067d7cd8ddd19.png
[5625c3e9e30a497c8e602e92ee93713a.png]: /images/20220828/45f6e587057d4b3e9eb140def1d4f545.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/b96524d12ccd4491921122fe5a53e6c1.png
[c2addf565c8a412d8d5a54e941068f64.png]: /images/20220828/0ad32311d8c14234933cd3c9e66568f5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/75c9d1772c894a28b3523d19d6c2ac07.png
[50ab7264296a48c8920eaec1e329bd1c.png]: /images/20220828/4a280ae030ed48e59ed5188a6d4f7668.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/5919a09ed14546c997b14a4f6f53c07a.png
[3ac45e7074a7495b9bce4898e26585a4.png]: /images/20220828/7d7cf077230b4c42be8e07b607f39077.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/1505544984d84a06b44a7fe9e1614770.png
[c3ceee343ff14962b06c758c15be9780.png]: /images/20220828/41546298ad154476abbdf5a3182635fc.png
[1922487c120f414b8df268333af98b19.png]: /images/20220828/d70edea0296e403a8b69a69523b6b4fc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/576a6107751c4ed081a077456ac034d3.png
[a5c2c392e1d74444b33a68a99112047b.png]: /images/20220828/8e99401860ec47358a9b092eea0d91bb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/9de08788d44f42738d837ed1edb4c87c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/e9442a876aad45f892aa376435960cf5.png
[9eebcb3f0995450db045766c373c8366.png]: /images/20220828/e1b9803147e84084ab1010e58649d797.png
[8eb55560de0b4ffe909ce81c860a9dba.png]: /images/20220828/e85cddef5cd74d1da0bf7b475e046fdc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/dde06549c5d4491db9008fe9d4fd3a3f.png
[e8ab6ebfc55b4b37ae32fe6f08e2c030.png]: /images/20220828/7a9a5c828ec64ba2beec60dfc55c14a2.png
[eef140a495ea4882b07326ddfa1e7ce8.png]: /images/20220828/e21dc10ae7864e96b859c4ff4702e2df.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]: /images/20220828/c85cc2b4adee4ce7850c0eafa615f8b9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/9514d300198c44788c15cfe31c770bae.png
[3fa9081194094792a39a630db60af5c3.png]: /images/20220828/44648a44e7084813b660aa0a4fd97f3b.png
[258696cfccda479b856452b3581ef092.png]: /images/20220828/86d13601e59142deace3da36224605cb.png