前言：我们前面已经学习论map和set，现在又冒出来一个unordered_map和unordered_set，这两个有啥差别吗？前面我们已经说过，map和set的底层是红黑树，那unordered_map和unordered_set的底层是什么呢？接下来我们会逐渐揭开它神秘的面纱。
如果大家不了解map和set可以看我往期博客：C++之map与set的使用与原理+拓展avl树（详解）-CSDN博客
目录
一，unordered_map和unordered_set的使用
1)unordered_set
1）函数模板参数
2）构造函数
3）成员函数及功能
2）unordered_map
1）函数模板参数
2）构造函数
2）成员函数及功能
二，unordered_map和unordered_set的底层实现及代码
1）哈希表
2）常见哈希函数
3）线性探测法
4）线性探测法代码
1）提前准备
2）私有成员变量
3)插入
4）删除
5）查找
6）完整代码
5）悬挂法
1）私有成员变量
2）插入
3）删除
4）查找
5）完整代码
一，unordered_map和unordered_set的使用
1)unordered_set
1）函数模板参数
Hash模板参数默认是哈希桶（等下会讲原理），Pred则是一个判断两个key是不是相等的函数，用来查找元素和插入元素时判断是否存在，Alloc则类似于new开辟空间。
2）构造函数
explicit unordered_set ( const allocator_type& alloc );
分配器构造法
template
unordered_set ( InputIterator first, InputIterator last,
size_type n = /* see below */,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& alloc = allocator_type() );
迭代器范围构造法
unordered_set ( const unordered_set& ust );
unordered_set ( const unordered_set& ust, const allocator_type& alloc );
拷贝构造法
unordered_set ( unordered_set&& ust );
unordered_set ( unordered_set&& ust, const allocator_type& alloc );
移动构造函数（右值引用构造，我后面的博客应该会讲右值引用，现在大家期待一下吧）
unordered_set ( initializer_list
size_type n = /* see below */,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& alloc = allocator_type() );
初始化列表构造法（在C++11后，一切皆可{}初始化，例如：
unordered_set
1，2，3，4，5会形成一个初始化列表，这样子方便连续的构造
可以一次性就把所有初始化列表里面的值构造，无需多次调用构造函数。
3）成员函数及功能
unordered_set - C++ Referencehttps://legacy.cplusplus.com/reference/unordered_set/unordered_set/
2）unordered_map
1）函数模板参数
首先我们看模板参数，T也就是value，Hash函数默认是哈希桶，Pred则是一个判断两个key是不是相等的函数，用来查找元素和插入元素时判断是否存在，Alloc则类似于new开辟空间。
2）构造函数
explicit unordered_map ( const allocator_type& alloc );
分配器构造法
template
unordered_map ( InputIterator first, InputIterator last,
size_type n = /* see below */,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& alloc = allocator_type() );
迭代器范围构造法
unordered_map ( const unordered_map& ump );
unordered_map ( const unordered_map& ump, const allocator_type& alloc );
拷贝构造函数
unordered_map ( unordered_map&& ump );
unordered_map ( unordered_map&& ump, const allocator_type& alloc );
移动构造函数（右值引用构造）
unordered_map ( initializer_list
size_type n = /* see below */,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& alloc = allocator_type() );
初始化列表构造法
2）成员函数及功能
由于这是老生常谈了，大家看文档估计也能看懂，这里给大家一个链接，有兴趣的自行观看
unordered_map - C++ Referencehttps://legacy.cplusplus.com/reference/unordered_map/unordered_map/
二，unordered_map和unordered_set的底层实现及代码
1）哈希表
哈希表有点类似于我们的计数排序，但是计数排序有缺点就是只能排整形家族，哈希表就是会开大于我们要存储数据元素个数的大小（一般来说是数组），然后通过一个特点的转换公式把不同类型全部转化为无符号整形，然后按照下标存储，但是如何将不同类型的元素转换整形呢？这是一个问题，我们这里提供一个思路，假如是string或者插入类型，是不是它们都有ascll码值，将ascll码值转换为整型不就行了吗？
template
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// 特化 是匹配问题，当为string类型是不会走上面的HashFunc函数，特化的模板函数的格式在下面
template<>
struct HashFunc
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto e : s)
{
hash += e;
hash *= 131;
}
return hash;
}
};
我们也提供几种Hash整形的转换方法。
2）常见哈希函数
1. 直接定址法--(常用) 取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况 面试题：字符串中第一个只出现一次字符 2. 除留余数法--(常用) 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址 3. 平方取中法--(了解) 假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况 4. 折叠法--(了解) 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。 折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况 5. 随机数法--(了解) 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。 通常应用于关键字长度不等时采用此法 6. 数学分析法--(了解) 设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：
大家看完上面的内容，有没有发现一个问题，不论是哪种方法都会出现一个问题，可能不同的元素会映射到同一个位置，那我们该怎么办呢？现在给大家提供两种解决方法。
3）线性探测法
这种方法的解决办法是当发现两个位置冲突了之后，就从这个元素开始查找下一个空的元素，如果发现空的元素就插入，有些人可能会说如果全满了呢？那就回到0号下标开始继续查找，因为数组大小是大于元素个数的，所有不要担心全部满了。那查找呢？这种情况不能只查找映射位置，要一直往后找，直到碰到空。那如何删除了，删除不能直接删除，这样子可能会导致下次查找元素出现错误，因为这个位置制空后，查找的原则是找到空就停止，原本应该继续往后找的，但是因为你删除元素导致此位置为空，无法向后继续找，所有我们要有一个标记方法标注这里是被删除的，而不是本身就为空。
4）线性探测法代码
1）提前准备
首先我们需要一个东西来标记当前位置的状态，辨别删除和为空，防止误判，我们采用枚举
enum State { EMPTY, EXIST, DELETE };
2）私有成员变量
数组加枚举变量，数组因为里面要包括枚举和元素所以使用结构体封装一下
class Hash{
struct Elem
{
pair
State _state;
};
private:
std::vector
size_t _size;
size_t _totalSize; // 哈希表中的所有元素：有效和已删除, 扩容时候要用到
};
3)插入
bool Insert(const pair
if (((double)_size/_ht.size())>=0.7) {//如果元素占了整个数组大小的7/10就扩容
HashTable
a._ht.resize(_ht.size()*2); //开辟新的空间
for (size_t i = 0; i < _ht.size(); i++) {
if (_ht[i]._state == EXIST) {
a.Insert(_ht[i]._val);
}
}
a._ht.swap(_ht); //交换数据
_totalSize = _size;
}
size_t site = val.first % _ht.size(); //哈希函数求映射位
while (_ht[site]._state ==EXIST) { //找到空的位置或者已经被删除了的位置
site++;
site = site % _ht.size();
}
_ht[site]._state = EXIST; //改变状态
_ht[site]._val = val;
_size++;
_totalSize++; //数据个数加加
return true;
}
4）删除
// 删除
bool Erase(const K& key) {
size_t site = Find(key); //复用Find函数
if (site == 0) //没找到，返回false
return false;
_ht[site - 1]._state = DELETE; //改变状态和数据个数
_size--;
return true;
}
5）查找
// 查找
size_t Find(const K& key) {
size_t site = key % _ht.size(); //利用哈希函数求映射值
while (_ht[site]._state != EMPTY&&_ht[site]._val.first!=key) {
site++; //找到元素的位置并且位置状态位存在
site = site % _ht.size();
}
if (_ht[site]._state == EMPTY||_ht[site]._state==DELETE)
return 0;
return site+1; //返回下标
}
6）完整代码
#pragma once
#include
#include
#include
#include
using namespace std;
namespace Close_Hash
{
enum State { EMPTY, EXIST, DELETE };
template
class HashTable
{
struct Elem
{
pair
State _state;
};
public:
HashTable(size_t capacity = 5)
: _ht(capacity), _size(0), _totalSize(0)
{
for (size_t i = 0; i < capacity; ++i)
_ht[i]._state = EMPTY;
}
// 插入
bool Insert(const pair
if (((double)_size/_ht.size())>=0.7) {
HashTable
a._ht.resize(_ht.size()*2);
for (size_t i = 0; i < _ht.size(); i++) {
if (_ht[i]._state == EXIST) {
a.Insert(_ht[i]._val);
}
}
a._ht.swap(_ht);
_totalSize = _size;
}
//cout <<_size<<" "<<_ht.size() << "容量比：" << (double)_size / _ht.size() << endl;
size_t site = val.first % _ht.size();
while (_ht[site]._state ==EXIST) {
site++;
site = site % _ht.size();
}
_ht[site]._state = EXIST;
_ht[site]._val = val;
_size++;
_totalSize++;
return true;
}
// 查找
size_t Find(const K& key) {
size_t site = key % _ht.size();
while (_ht[site]._state != EMPTY&&_ht[site]._val.first!=key) {
site++;
site = site % _ht.size();
}
if (_ht[site]._state == EMPTY||_ht[site]._state==DELETE)
return 0;
return site+1;
}
// 删除
bool Erase(const K& key) {
size_t site = Find(key);
if (site == 0)
return false;
_ht[site - 1]._state = DELETE;
_size--;
return true;
}
size_t Size()const
{
return _size;
}
bool Empty() const
{
return _size == 0;
}
void Swap(HashTable
{
swap(_size, ht._size);
swap(_totalSize, ht._totalSize);
_ht.swap(ht._ht);
}
private:
size_t HashFunc(const K& key)
{
return key % _ht.capacity();
}
private:
std::vector
size_t _size;
size_t _totalSize; // 哈希表中的所有元素：有效和已删除, 扩容时候要用到
};
}
5）悬挂法
悬挂法人如其名，它的结构就是一个数组下面挂在一堆链表，也就是说数组里面并不直接存着元素，而是存着指针，这种方法有什么好处呢？前面我们的线性探测法如果当前位置被占了就需要找下一个空位，而悬挂法只需要在链表下面多加一个元素就行了。但是有一个小技巧，我们新加入的元素不需要挂在最后，只需要取代第一个结点的位置就行了。
1）私有成员变量
悬挂法需要一个一个数组，数组里面应该包括一个结点的struct指针，struct里面应该包括数据，和下一个结点的地址。
template
struct HashNode
{
HashNode
T _data;
HashNode(const T& data)
:_next(nullptr)
, _data(data)
{}
};
private:
vector
size_t _size; // 哈希表中有效元素的个数
2）插入
悬挂法插入结点先通过哈希函数找到下标，然后按照我上面说的那种方法，具体代码实现及注释如下
Node* Insert(const V& data)
{
// 0. 检测是否需要扩容
CheckCapacity();
// 1. 通过哈希函数计算data所在的桶号
size_t bucketNo = HashFunc(data);
// 2. 检测该元素是否在bucketNo桶中
// 本质：检测链表中是否存在data的节点
Node* pCur = _table[bucketNo];
while (pCur)
{
if (pCur->_data == data)
return nullptr;
pCur = pCur->_pNext;
}
// 插入新节点，直接头插
pCur = new Node(data);
pCur->_pNext = _table[bucketNo];
_table[bucketNo] = pCur;
++_size;
return pCur;
}
3）删除
删除元素需要先通过哈希函数找到下标，然后按照顺序查找是否存在这个元素，然后删除，但是删除要注意必须保存其父节点不然删除无法更新链表，还有就要要注意删除头节点要单独处理
// 删除哈希桶中为data的元素(data不会重复)
bool Erase(const V& data)
{
//哈希函数找结点，然后保存下标，需要一个指针指向其父亲
size_t bucketNo = HashFunc(data);
Node* pCur = _table[bucketNo];
Node* pPre = nullptr;
//找到下标后循坏查找
while (pCur)
{
if (data == pCur->_data)
{
// 删除
if (_table[bucketNo] == pCur)
{
// 删除第一个节点
_table[bucketNo] = pCur->_pNext;
}
else
{
// 删除的不是第一个节点
pPre->_pNext = pCur->_pNext;
}
delete pCur;
--_size;
return true;
}
pPre = pCur;
pCur = pCur->_pNext;
}
return false;
}
4）查找
如果仔细看了上面，估计查找已经手到擒来了，找到映射下标遍历就是了
Node* Find(const V& data)
{
size_t bucketNo = HashFunc(data);
Node* pCur = _table[bucketNo];
while (pCur)
{
if (data == pCur->_data)
return pCur;
pCur = pCur->_pNext;
}
return nullptr;
}
size_t Size()const
{
return _size;
}
bool Empty()const
{
return 0 == _size;
}
5）完整代码
#pragma once
#include
#include
#include "Common1.h"
using namespace std;
namespace OpenHash
{
template
class HashFunc
{
public:
size_t operator()(const T& val)
{
return val;
}
};
template<>
class HashFunc
{
public:
size_t operator()(const string& s)
{
const char* str = s.c_str();
unsigned int seed = 131; // 31 131 1313 13131 131313
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return hash;
}
};
template
struct HashBucketNode
{
HashBucketNode(const V& data)
: _pNext(nullptr), _data(data)
{}
HashBucketNode
V _data;
};
// 本文所实现的哈希桶中key是唯一的
template
class HashBucket
{
typedef HashBucketNode
typedef Node* PNode;
typedef HashBucket
public:
HashBucket(size_t capacity)
: _table(GetNextPrime(capacity))
, _size(0)
{}
~HashBucket()
{
Clear();
}
// 哈希桶中的元素不能重复
Node* Insert(const V& data)
{
// 0. 检测是否需要扩容
CheckCapacity();
// 1. 通过哈希函数计算data所在的桶号
size_t bucketNo = HashFunc(data);
// 2. 检测该元素是否在bucketNo桶中
// 本质：检测链表中是否存在data的节点
Node* pCur = _table[bucketNo];
while (pCur)
{
if (pCur->_data == data)
return nullptr;
pCur = pCur->_pNext;
}
// 插入新节点
pCur = new Node(data);
pCur->_pNext = _table[bucketNo];
_table[bucketNo] = pCur;
++_size;
return pCur;
}
// 删除哈希桶中为data的元素(data不会重复)
bool Erase(const V& data)
{
size_t bucketNo = HashFunc(data);
Node* pCur = _table[bucketNo];
Node* pPre = nullptr;
while (pCur)
{
if (data == pCur->_data)
{
// 删除
if (_table[bucketNo] == pCur)
{
// 删除第一个节点
_table[bucketNo] = pCur->_pNext;
}
else
{
// 删除的不是第一个节点
pPre->_pNext = pCur->_pNext;
}
delete pCur;
--_size;
return true;
}
pPre = pCur;
pCur = pCur->_pNext;
}
return false;
}
Node* Find(const V& data)
{
size_t bucketNo = HashFunc(data);
Node* pCur = _table[bucketNo];
while (pCur)
{
if (data == pCur->_data)
return pCur;
pCur = pCur->_pNext;
}
return nullptr;
}
size_t Size()const
{
return _size;
}
bool Empty()const
{
return 0 == _size;
}
void Clear()
{
for (size_t i = 0; i < _table.capacity(); ++i)
{
Node* pCur = _table[i];
// 删除i号桶所对应链表中的所有节点
while (pCur)
{
// 采用头删
_table[i] = pCur->_pNext;
delete pCur;
pCur = _table[i];
}
}
_size = 0;
}
size_t BucketCount()const
{
return _table.capacity();
}
void Swap(Self& ht)
{
_table.swap(ht._table);
swap(_size, ht._size);
}
private:
size_t HashFunc(const V& data)
{
return HF()(data) % _table.capacity();
}
void CheckCapacity()
{
if (_size == _table.capacity())
{
#if 0
HashBucket
// 将旧哈希桶中的元素向新哈希桶中进行搬移
// 搬移所有旧哈希桶中的元素
for (size_t i = 0; i < _table.capacity(); ++i)
{
Node* pCur = _table[i];
while (pCur)
{
ht.Insert(pCur->_data); // new 节点
pCur = pCur->_pNext;
}
}
Swap(ht);
#endif
Self ht(GetNextPrime(_size));
// 将旧哈希桶中的节点直接向新哈希桶中搬移
for (size_t i = 0; i < _table.capacity(); ++i)
{
Node* pCur = _table[i];
while (pCur)
{
// 将pCur节点从旧哈希桶搬移到新哈希桶
// 1. 将pCur节点从旧链表中删除
_table[i] = pCur->_pNext;
// 2. 将pCur节点插入到新链表中
size_t bucketNo = ht.HashFunc(pCur->_data);
// 3. 插入节点--->头插
pCur->_pNext = ht._table[bucketNo];
ht._table[bucketNo] = pCur;
}
}
this->Swap(ht);
}
}
private:
vector
size_t _size; // 哈希表中有效元素的个数
};
}
相关文章
发表评论