【高阶数据结构】哈希表详解

前言

上一篇文章我们学习了STL中unordered系列容器的使用，并且提到，unordered系列容器的效率之所以比较高（尤其是查找），是因为它底层使用了哈希结构，即哈希表。

那这篇文章，我们就来学习一下哈希表

1. 哈希的概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即
O($lo{g}_{2}N$)，搜索的效率取决于搜索过程中元素的比较次数

理想的搜索方法：

可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(一般称为哈希函数hashFunc)使元素的存储位置与它的关键码之间能够建立一 一映射的关系，那么在查找时通过该函数可以很快找到该元素

当向该结构中：

插入元素

根据待插入元素的关键码，以此函数（即上面提到的哈希函数）计算出该元素的存储位置并按此位置进行存放

搜索元素

对元素的关键码进行同样的函数计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

举个栗子：

待插入数据集合{1，7，6，4，5，9}
哈希函数设置为：hash(key) = key % capacity（ capacity为存储元素底层空间总的大小）
假设表的capacity为10，那插入之后就是这样的

那查找的时候我们直接通过函数获取下标位置查找即可
用该方法进行搜索不必进行多次关键码的比较，元素的存储位置与它的关键码之间能够建立一 一映射的关系，那么在查找时通过该函数可以很快找到该元素，因此搜索的速度比较快

但是，按照上述哈希方式，向集合中插入元素44，会出现什么问题？

44%10结果也是4，但是之前4这个元素已经存在下标为4的位置了！

那这种现象我们把它叫做哈希冲突。

2. 哈希冲突

对于两个数据元素的关键字$k_i$和 $k_j$(i != j)，有$k_i$ != $k_j$，但有：Hash($k_i$) == Hash($k_j$)，即：

不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

那引起哈希冲突的一个原因可能是：

哈希函数设计不够合理

那下面我们来介绍一下哈希函数。

3. 哈希函数

哈希函数（Hash Function）在哈希表中起着关键的作用。它接收键作为输入，并计算出一个索引或哈希码，用于确定键在哈希表中的位置。

哈希函数设计原则：

1. 哈希函数的定义域必须包括需要存储的全部关键码，如果散列表允许有m个地址时，其值域必须在0到m-1之间
2. 哈希函数计算出来的地址能均匀分布在整个空间中
3. 哈希函数应该比较简单

那常见的哈希函数都有哪些呢？

3.1 直接定址法（常用）

第一种哈希函数——直接定址法：

取关键字的某个线性函数为散列地址（通常是键值直接映射）：Hash（Key）= A*Key + B
优点：简单高效
缺点：适用场景有限
使用场景：适合于键值比较均匀、分布比较集中的情况

我们之前文章里讲过一道题：

就这个，这道题其实就用了哈希的思想

我们来复习一下。

当时讲的思路是这样的：

字符串中字符的范围就是【a,z】，那我们就可以创建一个大小为26的整型数组，然后用一个相对映射去统计每个字母的出现次数，a就映射到下标为0的位置，b就映射到下标为1的位置，依次类推。
那怎么让这些字母映射到对应的位置呢？
减去’a’得到的值是不是就是它们映射的位置啊，然后遍历字符串，每个字母映射的值是几，就让下标为几的元素++，初值全为0，这样遍历过后每个字母出现的次数就统计出来了。（下标0的元素的值就是a出现的次数，1位置就是b出现的次数…）
但是现在有一个问题，那就是出现一次的字母可能不止一个，我们怎么判断那个是第一个只出现一次的字母呢？

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/405198