哈希（包含闭散列和开散列实现）
????????STL提供了两种关联式容器——树型和哈希关联式容器，本章就是关于哈希关联式容器的介绍。
unordered_map
unordered_map介绍
- unordered_map是一种储存键值对(key,value)的关联式容器，能够通过key快速索引到其对应的value
- 容器中，key值用于唯一的标示一个元素，value是一个对象，与key值关联，二者类型可以不相同
- 和map不同，unordered_map并不会对元素进行排序，为了能在常数范围中找到key对应的value，通常将相同哈希值的键值对放在相同的桶中
- 该容器对单个元素的访问比map快，但是在遍历元素自己的范围内效率低
- 可以通过 [] 访问value
- 迭代器至少是前向迭代器
unordered_map构造
- 该容器的构造函数实现了空的对象构造，迭代器构造等构造，和之前的容器使用方式一样?
unordered_map的容量
- ?empty：判断容器是否为空
- size：返回容器的大小
- max_size：返回容器的最大值
unordered_map的迭代器?
该容器的迭代器只有正向迭代器，没有rbegin。
使用方式和之前的容器一样，可以进行 ++，--，解引用等操作。
unordered_map的元素访问
- [] 访问：通过 [] 访问的元素若是存在，则放回key对应的value，否则就创建一个新的键值对<key,value>插入到容器中，value为默认值，并且容器大小++
- at访问：通过at访问的元素和 [] 访问类似，只不过当key值对应的value不存在时，直接抛异常
unordered_map的元素查找
- find：找到key值对应的元素并且返回
- count：查看key值的元素是否存在，并返回找到的元素数，但是由于unordered_map不允许重复的元素存在，因此这里返回值不是0，就是1
unordered_map的修改
emplace
这个函数返回一个 pair 类型，pair 的 first 为 iterator，seconde 为 bool 类型。
而且插入数据时不需要构建一个pair，内部会通过传入数据自动构建一个pair然后插入到set中。
不过当 unordered_map 中没有这个数据时，emplace 返回的 pair 的 first 是指向这个数据位置的迭代器，seconde 值为1，而有这个数据时，返回的 pair?的 first 是指向这个数据位置的迭代器，seconde 值为0；
emplace_hint
而这个函数只会返回一个指向插入数据的迭代器，并且我们可以指定插入的位置（容器可能会使用也可能不会使用此位置来插入数据）
只有当容器中没有元素和要插入的元素等效的键才会插入。
unordered_map的底层结构
unordered_map之所以被称为哈希型结构，就是因为底层采用的哈希结构。
哈希概念
在树型结构中，key值和value并没有直接的关系，因此在查找一个元素时需要多次比较才行，顺序查找的时间复杂度为 O(N),平衡树中为树的高度，即O(logN)。
而最理想的搜索方法就是不用进行比较，直接找到需要的元素。
那么，通过某种函数，来使元素的位置和它的键值构建一种关系，使之能够一一映射，那么查找时的速度就是最理想的。
而这就是哈希方法，该方法中的函数称为哈希函数，结构称为哈希结构。
哈希冲突
通过不同的关键字计算出相同的哈希地址，这种情况就是哈希冲突，而具有不同关键字但是有相同的哈希地址的数据元素称为"同义词"。
哈希函数
引起哈希冲突的原因就是哈希函数的设计不合理。
哈希函数的设计原则
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址，其值域必须包含在0-m-1之中
- 哈希函数计算出来的地址能够均匀的分布到整个空间中
- 哈希函数比较简单
哈希冲突的解决
哈希冲突的解决方式有两种：闭散列和开散列?
闭散列
????????闭散列又叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明哈希表还有空位，那么就可以将数据填到哈希冲突位置的下一个空位置去。这种方法就是线性探测。
线性探测：当发生冲突的位置开始，依次向后探测，知道找到下一个空位置为止。
- 插入
- 通过哈希函数获取插入元素在哈希表的位置
- 如果该位置没有元素就直接插入，否则就向后查找空位置，再插入元素
- 删除
- 采用闭散列时不能随便删除元素，否则会影响元素的查找（不同元素可能具有相同的哈希位置）
- 需要通过状态来标记一个元素是否被删除
当我们了解线性探测后，就能够实现线性探测的哈希表了。
哈希函数
using namespace std;
template<class K>
class DefaultHashFunc
{
public:
size_t operator() (const K& data)
{
return (size_t)data;
}
};
template<>
class DefaultHashFunc<string>
{
public:
size_t operator() (const string& data)
{
size_t ch = 0;
for (auto i : data)
{
ch *= 131;
ch += i;
}
return ch;
}
};如果是整型类型的哈希表，哈希函数就直接返回元素的值，但如果是string类型的话，我们需要对哈希函数做一个特化，这样才能保证不会有哈希冲突的出现。
闭散列的实现
namespace openaddress
{
enum STATE
{
EXIST,
EMPTY,
DELETE
};
template<class K,class V>
struct HashData
{
public:
pair<K,V> _data;
STATE _state = EMPTY;
};
template<class K,class V,class HashFunc = DefaultHashFunc<K>>
class HashTable
{
private:
void CheckCapacity()
{
//说明要扩容
if (_n * 10 / _table.size() >= 7)
{
HashTable<K, V, HashFunc> hs(_table.size()*2);
for (int i = 0; i < _table.size(); i++)
{
if (_table[i]._state == EXIST)
{
hs.Insert(_table[i]._data);
}
}
_table.swap(hs._table);
}
}
public:
HashTable(int n)
:_table(n),
_n(0)
{
}
HashTable()
:_table(10),
_n(0)
{
}
bool Insert(pair<K, V> kv)
{
if (Find(kv))
{
return false;
}
CheckCapacity();//检查是否需要扩容
HashFunc hf;
size_t index = hf(kv.first) % _table.size();
while (_table[index]._state == EXIST)
{
++index;
index %= _table.size();
}
_table[index]._data = kv;
_table[index]._state = EXIST;
++_n;
return true;
}
HashData<const K, V>* Find(pair<K, V> kv)
{
HashFunc hf;
size_t index = hf(kv.first) % _table.size();
while (_table[index]._state != EMPTY)
{
if (_table[index]._state == EXIST && _table[index]._data.first == kv.first)
return (HashData<const K, V>*) & _table[index];
index++;
}
return nullptr;
}
bool Erase(pair<K, V> kv)
{
HashData<const K, V>* ret = Find(kv);
if (ret)
{
ret->_state = DELETE;
--_n;
return true;
}
return false;
}
private:
vector<HashData<K,V>> _table;
size_t _n = 0;
};
}闭散列的扩容
散列表的载荷因子定义：α = 填入表中的元素个数 / 表的长度
对于闭散列来说，载荷因子是特别中要的因素，当散列表的载荷因子大于 0.7 时，就需要给闭散列扩容了。
线性探测的优缺点
线性探测的优点是实现十分简单，但是它的缺点十分致命：一旦发生哈希冲突，所有哈希冲突连在一起，容易形成数据堆积，即不同的关键码占据了重要位置，使得寻找位置需要多次比较，导致效率降低。
这就需要二次探测来避免该问题：将寻找下一个位置的方法改为：Hi = (H0 + i^2) % capacity。
其中 i 为常数，H0 是通过哈希函数获取的关键码，capacity 是表的大小。
因此，闭散列的最大问题就是空间利用率比较低。
开散列
开散列的概念
开散列又叫链地址法，首先通过哈希函数获取散列地址，相同的散列地址归于同一子集，每一个子集称为一个桶，桶内元素通过链表连接起来，各链表的头节点放在哈希表中。
每一个桶内的元素都发生了哈希冲突。
开散列的实现
namespace hash_bucket
{
template<class K,class V>
struct HashTableNode
{
HashTableNode(const pair<K,V>& kv)
:_next(nullptr),
_kv(kv)
{
}
pair<K, V> _kv;
HashTableNode<K, V>* _next;
};
template<class K,class V, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
typedef HashTableNode<K, V> Node;
typedef Node* pNode;
private:
void Checkcapacity()
{
size_t bucket = BucketCount();
HashFunc hf;
if (_n == bucket && bucket != 0)//若有效数据个数等于桶数就扩容
{
HashTable<K, V, HashFunc> hs(bucket*2);//创造一个新表
for (int i = 0; i < bucket; i++)
{
pNode cur = _table[i];
while (cur)
{
pNode next = cur->_next;
//获取在新表的位置
size_t index = hf(cur->_kv.first) % hs._table.size();
//头插进位置
cur->_next = hs._table[index];
hs._table[index] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(hs._table);
}
}
public:
HashTable()
:_table(10,nullptr)
,_n(0)
{
}
HashTable(size_t n)
:_table(n,nullptr)
,_n(0)
{
}
~HashTable()
{}
bool Insert(pair<K, V> kv)
{
if (Find(kv))
{
return false;
}
//检查是否扩容
Checkcapacity();
HashFunc hf;
size_t index = hf(kv.first) % _table.size();
pNode newnode = new Node(kv);
newnode->_next = _table[index];
_table[index] = newnode;
++_n;
return true;
}
pNode Find(pair<K, V> kv)
{
HashFunc hf;
size_t index = hf(kv.first) % _table.size();
pNode cur = _table[index];
while (cur)
{
if (cur->_kv.first == kv.first)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
bool Erase(pair<K, V> kv)
{
HashFunc hf;
size_t index = hf(kv.first);
pNode cur = _table[index];
pNode parent = nullptr;
while (cur)
{
if (cur->_kv.first == kv.first)
{
//若父节点不为空
if (parent)
{
parent->_next = cur->_next;
}
//为空
else
{
_table[index] = nullptr;
}
delete cur;
--_n;
return true;
}
parent = cur;
cur = cur->_next;
}
return false;
}
size_t BucketCount()
{
size_t count = 0;
for (int i = 0; i < _table.size(); i++)
{
if (_table[i] != nullptr)
{
count++;
}
}
return count;
}
private:
vector<pNode> _table;
size_t _n = 0;
};
}?开散列的扩容
开散列的扩容和闭散列不同，开散列扩容最好的情况是每个桶只有一个元素，当元素个数等于桶的个数时，就需要扩容。
void Checkcapacity()
{
size_t bucket = BucketCount();
HashFunc hf;
if (_n == bucket && bucket != 0)//若有效数据个数等于桶数就扩容
{
HashTable<K, V, HashFunc> hs(bucket*2);//创造一个新表
for (int i = 0; i < bucket; i++)
{
pNode cur = _table[i];
while (cur)
{
pNode next = cur->_next;
//获取在新表的位置
size_t index = hf(cur->_kv.first) % hs._table.size();
//头插进位置
cur->_next = hs._table[index];
hs._table[index] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(hs._table);
}
}当元素个数等于桶的个数后，就将哈希表的个数扩展为原来的两倍（自己定义），这样就能够成功扩容，并且提升闭散列的效率。
string类型的插入
本文开散列对于string类型的插入的操作方法和闭散列一样。
都是对泛型的函数进行特化。
template<>
class DefaultHashFunc<string>
{
public:
size_t operator() (const string& data)
{
size_t ch = 0;
for (auto i : data)
{
ch *= 131;
ch += i;
}
return ch;
}
};本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- L1-056 猜数字(Java)
- 198.【2023年华为OD机试真题（C卷）】万能字符单词拼写（Java&Python&C++&JS实现）
- Massachusetts Institute of Technology
- 详解JavaScript闭包
- 【2023-11-29】华为秋招笔试三道编程题解
- C#编程-使用变量
- 大型语言模型基础知识的可视化指南
- 【vue滚动条插件vuescroll】【vue自定义滚动条】
- 第七天| 454.四数相加II、383. 赎金信 、15. 三数之和、18. 四数之和
- k8s面试之——简述网络模型