【数据布局】哈希表(散列表)

目次
1、unordered系列关联式容器
2、哈希概念
3、哈希函数
3.1 直接定址法
3.2 除留余数法
4、哈希辩论
4.1 闭散列(开放定址法)
4.1.1 线性探测
4.1.2 二次探测
4.1.3 线性探测代码实现
插入
搜刮
删除
对于不可以取模的范例
4.2 开散列(哈希桶/拉链法)
插入
搜刮
删除
对于不可取模的范例

---

1、unordered系列关联式容器

在C++98中，STL提供了底层为红黑树布局的一系列关联式容器，在查询时服从可到达O(logN)，即最差环境下必要比力红黑树的高度次，当树中的节点非常多时，查询服从也不抱负。最好的查询是，举行很少的比力次数就可以或许将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树布局的关联式容器利用方式根本雷同，只是其底层布局差别，其底层布局是利用哈希表实现的。
这四个容器是unordered_set、unordered_map、unordered_multiset和unordered_multimap。这四个容器后序会有具体先容，这里就简朴先容一下unordered_set和set的区别，为了反面更好地先容哈希表

unoredered_set和set百分之90的内容都是雷同的，差别点有：
1. 对key的要求差别
set：支持比力巨细(自界说范例自己写比力函数)
unordered_set：支持key转化为整型 + 比力相称
2. set遍历有序，unordered_set遍历无序
3. set是双向迭代器，unordered_set是单向迭代器
4. 性能差别(插入、删除、搜刮)
set：O(logN)             unordered_set：O(1)
2、哈希概念

哈希/散列是一种头脑，指的是值与值创建映射关系
哈希表/散列表是根据哈希头脑计划出来的数据布局，是将值与存储位置创建映射关系
我们利用一道题来引入哈希表

这道题是只包罗小写字母的，以是我们可以想到，创建一个巨细为26的整型数组，用一个下标代表一个字符，下标 = 字符 - ‘a’，然后遍历一遍字符串s，统计出每个字符出现的个数，完成之后，再遍历一次字符串s，假如遍历到的字符对应的下标的值是1，就代表这个字符再字符串中只出现了1次，也就是结果

1. class Solution {
2. public:
3.     int firstUniqChar(string s) {
4.         // 统计每个字符出现的次数
5.         int count[26] = {0};
6.         int size = s.size();
7.         for(int i = 0; i < size; ++i)
8.             count[s[i] - 'a'] += 1;
9.         // 按照字符次序从前往后找只出现一次的字符
10.         for(int i = 0; i < size; ++i)
11.             if(1 == count[s[i] - 'a'])
12.                 return i;
13.         return -1;
14.     }
15. };

复制代码

这就是哈希头脑，谁人数组就是哈希表。将字符串中大概出现的字符与数组的下标(存储位置)创建起了映射关系。当搜刮一个值出现的次数时count[s - 'a']，时间复杂度就是O(1)。但与真正的哈希表也是有些区别，真正的哈希表是将值(在这里也就是字符)放到映射的存储位置，而这里是将值出现的次数放到映射的存储位置。
我们之前学过的次序布局以及均衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要颠末关键码的多次比力。次序查找时间复杂度为O(N)，均衡树中为树的高度，即O(logN)，搜刮的服从取决于搜刮过程中元素的比力次数
抱负的搜刮方法：可以不颠末任何比力，一次直接从表中得到要搜刮的元素。假如构造一种存储布局，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间可以或许创建逐一映射的关系，那么在查找时通过该函数可以很快找到该元素
当向该布局中：
插入元素：根据待插入元素的关键码，以此函数盘算出该元素的存储位置并按此位置举行存放
搜刮元素：对元素的关键码举行同样的盘算，把求得的函数值当做元素的存储位置，在布局中按此位置取元素比力，若关键码相称，则搜刮乐成
该方式即为哈希(散列)方法，哈希方法中利用的转换函数称为哈希(散列)函数，构造出来的布局称为哈希表(Hash Table)(大概称散列表)
若要将值与存储位置创建映射关系，就必要利用哈希函数
3、哈希函数

将值与存储位置创建关系的函数，称为哈希函数
常用的哈希函数有多种，这里仅先容两种
3.1 直接定址法

取关键字的某个线性函数为散列地点：Hash(Key)= A*Key + B
用key的值映射一个绝对位置或相对位置
优点：简朴、匀称、没有辩论
缺点：只恰当范围会集的数据
利用场景：恰当查找比力小且连续的环境
上面的标题利用的就是这种方法，地点 = 字符 - 'a'，之以是实用这种方法，是由于26个字母是连着的，是范围会集的数据，参加有一组数据是10，20，15，35，66，16，10000，假如利用直接定址法，必要开一个10000巨细的数组，而且内里的数据非常分散，显然是不实用的
3.2 除留余数法

key模表的巨细N后，映射到表中的一个位置
hashi = key % N，N是表的巨细
假设有一组数据10，20，15，35，66，16，10000，表的巨细是10，会发现，用10和20模表的巨细，结果都是0，那是将10和20都放到下标为0的位置吗？这种环境称为哈希辩论
4、哈希辩论

哈希辩论就是指差别值，取模以后映射到雷同位置，也称为哈希碰撞
办理哈希辩论的两种常用方式是：闭散列和开散列
4.1 闭散列(开放定址法)

闭散列：也叫开放定址法，当发生哈希辩论时，假如哈希表未被装满，阐明在哈希表中一定尚有空位置，那么可以把key存放到辩论位置中的“下一个” 空位置中去。那怎样探求下一个空位置呢？
闭散列就是按规则去其他位置找一个空位置存储，也就是根据这个规则去探求“下一个”位置，探求下一个位置的方法有两种，线性探测和二次探测
4.1.1 线性探测

线性探测就是若映射到的位置已经被占了，则从这个位置开始，往下探求空的位置，怎样将数据放入空位置中。但这种方法轻易造成一片拥堵，由于这个值占用了别人的位置，反面插入的值又要今后占位置
当前位置 + 1 ，若还被占了，当前位置+2，...，不停到空位置

4.1.2 二次探测

二次探测与线性探测是雷同的，都是当映射到的位置已经被占了，当前位置 + 1^2 ，若还被占了，当前位置 + 2^2，...，不停到空位置
在前面，我们有提到set和unordered_set对key的要求差别， unordered_set要求key可以比力相称，正是在这里体现了这个作用。而且支持将key转为整型就是为了可以或许取模
在代码实现，我们只实现线性探测，由于两者是雷同的
4.1.3 线性探测代码实现

我们前面只是相识了线性探测的插入利用，接下来我们相识一下线性探测的查找和删除利用

查找16：先去16映射到的位置查察，比力这个位置存储的值与16是否相称，若不想等，则继续今后查找，若到了空，则表中没有这个数据。像这里，16映射到的位置存放的是35，不是16，以是继续向后查找，不停到下标为8的时间找到16。假设要查找的是26，则26映射到的位置是35，继续向后查找，会发现，不停到下标为9没有存放值的位置都没有找到26，以是表中没有26
删除66：先查找66，若66存在，则删除

此时假如再查找16，会发现表中有16，但是找不到。以是，表中存数据时，每个位置不应该只存数据，还应该存放这个数据的状态。数据的状态有3种：存在、不存在、删除。此时也必要修改一下上面的查找和删除逻辑。查找除了要比力值是否雷同，而且还必要这个值的状态是存在，才算找到，找不到时，是从映射的位置不停向后找，直到状态为空，

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金