数据结构：哈希表 | C++中的set与map

上回说到，红黑树是提升了动态数据集中频繁插入或删除操作的性能。而哈希表(Hash Table)，则是解决了传统数组或链表查找数据必须要遍历的缺点。

---

哈希表

哈希表的特点就是能够让数据通过哈希函数存到表中，哈希函数能够将数据处理为表中位置的索引(这个就叫映射)，然后将其存入。这样一来，我们查找数据的时候只要一通过哈希函数就可以得到该数据的索引，然后进行操作。

哈希函数有很多种实现方法。

1、直接定址法

数据本身就直接作为哈希地址（即位置索引）然后进行存放，好处就是不会产生哈希冲突。

可以看到我们的存入的数据是分散在表中的，只有3个数却占用了6个位置。这也是为什么哈希表又叫散列表。这种方法只适合数据集中的情况。

2、除留余数法

这是最经典的方法。通过指定一个除数，将我们的数据进行相除来得到哈希地址。

这种方法可以有效地减少空间浪费，将数据集中起来。但是如果像2、22这样的数就会产生哈希冲突。其解决方法之后会讲到。

3、平方取中法

这个通过将数据平方计算后，根据哈希表的大小取中间的几位数，这样更有机会让数据随机均匀分布在哈希表中。

如1234的平方为1522756，哈希表的大小是100，那么去中间3位，存入227的地址中。

现在谈谈如何解决哈希冲突，一般有两种方法。

1、开放寻址法(闲散列)

顾名思义就是让空地址向发生冲突的新数据开放，让其存进去。比如线性探测和二次探测。线性探测是指按照顺序将新数据排在原本哈希地址的后面，先+1，不行+2，依次类推。而二次探测就是把这些数进行了平方再加，向前后两方进行。

那我们如果一直发生冲突，导致哈希表大小不够用了怎么办？这里需要引入“负载因子”的概念。负载因子是一个比例，表示当哈希表中的数据比哈希表的大小超过负载因子时，哈希表需要扩容，一般为0.7。

2、链地址法(开散列)

哈希桶法，拉链法一般都是指这个。

就是把每个位置作为一个链表的头，如果发生冲突，就将其作为后继节点连接在该位置下面。

虽然这样的负载因子可以大于一(即不用扩容)，但因为要存储指针，会造成更多的空间开销。

我们讨论哈希表时常常会谈到“键值对”。这里的“键 Key”就是钥匙的意思，可以通过键来获取哈希地址。所以我们上文所操作的所有数据，都可以叫做键，关键码值常常也说的是这个。而另一个“值 Value”指的是与键关联的数据，其存在真正赋予了哈希表以灵活性与实用性，因为键一旦在哈希表中确认就不便更改了，而值可以随便的更新删除。所以键更像成为了值的索引，从而适应常用的操作。

之前上文中介绍的都是值为空、只有键的情况，这可以称为是哈希表实现的“集合 Set”，而包含键值对的情况称为哈希表实现的“映射 Map”。

上文提到的哈希桶，就是指储存了键值对的一个位置。“哈希桶法”就是因为一个桶下面连着挂着好几个桶而得名的。

C++中的set与map

现在终于到了追本溯源的时候了。C++的STL库中，分别有着用红黑树实现的<set><map>，还有着用哈希表实现的<unordered_set><unordered_map>，这两种结构下最显著的区别就是其有序性了，红黑树默认是升序排列的。

上次讲到红黑树的查找删除操作时间复杂度都是O(logn)，而哈希表是O(1)(平均复杂度，最坏情况O(n)，持续哈希冲突)，可以说是这种结构最大的优势了，但其需要预分派桶数组，拉链法还有存新链表，造成更多的空间占用。那么<unordered_set>和<unordered_map>大多会用在不关心顺序，追求快速操作的场景，其他情况都用<set><map>即可。

除了STL容器的通用方法以外，集合和映射还有这些用法。

//集合
set<int> s1 = { 1, 3, 2 };
unordered_set<int> s2 = { 1, 3, 2 };
s1.count(1);//在set中由于不重复性，可用于检测存在否
s2.count(1);//返回0或1
//对于有序的set
cout << *s1.lower_bound(1) << endl;//找到大于等于目标值的数迭代器
cout << *s1.upper_bound(1) << endl;//找到大于目标值的数迭代器
//对于无序的unordered_set
int num = s2.bucket_count();//桶的数量
cout << num << endl;
cout << s2.load_factor() << endl;//查看负载因子
s2.rehash(11);//设置桶的数量，重哈希，这个过程也包含对照负载因子扩容
num = s2.bucket_count();
cout << num << endl;
//映射
map<int, int> m1 = { {1, 3}, {2, 9}, {3, 4} };//前为key后为value
unordered_map<int, int> m2 = { {1, 3}, {2, 9}, {3, 4} };
m1.count(1);//检测存在否
m2.count(1);
//插入键值对，若键已存在则不覆盖
m1.emplace(2, 1);
m2.emplace(2, 1);
m1.insert({ 4, 6 });//这个返回迭代器
m2.insert({ 4, 6 });
//通过[key]访问value
cout << m1[1] << endl;
cout << m2[4] << endl;
//对于有序的map     //用first和second访问key和value
cout << m1.lower_bound(1)->first << endl;//找到key大于等于目标值的数迭代器
cout << m1.upper_bound(1)->second << endl;//找到key大于目标值的数迭代器
//对于无序的unordered_map
cout << m2.bucket(3) << endl;//返回key3的桶编号
m2.reserve(10);//预分配空间

 正好，一道名为“数组的度”的题就是用哈希表解决的，就在这里练练手吧！

    int findShortestSubArray(vector<int>& nums) {//key用来记录对应的数，vector用来记录索引unordered_map<int, vector<int>> m; //第一次记录for(int i = 0; i < nums.size(); i++){if(!m.count(nums[i])){ //分别是 出现次数、头索引、尾索引m[nums[i]] = {1, i, i};}else{  //增加次数，更新尾索引m[nums[i]][0]++;m[nums[i]][2] = i;}}//寻找出现次数最大的int num = 0, minLength = 0;//注意，获取的每一个是键值对类型pair<T1, T2>for(pair<int, vector<int>> it : m){if(num < it.second[0]){ num = it.second[0]; minLength = it.second[2] - it.second[1] + 1; }else if(num == it.second[0]){ if(minLength > it.second[2] - it.second[1] + 1){ minLength = it.second[2] - it.second[1] + 1;}}}return minLength;}   

---

小结

最近笔者还真抽不出时间好好学习游戏开发有关的知识，七七八八的事情挺多。不过瓜熟蒂落，水到渠成，把事情都梳理顺畅，再着手沉淀也不晚。

如有补充纠正欢迎留言。