【C++】unordered系列

前言：

在C++11及以后的标准中，unordered容器是标准模板库（STL）的一部分，提供了高效的数据结构选项，适用于需要快速查找和插入操作的场景。

unordered通常与关联容器一起使用，特别是unordered_map和unordered_set。这些容器提供了基于哈希表的实现，它们提供了与map和set相似的接口，但在查找、插入和删除操作上通常具有更高的性能，尤其是在处理大量数据时。

• unordered_map是一个关联容器，它存储键值对，并根据键的哈希值进行排序，以实现快速的查找操作。
• unordered_set则存储唯一的元素，并使用哈希表来管理这些元素，以便快速检查一个元素是否存在于集合中。

unordered_map的接口说明

注： unordered_map和unordered_set接口相似就只介绍一个接口。

unordered_map的接口说明

函数声明	功能介绍
unordered_map	构造不同格式的unordered_map对象

unordered_map的容量

函数声明	功能介绍
bool empty()const	检测unordered_map是否为空
size_t size() const	获取unordered_map的有效元素个数

unordered_map的迭代器

函数声明	功能介绍
begin	返回unordered_map第一个元素的迭代器
end	返回unordered_map最后一个元素下一个位置的迭代器
cbegin	返回unordered_map第一个元素的const迭代器
cend	返回unordered_map最后一个元素下一个位置的const迭代器

unordered_map的元素访问

函数声明	功能介绍
operator[]	返回与key对应的value，没有一个默认值

unordered_map的查询

函数声明	功能介绍
iterator find(const K& key)	返回key在哈希桶中的位置
size_t count(const K& key)	返回哈希桶中关键码为key的键值对的个数

unordered_map的修改操作

函数声明	功能介绍
insert	向容器中插入键值对
erase	删除容器中的键值对
void clear()	清空容器中有效元素个数
void swap(unordered_map&)	交换两个容器中的元素

unordered_map的桶操作

函数声明	功能介绍
size_t bucket_count()const	返回哈希桶中桶的总个数
size_t bucket_size(size_t n)const	返回n号桶中有效元素的总个数
size_t bucket(const K& key)	返回元素key所在的桶号

哈希

1. **哈希（Hash）**是一种将任意大小的数据映射为固定大小值的函数，通常用于数据的快速查找和存储。
2. **哈希表（Hash Table）**是基于哈希函数的一种数据结构，它通过计算关键字的哈希值来直接访问存储位置，从而实现常数时间复杂度的查找性能。

• 在这里面的经过一系列的处理，得到的结果就映射到对应的位置，方便查找，加快了查找的速度。但是也会引发一系列的问题（哈希冲突）。

哈希函数

向上面的通过一系列的计算的过程就是哈希函数，有点类似于数学上的函数，一个数经过对应关系会得到两者的映射的关系。

常见的哈希函数

1. 直接定址法：这种方法通过一个简单的线性函数计算哈希地址，公式为 Hash(Key) = A * Key + B。这种方法简单且分布均匀，但需要提前知道键值的分布情况。
2. 除留余数法：这是一种常用的哈希函数，通过取关键字除以一个质数后的余数作为哈希地址，公式为 Hash(Key) = Key % p，其中 p 是一个不大于哈希表大小且最接近或等于哈希表大小的质数。
3. 乘法取余法：这种方法通过将关键字乘以一个固定的数（通常是一个接近2的数），然后取结果的整数部分并进行取模运算来计算哈希地址。这种方法适用于处理字符串等非整数类型的键值。
4. 平方取中法：这种方法适用于不清楚键值分布的情况，通过计算关键字平方后的中间几位数作为哈希地址。
5. 折叠法：折叠法将键值分割成几部分，然后将这些部分叠加求和，并取后几位作为散列地址，适用于键值位数较多的情况。
6. 标准库中的std::hash：C++标准库提供了std::hash模板，它为内置数据类型和一些标准库类型提供了默认的哈希函数实现。对于自定义类型，可以通过特化std::hash模板来提供自定义的哈希函数。

哈希冲突

哈希冲突是指不同的输入值通过哈希函数计算得到了相同的哈希值的现象。

1. 在哈希表等数据结构中，哈希冲突是不可避免的，因为哈希函数的输出范围通常远小于可能的输入值范围。

解决方法

• **开放定址法（闭散列）：**当发生冲突时，会在哈希表中寻找下一个空位置来存放新元素。常见的开放定址法有线性探测和二次探测。线性探测是从冲突位置开始，依次向后查找空位置；二次探测则是通过更复杂的数学公式来确定下一个探测位置。
• **再哈希法：**使用一个或多个备用哈希函数来处理冲突，将冲突的元素重新映射到哈希表的其他位置。
• 链地址法（开散列）：在哈希表的每个存储位置不是存储元素本身，而是存储一个指向元素的指针，冲突的元素会被添加到一个链表中。这种方法可以很好地处理大量冲突，但可能会导致链表过长，影响性能。
• **建立公共溢出区：**为所有可能的哈希冲突预留一个或多个区域，冲突的元素被存储在这些区域中。

**注：**降低哈希冲突是提高效率的一个很好的方法

简单哈希

• 在数组里面存储结构体
• 定义哈希要有存在的状态定义了枚举

template<class K,class V>
struct Hashdata
{pair<K, V> _kv;state _state = EMPTY;
};
enum state
{EXIST,EMPTY,DELETE
};

Hash结构

1. 两个模板参数K V结构
2. 最后是存储hash的取值，针对整形、浮点型、字符串。进行仿函数的重写

template<class K,class V,class HashFunc = Defaulthashfunc<K>>
class Hash
{
public:private:vector<Hashdata<K, V>> _table;size_t _n = 0;
};

仿函数

1. 在函数的内容的不确定的时候进行返回。
2. 针对string字符串的直接进行特模板化。
3. 针对26字母有不同的组合，要进行字符串的哈希化处理，目的是针对哈希冲突 （本次采用 BKDR算法）参考：字符串哈希算法

template<class K>
struct Defaulthashfunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct Defaulthashfunc<string>
{size_t operator()(const string& str){size_t hash = 0;for (auto e : str){hash *= 131;hash += e;}return hash;}
};

插入

• 将hash表直接扩容，进行哈希计算
• 进行哈希扩容 ： 不建议直接将哈希表填写满，不利于哈数的查找，将哈希的负载因子（已经存储的数据比总空间的大小）设置到0.7到0.8之间即可。
• 扩容： 重新定义哈希表（扩容后），进行数据的重新插入，进行交换
• 进行哈希的冲突的解决

	bool insert(const pair<K, V>& kv){size_t hashi = 0;HashFunc hf;hashi = hf(kv.first) % _table.size();if ((_n * 10 / _table.size()) >= 7){size_t newsize = _table.size() * 2;Hash<K, V, HashFunc> newhash;newhash._table.resize(newsize);for (int i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST){newhash.insert(_table[i]._kv);}}_table.swap(newhash._table);}//线性探测while (_table[hashi]._state == EXIST){++hashi;hashi %= _table.size();}_table[hashi]._kv = kv;_table[hashi]._state = EXIST;++_n;return true;}

开放定址法（闭散列）

发生冲突会在哈希表的另外一个空位置寻找。

//线性探测
while (_table[hashi]._state == EXIST)
{++hashi;hashi %= _table.size();
}_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_n;return true;
}

查找、删除

查找

返回结构体的指针利于后面的额删除

Hashdata<const K, V>* find(const K& key)
{HashFunc hf;size_t hashi = hf(key) % _table.size();while (_table[hashi]._state != EMPTY){if (_table[hashi]._state == EXIST&& _table[hashi]._kv.first == key){return (Hashdata<const K,V>*) & _table[hashi];}++hashi;hashi %= _table.size();}return nullptr;
}

删除

在删除的时候直接进行状态的修改

bool erase(const K& key)
{Hashdata<const K, V>* ret = find(key);if (ret){ret->_state = DELETE;--_n;return true;}return false;}