关于哈希表，你得知道这些！（哈希表的大总结）_哈希表 算是二次包装码

哈希表的知识点对于我来说比较陌生，所以在这里进行一个合集总结，参照代码随想录的刷题顺序对哈希表的具体应用进行一个相对全面的总览。

哈希表理论基础

（黄色高亮的内容为知识点标记）

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

用大白话来说——我们事先人为设定一个规律，根据这种规律，某一个数据应该放在表中的哪一个位置我们是可以推出来的，此后如果我们想知道这个数据有没有，我们只需要到理论中它应该存在的位置去找就可以，如果找不到那就说明这个数据是不存在的。

其中，某种规律其实就是哈希函数中的内部处理，也就是说我们通过哈希函数来确定这种规律。

从上述的大白话讲解中，我们也可以总结出哈希表的应用场景——

快速判断某一个数据是否在原集合中存在。

但有时候，我们设置的规律可能无法满足所有数据都能“一个萝卜一个坑”，例如设置规律为“对25取余”，但实际数据的范围为[0, 30],这时候有些数据就会发生冲突，我们将这种冲突称为哈希碰撞。

解决哈希碰撞的方法主要有两种：

• 拉链法

• 线性探测法

拉链法主要是对冲突的元素采用链表的方式进行连接，如下图：

线性探测法可以看成是一种和和气气的占座方式，比如说有两个人（A和B）都买到了位置2，但是A先到了，B就没有位置坐了，此时B就往后找位置，找到了位置3，但是位置3已经被本来就应该在这里的C占到了，这时候B就接着往后找，找到了位置4，位置4没有人，B就坐下了。过了一会儿，本来应该坐在位置4上的D上车了，发现位置4被B占领了，D没有生气，而是接着往后找位置坐，跟B的行为一致。这种方式就叫做线性探测法。

当然，大家都能和和气气让座占座的前提是大家都知道所有人一定都能坐得下，这就要求我们在预开数组的时候要让数组的容量大于所有参与到哈希函数中的元素数量。

除此之外，解决冲突的方法还有再哈希法以及建立公共溢出区等等，这里不做详述，以上四种方法也可以参考下面这篇博客