1.两者与map及set的关系2.std::find和unordered_set::find3.随机数据测试4.底层结构
4.1哈希概念4.2哈希冲突4.3哈希函数
4.3.1直接定址法(常用)4.3.2除留余数法(常用) 5.解决哈希冲突
5.1闭散列——开放定址法
5.1.1线性探测5.1.2二次探测5.1.3负载因子5.1.4模拟实现
5.1.4.1判空5.1.4.2取模的选择5.1.4.3扩容的要求5.1.4.4仿函数处理各种类型转成整数 5.1.5小结 5.2开散列——哈希桶/拉链法
5.2.1概念5.2.2控制哈希冲突——控制负载因子5.2.3模拟实现5.2.4接口补充5.2.5迭代器的实现
5.2.5.1operator++5.2.5.2前置声明 5.2.6拷贝构造和赋值和析构5.2.7封装成unordered_map和unordered_set5.2.8小结
1.两者与map及set的关系map和set底层是红黑树，近似平衡搜索树。C++98支持。
unordered_map和unordered_set底层是哈希，哈希表/散列表。C++11支持。
前者有正向和反向迭代器。后者没有反向迭代器。
2.std::find和unordered_set::findstd::find对于只要有迭代器的可以用，遍历迭代器。涉及的目的是复用。
优点：通用算法，每个容器都可以使用，泛型算法。缺点：暴力查找。 O ( N ) O(N) O(N)。
unordered_set::find
优点:使用哈希特性去查找，效率高。 O ( 1 ) O(1) O(1)。
set类似，效率是 O ( l o g N ) O(logN) O(logN)。
序列式容器:vector/list/deque，纯粹存储数据。
关联式容器:map/set/unordered_map/unordered_set，存储数据+查找数据。
int main()
{
unorderedset um;
um.insert(2);
um.insert(4);
um.insert(3);
um.insert(5);
um.insert(1);
for(auto e: um){
cout<< e << " ";
}cout<
3.随机数据测试
可以看出，在大的数据下unordered系列效率更高。
void test()
{
int N = 100000;
vector v;
v.reserve(N);
srand(time(0));
for (int i = 0; i < N; ++i)
{
v.push_back(rand());
}
unordered_set us;
set s;
size_t begin1 = clock();
for (auto e : v)
{
s.insert(e);
}
size_t end1 = clock();
size_t begin2 = clock();
for (auto e : v)
{
us.insert(e);
}
size_t end2 = clock();
cout <<"set insert:" <
4.底层结构
unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。
4.1哈希概念
哈希/散列——建立映射关系
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。
顺序查找时间复杂度为O(N)，平衡树中为树的高度，即
O
(
l
o
g
2
(
N
)
)
O(log_2(N))
O(log2(N))，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
4.2哈希冲突
对于两个数据元素的关键字
k
i
k_i
ki和
k
j
k_j
kj
(
i
!
=
j
)
(i!=j)
(i!=j)，有
k
i
!
=
k
j
k_i !=k_j
ki!=kj,但有：
H
a
s
h
(
k
i
)
=
=
H
a
s
h
(
k
j
)
Hash(k_i) == Hash(k_j )
Hash(ki)==Hash(kj)，即:不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
4.3哈希函数
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：
哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间。哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单
4.3.1直接定址法(常用)
取关键字的某个线性函数为散列地址：
H
a
s
h
（
K
e
y
）
=
A
∗
K
e
y
+
B
Hash（Key）= A*Key + B
Hash（Key）=A∗Key+B
适用场景：使用于整数，且数据范围比较集中。每个值都对应一个唯一位置。
优点：
速度快，每个都是1次都能找到节省空间
缺点：
给的一组数据范围很大，直接定址法会浪费很多空间不能处理浮点数，字符串等处理情况。（字符串会存在冲突，而直接定址法是唯一位置）
字符串中的第一个唯一字符这个题就是一个简单的直接定址法的应用。
4.3.2除留余数法(常用)
根据数据个数，开辟一块空间,key%空间大小，算出映射的位置。
H
a
s
h
(
K
e
y
)
=
K
e
y
%
l
e
n
Hash(Key)=Key%len
Hash(Key)=Key%len
优点：使用场景广，不受限制。
缺点：存在哈希冲突，会导致不同的值映射同一个位置上。需要解决哈希冲突，哈希冲突越多，效率下降越厉害。
剩余还有一些平方取中法，折叠法，随机数法，数学分析法等
5.解决哈希冲突
5.1闭散列——开放定址法
5.1.1线性探测
比如该组数据:
1
,
5
,
10
,
100000
,
100
,
18
,
15
,
7
1,5,10,100000,100,18,15,7
1,5,10,100000,100,18,15,7。
处理方法：模出来映射的位置已经冲突，那就需要往后线性找一个空位置，存数据。
H
a
s
h
(
k
e
y
)
=
k
e
y
%
l
e
n
+
i
(
i
=
0
,
1
,
2...
)
Hash(key)=key%len+i(i=0,1,2...)
Hash(key)=key%len+i(i=0,1,2...)
线性探测缺点:某些连续位置出现冲突，会出现踩踏效应。
那么对空间增容有效果吗？增容并没有实际的效果。
5.1.2二次探测
为了解决线性探测的问题，有人提出了二次探测。
二次探测是按2次方的方式往后走。
H
a
s
h
(
k
e
y
)
=
k
e
y
%
l
e
n
+
i
2
(
i
=
0
,
1
,
2
,
3...
)
Hash(key)=key%len+i^2(i=0,1,2,3...)
Hash(key)=key%len+i2(i=0,1,2,3...)。如果超出了空间就类似循环队列%回来。
5.1.3负载因子
由前两个部分的讨论可以知道，空间不一定够，存在空间为满的情况，是需要扩容的。
负载因子(载荷因子) = 存储的有效数据个数/空间的大小。
负载因子越大，冲突的概率越高，增删查改的效率越低。
负载因子越小，冲突的概率越低，增删查改的效率越高，但是空间利用率很低，浪费很多。
5.1.4模拟实现
5.1.4.1判空
如何判断一个位置是空(没有值)?
这个问题涉及到删除。假如用0表示空，规定表中不存0。
比如删除100000，此时这个位置变成0，此时再找100就会在之前100000被删除的地方停止，因为0意味着空。这就会导致找不到100。
解决方法就是在HashData里加入状态值。一般使用枚举常量，方便调试。
查找状态看的是EMPTY，删除看的是DELETE
enum State
{
EMPTY,
EXITS,
DELETE
};
template < class K , class V >
struct HashData
{
pair _kv;
State _state = EMPTY; //状态
};
5.1.4.2取模的选择
取%使用的是vector的size()还是capacity
比如说有capacity为20，size为10，此时获得的值为15，使用[]就会访问出错。
5.1.4.3扩容的要求
扩容直接扩容可以满足要求吗？
不行，直接扩容会导致原来的映射关系会被破坏。需要重新计算每个数据在新空间中的位置。这也说明了哈希表的扩容代价是比较大的。
下份代码同样可以像红黑树封装map和set一样封装unordered_map和unordered_set。分别一个传key一个key-value，hashtable拿一个统一的T类型封装。
#pragma once
#include
#include
using namespace std;
namespace CloseHash
{
enum State
{
EMPTY,
EXITS,
DELETE
};
template < class K , class V >
struct HashData
{
pair _kv;
State _state = EMPTY; //状态
};
template < class K , class V >
class HashTable
{
public:
bool Insert(const pair& kv)
{
HashData< K, V >* ret = Find(kv.first);
if (ret) return false;
if (_table.size() == 0)
{
_table.resize(10);
}
else if ( (double)_n / (double)_table.size() > 0.7 )
{
增容
//vector newtable;
//newtable.resize(_table.size()*2);
//for (auto& e : _table)
//{
// if (e._state == EXITS)
// {
// ///重新计算放到newtablel
// ///...跟下面逻辑类似
// }
//}
//_table.swap(newtable);//到那时这部分会重写下面逻辑
HashTable newHT; //创建一个新对象
newHT._table.resize(_table.size() * 2); //此时新对象的_table增容了
for (auto& e : _table)
{
if (e._state == EXITS)
{
newHT.Insert(e._kv);//将旧表中存在的数据插入到新表，再次调用Insert自己来插入新数据。达到复用的效果。
}
}
_table.swap(newHT._table);
}
size_t start = kv.first % _table.size();
size_t index = start;
//探测后面的位置--线性探测或二次探测
size_t i = 1;
while (_table[index]._state == EXITS)
{
index = start + i;
index %= _table.size();
++i;
}
_table[index]._kv = kv;
_table[index]._state = EXITS;
++_n;
return true;
}
HashData* Find(const K& key)
{
if (_table.size() == 0)
{
return nullptr;
}
size_t start = key % _table.size();
size_t index = start;
size_t i = 1;
while (_table[index]._state != EMPTY )
{
if ( _table[index]._state == EXITS && _table[index]._kv.first == key )
{
return &_table[index];
}
index = start + i;
index %= _table.size();
++ i;
}
return nullptr;
}
bool Erase(const K& key)
{
HashData* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else {
ret->_state = DELETE;
return true;
}
}
private:
vector> _table;
size_t _n = 0;//存储的有效数据的个数
};
void TestHashTable()
{
int a[] = { 1, 5, 10 ,100000, 100 ,18 ,15 ,7 ,40 };
HashTable ht;
for (auto& e : a)
{
ht.Insert(make_pair(e, e));
}
auto ret = ht.Find(100);
if (ret)
{
cout << "找到了 " << endl;
}
else {
cout << "没找到" << endl;
}
ht.Erase(100000);
ret = ht.Find(100);
if (ret)
{
cout << "找到了 " << endl;
}
else {
cout << "没找到" << endl;
}
ht.Erase(100);
ret = ht.Find(100);
if (ret)
{
cout << "找到了 " << endl;
}
else {
cout << "没找到" << endl;
}
}
}
5.1.4.4仿函数处理各种类型转成整数
但是这种做法存在很多问题。
比如说传入的是字符串。字符串是没有%的。虽然可以通过重载%，但是肯定还会有其他的问题。
void TestHashTable1()
{
string str[] = { "苹果", "苹果","香蕉","香蕉","苹果","苹果","苹果","葡萄" };
HashTable ht;
for (auto& s : str)
{
auto ret = ht.Find(s);
if (ret)
{
ret->_kv.second++;
}
else {
ht.Insert(make_pair(s,1));
}
}
}
解决方法: 凡是泛型涉及到的各种类型比较计算问题，使用仿函数去处理。任意类型都可以做key,自己写一个对应的仿函数转化成整数就行。
处理整型，那么我们通过仿函数进行将输入转化成整形。
处理字符串，那么我们通过仿函数进行将输入转化成整形。通过字符串哈希的算法。
处理结构体，比如说结构中有一个整形，基本是唯一值——学号主码；比如说结构体中有一个字符串，基本是唯一值——身份z号；如果没有一项是唯一值，可以考虑多项组合。
但是不能用地址，同key的对象地址是不同的。
所以unordered_set中的hash就是转化成整数进行取模的仿函数。
#pragma once
#include
#include
using namespace std;
namespace CloseHash
{
enum State
{
EMPTY,
EXITS,
DELETE
};
template < class K , class V >
struct HashData
{
pair _kv;
State _state = EMPTY; //状态
};
template < class K , class V ,class HashFunc>
class HashTable
{
public:
bool Insert(const pair& kv)
{
HashData< K, V >* ret = Find(kv.first);
if (ret) return false;
if (_table.size() == 0)
{
_table.resize(10);
}
else if ( (double)_n / (double)_table.size() > 0.7 )
{
HashTable newHT; //创建一个新对象
newHT._table.resize(_table.size() * 2); //此时新对象的_table增容了
for (auto& e : _table)
{
if (e._state == EXITS)
{
newHT.Insert(e._kv);//将旧表中存在的数据插入到新表，再次调用Insert自己来插入新数据。达到复用的效果。
}
}
_table.swap(newHT._table);
}
HashFunc hf;
size_t start = hf (kv.first) % _table.size();
size_t index = start;
//探测后面的位置--线性探测或二次探测
size_t i = 1;
while (_table[index]._state == EXITS)
{
index = start + i;
index %= _table.size();
++i;
}
_table[index]._kv = kv;
_table[index]._state = EXITS;
++_n;
return true;
}
HashData* Find(const K& key)
{
if (_table.size() == 0)
{
return nullptr;
}
HashFunc hf;
size_t start = hf(key) % _table.size();
size_t index = start;
size_t i = 1;
while (_table[index]._state != EMPTY )
{
if ( _table[index]._state == EXITS && _table[index]._kv.first == key )
{
return &_table[index];
}
index = start + i;
index %= _table.size();
++ i;
}
return nullptr;
}
bool Erase(const K& key)
{
HashData* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else {
ret->_state = DELETE;
_n--;
return true;
}
}
private:
vector> _table;
size_t _n = 0;//存储的有效数据的个数
};
struct IntHashFunc
{
int operator()(int i)
{
return i;
}
};
void TestHashTable1()
{
int a[] = { 1, 5, 10 ,100000, 100 ,18 ,15 ,7 ,40 };
HashTable ht;
for (auto& e : a)
{
ht.Insert(make_pair(e, e));
}
auto ret = ht.Find(100);
if (ret)
{
cout << "找到了 " << endl;
}
else {
cout << "没找到" << endl;
}
ht.Erase(100000);
ret = ht.Find(100);
if (ret)
{
cout << "找到了 " << endl;
}
else {
cout << "没找到" << endl;
}
ht.Erase(100);
ret = ht.Find(100);
if (ret)
{
cout << "找到了 " << endl;
}
else {
cout << "没找到" << endl;
}
}
struct stringHashFunc
{
//static int mod 。类外初始化= 998244353;直接用unsigned long long 溢出自动取模
size_t operator()(const string& s)
{
size_t value = 0 ;
for(int i =0 ;i ht;
for (auto& s : str)
{
auto ret = ht.Find(s);
if (ret)
{
ret->_kv.second++;
}
else {
ht.Insert(make_pair(s,1));
}
}
}
}
5.1.5小结
一个类型去做map/set的Key有什么要求？ 能支持比较大小。一种方式是重载比较大小，存在是别人的库不支持的情况；使用仿函数来支持比较大小。
一个类型去做unordered_map/unordered_mapd的Key有什么要求？能支持转换成整型+相等比较。
那么类里面是怎么做到平时使用对于内置类型和string不用传仿函数的？
对于内置类型默认能转成整数，对于string类型进行模板的特化。
//默认能转整形的
template
struct Hash
{
size_t operator()(const K& key)
{
return key;
}
};
//模板的特化:string的
template<>
struct Hash
{
size_t operator()(const string& s)
{
size_t value = 0 ;
for(int i =0 ;i >
struct HashTabel{
};
5.2开散列——哈希桶/拉链法
5.2.1概念
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
关于插入
这种情况直接插入就可以了。
bool Insert(const pair& kv)
{
if (Find(kv.first)) return false;
size_t index = kv.first % _table.size();
Node* newnode = new Node(kv);
//头插
newnode->_next = _table[index];
_table[index] = newnode;
++_n;
}
关于删除
一般做法就是从头开始找同时获得父亲和当前结点，最后删除，特判一下在链表头的情况。
这里介绍一种替换法删除。但是这样会导致其他结点的迭代器失效。只是思路的一个小开拓。
bool Erase(const K& key)
{
size_t index = kv.first % _table.size();
Node* prev = nullptr;
Node* cur = _table[index];
while (cur)
{
if (cur->_first == key)
{
if (_table[index] == cur)
{
_table[index] = cur->_next;
}
else {
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
5.2.2控制哈希冲突——控制负载因子
影响哈希性能最重要的因素是负载因子。
但是同样存在哈希冲突的问题，如何控制哈希冲突呢？
控制负载因子
负载因子越小，冲突的概率越高。但是浪费的空间也越多。反之，则冲突概率越高，效率越低。负载因子大的时候可以扩容。
闭散列的开放定址法，负载因子不能超过1，一般建议控制在[0.0,0.7]左右开散列的哈希桶，负载因子可以超过1，一般建议控制在[0.0,1]左右把哈希表的大小改成素数据说可以减少哈希冲突
实际中哈希桶结构更实用，原因在于
空间利用率高
极端情况(数据不多，负载因子很低，但是这些数据大部分冲突了)可控
处理方式是将冲突数据多的这个桶改成红黑树结构(Java就是这么处理的)
struct HashNode
{
ListNode* _head;
RBTreeNode* _root;
bool _isList = true;
};
vector_table;
template
struct HashNode
{
forward_list _list;
set _tree;
};
vector>_table;
5.2.3模拟实现
namespace OpenHash
{
template
struct Hash {
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct Hash
{
size_t operator()(const string& str)
{
size_t res = 0;
for (auto ch : str)
{
res = res * 131 + ch;
}
return res;
}
};
template
struct HashNode
{
HashNode* _next;
pair _kv;
HashNode(const pair& kv)
:_next(nullptr),
_kv(kv)
{}
};
template>
class HashTable
{
typedef HashNode< K, V > Node;
public:
const int PRIMECOUNT = 28;
static const size_t primeList[PRIMECOUNT] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
size_t GetNextPrime(size_t prime)
{
size_t i = 0;
for (; i < PRIMECOUNT; ++i)
{
if (primeList[i] > prime )
return primeList[i];
}
return primeList[i];
}
bool Insert(const pair& kv)
{
if (Find(kv.first)) return false;
HashFunc hf;
//负载因子到1时进行增容
if (_n == _table.size())
{
vector newtable;
newtable.resize(GetNextPrime(_table.size()));
//遍历取旧表中结点，重新算映射关系，挂到新表中
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i])
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
size_t index = hf(cur->_kv.first) % newtable.size();
//头插
cur->_next = newtable[index];
newtable[index] = cur;
cur = next;
}
}
}
_table.swap(newtable);
}
size_t index = hf(kv.first) % _table.size();
Node* newnode = new Node(kv);
//头插
newnode->_next = _table[index];
_table[index] = newnode;
++_n;
}
Node* Find(const K& key)
{
if ( 0 == _table.size() ) return nullptr;
HashFunc hf;
size_t index = hf(key) % _table.size();
Node* cur = _table[index];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
HashFunc hf;
size_t index = hf(key) % _table.size();
Node* prev = nullptr;
Node* cur = _table[index];
while (cur)
{
if (cur->_first == key)
{
if (_table[index] == cur)
{
_table[index] = cur->_next;
}
else {
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
//Node** table;
vector _table;
size_t _n = 0;
};
void TestHashTable1()
{
int a[] = { 1,5,10,100000,100,18,15,7,40,44 };
HashTable ht;
for (auto e : a)
{
ht.Insert(make_pair(e, e));
}
ht.Insert(make_pair(25,25));
}
void TestHashTable2()
{
string str[] = { "苹果", "苹果","香蕉","香蕉","苹果","苹果","苹果","葡萄" };
HashTable ht;
for (auto& s : str)
{
auto ret = ht.Find(s);
if (ret)
{
ret->_kv.second++;
}
else {
ht.Insert(make_pair(s, 1));
}
}
}
}
5.2.4接口补充
负载因子的查看:load_factor哈希桶的个数:bucket_count申请哈希桶的空间:reserve和rehash
两者在空的情况下效果一样。如果已经有数据则推荐用rehash，旧空间有数据讲旧表的数据算到新表。对于已经知道数据个数可以提前开好空间，提升一些效率。
5.2.5迭代器的实现
5.2.5.1operator++
重点是opeartor++
对于自己在哪个位置我们可以直接算，但是找下一个位置就必然需要HashTable，因此把对应的HashTable的地址传过来(this）。
但是传指针也不能访问类的私有成员table，因此需要将__HITerator声明为HashTable的友元类。
template >
struct __HITerator
{
typedef HashNode Node;
typedef __HITerator Self;
typedef HashTable< K, T, KOfT, HashFunc > HT;
Node* _node;
HT* _pht;
__HITerator(Node* node,HT* pht)
:_node(node),
_table(pht)
{}
}；
template >
class HashTable
{
typedef HashNode Node;
public:
typedef __HITerator iterator;
template >
friend struct __HITerator;
iterator begin()
{
size_t i = 0;
while (i < _table.size())
{
if (_table[i])
{
return iterator(_table[i], this);
}
}
}
iterator end()
{
return iterator(nullptr, this);
}
};
template >
struct __HITerator
{
typedef HashNode Node;
typedef __HITerator Self;
typedef HashTable< K, T, KOfT, HashFunc > HT;
Node* _node;
HT* _pht;
__HITerator(Node* node,HT* pht)
:_node(node),
_pht(pht)
{}
Self& operator++()
{
//1.当前桶中还有数据,那么就在当前桶往后走
//2.当前桶走完了,需要往下一个桶去走(需要往后找)
if (_node->_next)
{
_node = _node->_next;
}
else
{
//匿名对象
size_t index = HashFunc()( KOfT()(_node->_data) ) % _pht->_table.size();
++index;
while (index < _pht->_table.size() )
{
if (_pht->_table[index])
{
_node = _pht->_table[index];
return *this;
}
else ++index;
}
_node = nullptr;
return *this;
}
return *this;
}
T& operator* ()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
};
5.2.5.2前置声明
针对这种情况需要前置声明。
5.2.6拷贝构造和赋值和析构
因为vector，因此调用vector的时候深拷贝为两个vector，但是里面的指针是浅拷贝的。所以需要手动实现。
c++11可以直接HashTable()=defalut显式指定默认构造函数。
拷贝构造也可以类似AVLTree的做法复用insert。
template >
class HashTable
{
typedef HashNode Node;
template >
friend struct __HITerator;
public:
typedef __HITerator iterator;
HashTable() = default;//显式指定默认构造函数
HashTable(const HashTable& ht)
{
_n = ht._n;
_table.resize(ht._table.size());
for (size_t i = 0; i < ht._table.size(); i++)
{
Node* cur = ht._table[i];
while (cur)
{
Node* cpnode = new Node(cur->_data);
//头插到新表
cpnode->_next = _table[i];
_table[i] = cpnode;
cur = cur->_next;
}
}
}
HashTable& operator=(HashTable ht)
{
_table.swap(ht._table);
swap(_n, ht._n);
return *this;
}
~HashTable()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
};
5.2.7封装成unordered_map和unordered_set
其对于key和key-value模型的封装和红黑树封装出map和set是一致的。哈希底层使用一个更高层度的抽象类型T同时表示key和key-value，通过传入的KeyOfType仿函数来取出key的key，key-value的key，从而获得要拿来比较的属性。
unordered_set
#pragma once
#include"HashTable.h"
namespace Y {
template
class unordered_set
{
public:
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
typedef typename OpenHash::HashTable::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair insert(const K& key)
{
return _ht.Insert(key);
}
private:
OpenHash::HashTable _ht;
};
void test_unordered_set1()
{
unordered_set us;
us.insert(200);
us.insert(1);
us.insert(2);
us.insert(33);
us.insert(50);
us.insert(60);
us.insert(243);
us.insert(6);
unordered_set::iterator it = us.begin();
while( it !=us.end() )
{
cout << *it << " ";
++it;
}
}
}
unordered_map
#pragma once
#include"HashTable.h"
namespace Y {
template
class unordered_map
{
public:
struct MapKeyOfT
{
const K& operator()(const pair& kv)
{
return kv.first;
}
};
typedef typename OpenHash::HashTable, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair insert(const pair& kv)
{
return _ht.Insert(kv);
}
V& operator[](const K& key)
{
pair ret = this->insert(make_pair(key, V()));
return ret.first->second;
}
private:
OpenHash::HashTable, MapKeyOfT> _ht;
};
void test_unordered_map1()
{
unordered_map dict;
dict.insert(make_pair("sort", ""));
dict["left"] = "123";
dict["left"] = "2132";
dict["map"] = "21412";
dict["string"] = "2131";
dict["set"] = "123";
unordered_map::iterator it = dict.begin();
while (it != dict.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
}
HashTable.h
#pragma once
#include
#include
using namespace std;
namespace CloseHash
{
enum State
{
EMPTY,
EXITS,
DELETE
};
template < class K , class V >
struct HashData
{
pair _kv;
State _state = EMPTY; //状态
};
template < class K , class V ,class HashFunc>
class HashTable
{
public:
bool Insert(const pair& kv)
{
HashData< K, V >* ret = Find(kv.first);
if (ret) return false;
if (_table.size() == 0)
{
_table.resize(10);
}
else if ( (double)_n / (double)_table.size() > 0.7 )
{
HashTable newHT; //创建一个新对象
newHT._table.resize(_table.size() * 2); //此时新对象的_table增容了
for (auto& e : _table)
{
if (e._state == EXITS)
{
newHT.Insert(e._kv);//将旧表中存在的数据插入到新表，再次调用Insert自己来插入新数据。达到复用的效果。
}
}
_table.swap(newHT._table);
}
HashFunc hf;
size_t start = hf (kv.first) % _table.size();
size_t index = start;
//探测后面的位置--线性探测或二次探测
size_t i = 1;
while (_table[index]._state == EXITS)
{
index = start + i;
index %= _table.size();
++i;
}
_table[index]._kv = kv;
_table[index]._state = EXITS;
++_n;
return true;
}
HashData* Find(const K& key)
{
if (_table.size() == 0)
{
return nullptr;
}
HashFunc hf;
size_t start = hf(key) % _table.size();
size_t index = start;
size_t i = 1;
while (_table[index]._state != EMPTY )
{
if ( _table[index]._state == EXITS && _table[index]._kv.first == key )
{
return &_table[index];
}
index = start + i;
index %= _table.size();
++ i;
}
return nullptr;
}
bool Erase(const K& key)
{
HashData* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else {
ret->_state = DELETE;
return true;
}
}
private:
vector> _table;
size_t _n = 0;//存储的有效数据的个数
};
struct IntHashFunc
{
int operator()(int i)
{
return i;
}
};
void TestHashTable1()
{
int a[] = { 1, 5, 10 ,100000, 100 ,18 ,15 ,7 ,40 };
HashTable ht;
for (auto& e : a)
{
ht.Insert(make_pair(e, e));
}
auto ret = ht.Find(100);
if (ret)
{
cout << "找到了 " << endl;
}
else {
cout << "没找到" << endl;
}
ht.Erase(100000);
ret = ht.Find(100);
if (ret)
{
cout << "找到了 " << endl;
}
else {
cout << "没找到" << endl;
}
ht.Erase(100);
ret = ht.Find(100);
if (ret)
{
cout << "找到了 " << endl;
}
else {
cout << "没找到" << endl;
}
}
struct stringHashFunc
{
size_t operator()(const string& s)
{
size_t value = 0;
for (auto ch : s)
{
value = value * 131 + ch;
}
return value;
}
};
void TestHashTable2()
{
string str[] = { "苹果", "苹果","香蕉","香蕉","苹果","苹果","苹果","葡萄" };
HashTable ht;
for (auto& s : str)
{
auto ret = ht.Find(s);
if (ret)
{
ret->_kv.second++;
}
else {
ht.Insert(make_pair(s,1));
}
}
}
void TestStringHashFunc()
{
stringHashFunc hf;
cout << hf("insert") << endl;
cout << hf("int") << endl;
cout << hf("abcd") << endl;
cout << hf("dcba") << endl;
}
}
namespace OpenHash
{
template
struct Hash {
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct Hash
{
size_t operator()(const string& str)
{
size_t res = 0;
for (auto ch : str)
{
res = res * 131 + ch;
}
return res;
}
};
template
struct HashNode
{
HashNode* _next;
T _data;
HashNode(const T& data)
:_next(nullptr),
_data(data)
{}
};
//前置声明
template
class HashTable;
//迭代器
template >
struct __HITerator
{
typedef HashNode Node;
typedef __HITerator Self;
typedef HashTable< K, T, KOfT, HashFunc > HT;
Node* _node;
HT* _pht;
__HITerator(Node* node,HT* pht)
:_node(node),
_pht(pht)
{}
Self& operator++()
{
//1.当前桶中还有数据,那么就在当前桶往后走
//2.当前桶走完了,需要往下一个桶去走(需要往后找)
if (_node->_next)
{
_node = _node->_next;
}
else
{
//匿名对象
size_t index = HashFunc()( KOfT()(_node->_data) ) % _pht->_table.size();
++index;
while (index < _pht->_table.size() )
{
if (_pht->_table[index])
{
_node = _pht->_table[index];
return *this;
}
else ++index;
}
_node = nullptr;
return *this;
}
return *this;
}
T& operator* ()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
};
template >
class HashTable
{
typedef HashNode Node;
template >
friend struct __HITerator;
public:
typedef __HITerator iterator;
HashTable() = default;//显式指定默认构造函数
HashTable(const HashTable& ht)
{
_n = ht._n;
_table.resize(ht._table.size());
for (size_t i = 0; i < ht._table.size(); i++)
{
Node* cur = ht._table[i];
while (cur)
{
Node* cpnode = new Node(cur->_data);
//头插到新表
cpnode->_next = _table[i];
_table[i] = cpnode;
cur = cur->_next;
}
}
}
HashTable& operator=(HashTable ht)
{
_table.swap(ht._table);
swap(_n, ht._n);
return *this;
}
~HashTable()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
iterator begin()
{
size_t i = 0;
while (i < _table.size())
{
if (_table[i])
{
return iterator(_table[i], this);
}
i++;
}
}
iterator end()
{
return iterator(nullptr, this);
}
const int PRIMECOUNT = 28;
const size_t primeList[28] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
size_t GetNextPrime(size_t prime)
{
size_t i = 0;
for (; i < PRIMECOUNT; ++i)
{
if (primeList[i] > prime )
return primeList[i];
}
return primeList[i];
}
pair Insert(const T& data)
{
KOfT kot;
auto ret = Find(kot(data));
if (ret != end())
{
return make_pair(ret, false);
}
HashFunc hf;
//负载因子到1时进行增容
if (_n == _table.size())
{
vector newtable;
newtable.resize(GetNextPrime(_table.size()));
//遍历取旧表中结点，重新算映射关系，挂到新表中
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i])
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
size_t index = hf( kot(cur->_data) ) % newtable.size();
//头插
cur->_next = newtable[index];
newtable[index] = cur;
cur = next;
}
}
}
_table.swap(newtable);
}
size_t index = hf( kot(data) ) % _table.size();
Node* newnode = new Node(data);
//头插
newnode->_next = _table[index];
_table[index] = newnode;
++_n;
return make_pair(iterator(newnode,this), true);
}
iterator Find(const K& key)
{
if ( 0 == _table.size() ) return end();
KOfT koft;
HashFunc hf;
size_t index = hf(key) % _table.size();
Node* cur = _table[index];
while (cur)
{
if (koft(cur->_data) == key)
{
return iterator(cur,this);
}
cur = cur->_next;
}
return end();
}
bool Erase(const K& key)
{
HashFunc hf;
size_t index = hf(key) % _table.size();
Node* prev = nullptr;
Node* cur = _table[index];
while (cur)
{
if (cur->_first == key)
{
if (_table[index] == cur)
{
_table[index] = cur->_next;
}
else {
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
//Node** table;
vector _table;
size_t _n = 0;
};
}
5.2.8小结
模板的编译错误直到实例化才会报错，而且模板的报错通常并不准确，甚至定位也不准确。因此建议采用屏蔽代码法来定位找到编译错误的位置。
相比平衡树和红黑树来说，哈希的算法并不复杂，但是重点在于对封装迭代器的学习以及结构的学习。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）