本章主要讲解unordered系列关联式容器及其底层结构和模拟实现,还有哈希的相关应用等
函数声明 | 功能介绍 |
---|---|
unordered_map | 构造不同格式的unordered_map对象 |
函数声明 | 功能介绍 |
---|---|
bool empty() const | 检测unordered_map是否为空 |
size_t size() const | 获取unordered_map的有效元素个数 |
函数声明 | 功能介绍 |
---|---|
begin | 返回unordered_map第一个元素的迭代器 |
end | 返回unordered_map最后一个元素下一个位置的迭代器 |
cbegin | 返回unordered_map第一个元素的const迭代器 |
cend | 返回unordered_map最后一个元素下一个位置的const迭代器 |
函数声明 | 功能介绍 |
---|---|
operator[] | 返回与key对应的value,没有一个默认值 |
注意:该函数中实际调用哈希桶的插入操作,用参数key与V()构造一个默认值往底层哈希桶中插入,如果key不在哈希桶中,插入成功,返回V(),插入失败,说明key已经在哈希桶中,将key对应的value返回
函数声明 | 功能介绍 |
---|---|
iterator find(const K& key) | 返回key在哈希桶中的位置 |
size_t count(const K& key) | 返回哈希桶中关键码为key的键值对的个数 |
注意:unordered_map中key是不能重复的,因此count函数的返回值最大为 1,对于unordered_multimap才是允许键值冗余的
函数声明 | 功能介绍 |
---|---|
insert | 向容器中插入键值对 |
erase | 删除容器中的键值对 |
void clear() | 清空容器中有效元素个数 |
void swap(unordered_map&) | 交换两个容器中的元素 |
函数声明 | 功能介绍 |
---|---|
size_t bucket_count()const | 返回哈希桶中桶的总个数 |
size_t bucket_size(size_t n)const | 返回n号桶中有效元素的总个数 |
size_t bucket(const K& key) | 返回元素key所在的桶号 |
void test_unordered_map()
{
unordered_map<string, string> dict;
dict.insert(make_pair("string", ""));
dict.insert(make_pair("sort", ""));
auto it = dict.begin();
while (it != dict.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
成员函数 | 功能 |
---|---|
insert | 插入指定元素 |
erase | 删除指定元素 |
find | 查找指定元素 |
size | 获取容器中元素的个数 |
empty | 判断容器是否为空 |
clear | 清空容器 |
swap | 交换两个容器中的数据 |
count | 获取容器中指定元素值的元素个数 |
成员函数 | 功能 |
---|---|
begin | 获取容器中第一个元素的正向迭代器 |
end | 获取容器中最后一个元素下一个位置的正向迭代器 |
void test_unordered_set()
{
unordered_set<int> s;
s.insert(3);
s.insert(4);
s.insert(5);
s.insert(3);
s.insert(1);
s.insert(2);
s.insert(6);
unordered_set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test_op()
{
set<int> s;
unordered_set<int> us;
const int n = 1000000;
vector<int> v;
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
v.push_back(rand());
}
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:" << end1 - begin1 << endl;
cout << "unordered_set insert:" << end2 - begin2 << endl;
cout << "=====================" << endl;
size_t begin3 = clock();
for (auto e : v)
{
s.find(e);
}
size_t end3 = clock();
size_t begin4 = clock();
for (auto e : v)
{
us.find(e);
}
size_t end4 = clock();
cout << "set find:" << end3 - begin3 << endl;
cout << "unordered_set find:" << end4 - begin4 << endl;
cout << "=====================" << endl;
size_t begin5 = clock();
for (auto e : v)
{
s.erase(e);
}
size_t end5 = clock();
size_t begin6 = clock();
for (auto e : v)
{
us.erase(e);
}
size_t end6 = clock();
cout << "set erase:" << end5 - begin5 << endl;
cout << "unordered_set erase:" << end6 - begin6 << endl;
}
总结:使用底层为哈希的容器总体的效率是非常高的,对于关联式set/map的复杂度能达到O(logN),而unordered系列关联式容器可以达到接近O(1)的水平
unordered系列的关联式容器之所以效率比较高,是因为其底层使用了哈希结构
该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称散列表)
哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小
注:该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快,但是这样的搜索存在哈希冲突
哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中
取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B
优点:简单、均匀 缺点:需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况
设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址
假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况
闭散列和开散列
闭散列也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去
从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止,即newindexi=(index+i)%capacity 线性探测实现非常简单,但是一旦发生哈希冲突,所有的冲突连在一起,容易产生数据**“**堆积”,即:不同关键码占据了可利用的空位置,使得寻找某关键码的位置需要许多次比较,导致搜索效率降低
从发生的冲突的位置开始,不逐个往后找,而是以平方个位置找,即计算位置为newindexi=(index+i^2)%capacity 二次探测可以较为有效的方式减小哈希冲突的概率
通过哈希函数获取待插入元素在哈希表中的位置,如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素
采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索,比如删除元素4,如果直接删除掉,44查找起来可能会受影响 因此线性探测采用标记的伪删除法来删除一个元素,即每个位置都有一个表示当前状态的变量,存在数据为EXIST,不存在为EMPTY,删除为DELETE
// 哈希表每个空间给个标记
// EMPTY此位置空, EXIST此位置已经有元素, DELETE元素已经删除
enum State
{
EMPTY, EXIST, DELETE
};
对于查找的话先利用哈希函数获取对应的哈希映射位置,再根据具体情况而进行下一步行为 如果探测的位置状态为空,那么不必比较数据且不用再往后查找 如果探测的位置状态为存在,那么则进行比较数据值,相等则查找到了;不相等则往后根据对应的探测方式继续查找 如果探测的位置状态为删除,那么同样需要继续往后查找,直到找到对应存在的数据或者探测到状态为空的位置就不用再查找了
使用除留余数定制法时,对于扩容后的哈希表对应的哈希函数的除数的值会发生相应的改变,导致下一次查找定制的位置可能不同,所以需要对原来的数据进行再次映射到新的位置上
//比较仿函数-取出类型中的数值
template<class T>
struct HashFunc
{
size_t operator()(const T& key)
{
return key;
}
};
//对string类型特化
template<>
struct HashFunc<string>
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (int i = 0; i < str.size(); i++)
hash = hash * 131 + str[i];//这种方式的冲突概率小
return hash;
}
};
enum State
{
EXIST,
DELETE,
EMPTY
};
//哈希储存的数据类型
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;//缺省值
};
//比较仿函数-取出类型中的数值
template<class T>
struct HashFunc
{
size_t operator()(const T& key)
{
return key;
}
};
//对string类型特化
template<>
struct HashFunc<string>
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (int i = 0; i < str.size(); i++)
hash = hash * 131 + str[i];//这种方式的冲突概率小
return hash;
}
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
HashData<K, V>* Find(const K& key)
{
if (_table.size() == 0)//避免取模0
return nullptr;
Hash hf;
int i = 0;
size_t start = hf(key) % _table.size();//取模size(),使用capacity()可能存到一定位置的空间会使得vector进行自动扩容,不便于控制
size_t index = start;
while (_table[index]._state != EMPTY)
{
if (_table[index]._kv.first == key &&
_table[index]._state == EXIST)//存在且key相等
return &_table[index];
i++;
index = (start + i * i) % _table.size();//二次探测+取模避免越界
}
return nullptr;
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))//避免冗余
return false;
if (_table.size() == 0 || _size * 1.0 / _table.size() >= 0.7)//空哈希或者哈希因子达到一定程序则扩容
{
size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
HashTable<K, V, Hash> newHT;
newHT._table.resize(newsize);//重新开辟足够空间
//重新构建映射
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i]._state == EXIST)
newHT.Insert(_table[i]._kv);
}
_table.swap(newHT._table);//交换地址
}
Hash hf;
int i = 0;
size_t start = hf(kv.first) % _table.size();//取模size()
size_t index = start;
while (_table[index]._state == EXIST)
{
i++;
index = (start + i * i) % _table.size();
}
//找到空或者删除则插入
_table[index]._kv = kv;
_table[index]._state = EXIST;
_size++;
return true;
}
bool Erase(const K& key)
{
auto ret = Find(key);
if (ret == nullptr)
return false;
else
{
ret->_state = DELETE;//伪删除
_size--;
return true;
}
}
size_t Size() const
{
return _size;
}
bool Empty() const
{
return _size == 0;
}
private:
vector<HashData<K, V>> _table;
size_t _size = 0;//记录有效数据个数
};
void TestHashTable1()
{
int a[] = { 5, 3, 100, 9999, 333, 14, 26, 34, 5 };
//int a[] = { 5, 15, 25, 35, 45 };
HashTable<int, int> ht;
for (auto e : a)
{
ht.Insert(make_pair(e, e));
}
ht.Erase(3);
cout << ht.Find(3) << endl;
}
void TestHashTable2()
{
//HashTable<string, string, HashFuncString> dict;
HashTable<string, string> dict;
dict.Insert(make_pair("sort", "排序"));
dict.Insert(make_pair("insert", "插入"));
}
void TestHashTable3()
{
HashTable<int, int> ht1;
int a[] = { 4, 44, 14, 5, 2, 22, 12, 5, 8, 10, 15 };
for (auto e : a)
{
ht1.Insert(make_pair(e, e));
}
ht1.Insert(make_pair(11, 11));
HashTable<int, int> ht2(ht1);
HashTable<int, int> ht;
ht = ht2;
for (size_t i = 0; i < 53; ++i)
{
ht.Insert(make_pair(rand(), i));
}
ht.Insert(make_pair(rand(), 0));
}
开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中
注:开散列中每个桶中放的都是发生哈希冲突的元素
通过哈希函数进行映射到对应的位置,我们的哈希桶选择存的元素是节点地址,那么直接选择头插就好,并不用担心哈希冲突,但是在插入之前需要进行遍历桶节点查看是否存在与插入的值相同的节点,没有才进行头插
通过哈希函数映射到对应的位置,进行对该位置通的遍历再进行删除或查找
桶的个数是一定的,随着元素的不断插入,每个桶中元素的个数不断增多,极端情况下,可能会导致一个桶中链表节点非常多,会影响的哈希表的性能,因此在一定条件下需要对哈希表进行增容 开散列最好的情况是:每个哈希桶中刚好挂一个节点,再继续插入元素时,每一次都会发生哈希冲突,因此,在元素个数刚好等于桶的个数时,可以给哈希表增容 科学增容:除留余数法,最好模一个素数
//获取下一个质数(接近二倍开辟),比较科学减少冲突的取扩容大小的方式
size_t GetNextPrime(size_t prime)
{
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 i = 0;
for (; i < PRIMECOUNT; ++i)
{
if (primeList[i] > prime)
return primeList[i];
}
return primeList[i];
}
//哈希储存的数据类型
template<class K,class V>
struct HashNode
{
pair<K,V> _kv;
HashNode* _next;
HashNode(const pair<K,V>& kv)
:_kv(kv)
, _next(nullptr)
{}
};
//取值比较仿函数及其特化
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (int i = 0; i < str.size(); i++)
{
hash = hash * 131 + str[i];
}
return hash;
}
};
//获取下一个质数(接近二倍开辟),比较科学减少冲突的取扩容大小的方式
size_t GetNextPrime(size_t prime)
{
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 i = 0;
for (; i < PRIMECOUNT; ++i)
{
if (primeList[i] > prime)
return primeList[i];
}
return primeList[i];
}
template<class K, class V, class Hash=HashFunc<K>>
class HashTable
{
typedef HashNode<K,V> Node;
public:
typedef HashTable<K, V, Hash> HT;
HashTable()
:_n(0)
{}
HashTable(const HT& ht)//拷贝构造
:_n(ht._n)
{
if (ht._table.size() == 0)//空栈
return;
_table.resize(ht._table.size(), nullptr);//开辟空间并初始化
for (int i = 0; i < ht._table.size(); i++)//遍历深拷贝
{
Node* cur = ht._table[i];
while (cur)//遍历桶
{
Node* newnode = new Node(cur->_kv);
newnode->_next = _table[i];//头插
_table[i] = newnode;
cur = cur->_next;
}
}
}
HT& operator=(const HT& ht)//赋值重载(现代式)
{
if (&ht != this)
{
HT temp(ht);//拷贝构造
_table.swap(temp._table);
_n = ht._n;
}
return *this;
}
~HashTable()//析构-释放资源
{
for (int i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;//置空
}
_n = 0;
}
bool Insert(const pair<K,V>& kv)
{
Hash hf;
//空哈希或者负载因子达到1时进行扩容
if (_table.size() == _n)
{
//size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
size_t newsize = GetNextPrime(_table.size());//获取新的扩容大小
vector<Node*> newdata;
newdata.resize(newsize, nullptr);//开新的数组并扩容
//将原数组中的节点重新映射插入到新数组
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)//挂有节点
{
Node* next = cur->_next;//记录下一个节点
size_t index = hf(cur->_kv.first) % newsize;//重新计算下标
cur->_next = newdata[index];//头插
newdata[index] = cur;
cur = next;//移动
}
_table[i] = nullptr;//原数组置空
}
_table.swap(newdata);
}
size_t index = hf(kv.first) % _table.size();
Node* cur = _table[index];//遍历查看桶数据知否相等
while (cur)
{
if (cur->_kv.first == kv.first)//相等
return false;
else
cur = cur->_next;
}
//头插
Node* newnode = new Node(kv);
newnode->_next = _table[index];
_table[index] = newnode;
++_n;
return true;
}
Node* Find(const K& key)
{
//空哈希
if (_table.size() == 0)
return nullptr;
Hash hf;
size_t index = hf(key) % _table.size();
Node* cur = _table[index];
while (cur)
{
if (cur->_kv.first == key)
return cur;
else
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
//空哈希
if (_table.size() == 0)
return false;
Hash hf;
size_t index = hf(key) % _table.size();
Node* cur = _table[index];
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first == key)
{
if (parent == nullptr)//头结点进行头删
_table[index] = cur->_next;
else
parent->_next = cur->_next;
delete cur;
--_n;
return true;
}
else
{
parent = cur;
cur = cur->_next;
}
}
return false;
}
private:
vector<Node*> _table;
size_t _n;
};
void TestHashTable1()
{
HashTable<int, int> ht;
int a[] = { 4, 44, 14, 5, 2, 22, 12, 5, 8, 10, 15 };
for (auto e : a)
{
ht.Insert(make_pair(e, e));
}
ht.Insert(make_pair(11, 11));
cout << ht.Find(44) << endl;
ht.Erase(44);
cout << ht.Find(44) << endl;
ht.Erase(2);
}
void TestHashTable2()
{
//HashTable<string, string, HashFuncString> dict;
HashTable<string, string> dict;
dict.Insert(make_pair("sort", "排序"));
dict.Insert(make_pair("insert", "插入"));
dict.Insert(make_pair("erase", "删除"));
}
void TestHashTable3()
{
HashTable<int, int> ht1;
int a[] = { 4, 44, 14, 5, 2, 22, 12, 5, 8, 10, 15 };
for (auto e : a)
{
ht1.Insert(make_pair(e, e));
}
ht1.Insert(make_pair(11, 11));
HashTable<int, int> ht2(ht1);
HashTable<int, int> ht;
ht = ht2;
for (size_t i = 0; i < 53; ++i)
{
ht.Insert(make_pair(rand(), i));
}
ht.Insert(make_pair(rand(), 0));
}
应用链地址法处理溢出,需要增设链接指针,似乎增加了存储开销。事实上: 由于开地址法必须保持大量的空闲空间以确保搜索效率,如二次探查法要求装载因子a <= 0.7,而表项所占空间又比指针大的多,所以使用链地址法反而比开地址法节省存储空间
这里使用哈希桶来封装实现map和set,哈希桶相对于哈希表来说没有哈希冲突,并且效率也十分好
使用哈希封装map/set和使用红黑树来封装的思维具有很多相似的地方
//哈希储存的数据类型
template<class T>
struct HashNode
{
T _data;//对于不同的上层可以存对应的K类型以及pair<K,V>
HashNode* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
//set上层
struct SetOfKey
{
const K& operator()(const K& key)const
{
return key;
}
};
typedef HashNode<K> Node;
typedef HashTable<K, K, Hash, SetOfKey> HT;
//map上层
struct MapOfKey
{
const K& operator()(const pair<K,V>& kv)const
{
return kv.first;
}
};
typedef HashNode<pair<K, V>> Node;
typedef HashTable<K, pair<K, V>, Hash, MapOfKey> HT;
上层封装中实现仿函数,给对应底层哈希传入对应使用的仿函数,便于进行使用对应的函数将储存数据的key继续取出比较
template<class K, class T, class Hash, class KeyOfT>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, Hash, KeyOfT> HT;
typedef HTIterator<K, T, Hash, KeyOfT> Self;
HT* _ht;
Node* _node;
HTIterator(Node* node, HT* ht)//不能加const,与成员变量不匹配
:_ht(ht)
, _node(node)
{}
bool operator==(const Self& s) const;
bool operator!=(const Self& s) const;
T& operator*();
T* operator->();
Self& operator++()
{
if (_node->_next)//存在下个节点
_node = _node->_next;
else//找下一个桶
{
Hash hf;
KeyOfT kot;
size_t index = hf(kot(_node->_data)) % _ht->_table.size();
//kot仿函数为了取出储存类型数据的key,hf仿函数是实现对key类型的取整值,便于进行取模
int i=index+1;
for (; i < _ht->_table.size(); i++)
{
if (_ht->_table[i])
{
_node = _ht->_table[i];
break;
}
}
if (i == _ht->_table.size())//走到最后*
_node = nullptr;
}
return *this;
}
};
template<class K, class T, class Hash, class KeyOfT>
class HashTable
{
typedef HashNode<T> Node;
friend struct HTIterator<K, T, Hash, KeyOfT>;//*
public:
typedef HashTable<K, T, Hash, KeyOfT> HT;
typedef HTIterator<K, T, Hash, KeyOfT> Iterator;
//...
}
注:对于哈希桶来说只有正向迭代器(单向),主要是底层是一个单向的链表,找上个节点地址比较麻烦,对于反向并不是很强求
//前置声明
template<class K, class T, class Hash, class KeyOfT>
class HashTable;
template<class K, class T, class Hash, class KeyOfT>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, Hash, KeyOfT> HT;
typedef HTIterator<K, T, Hash, KeyOfT> Self;
HT* _ht;
Node* _node;
//...
Self& operator++();
};
template<class K, class T, class Hash, class KeyOfT>
class HashTable
{
typedef HashNode<T> Node;
friend struct HTIterator<K, T, Hash, KeyOfT>;//*
public:
typedef HashTable<K, T, Hash, KeyOfT> HT;
typedef HTIterator<K, T, Hash, KeyOfT> Iterator;
Iterator begin()
{
for (int i = 0; i < _table.size(); i++)
{
if (_table[i])
return Iterator(_table[i], this);
}
return Iterator(nullptr, this);
}
Iterator end()
{
return Iterator(nullptr, this);
}
//...
}
#include<iostream>
#include<vector>
#include<string>
using namespace std;
//哈希储存的数据类型
template<class T>
struct HashNode
{
T _data;//对于不同的上层可以存对应的K类型以及pair<K,V>
HashNode* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
//取值比较仿函数及其特化
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (int i = 0; i < str.size(); i++)
{
hash = hash * 131 + str[i];
}
return hash;
}
};
//获取下一个质数(接近二倍开辟)
size_t GetNextPrime(size_t prime)
{
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 i = 0;
for (; i < PRIMECOUNT; ++i)
{
if (primeList[i] > prime)
return primeList[i];
}
return primeList[i];
}
//前置声明
template<class K, class T, class Hash, class KeyOfT>
class HashTable;
template<class K, class T, class Hash, class KeyOfT>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, Hash, KeyOfT> HT;
typedef HTIterator<K, T, Hash, KeyOfT> Self;
HT* _ht;
Node* _node;
HTIterator(Node* node, HT* ht)//不能加const,与成员变量不匹配
:_ht(ht)
, _node(node)
{}
bool operator==(const Self& s) const
{
return _node == s._node;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next)
_node = _node->_next;
else//找下一个桶
{
Hash hf;
KeyOfT kot;
size_t index = hf(kot(_node->_data)) % _ht->_table.size();
int i=index+1;
for (; i < _ht->_table.size(); i++)
{
if (_ht->_table[i])
{
_node = _ht->_table[i];
break;
}
}
if (i == _ht->_table.size())//走到最后*
_node = nullptr;
}
return *this;
}
};
template<class K, class T, class Hash, class KeyOfT>
class HashTable
{
typedef HashNode<T> Node;
friend struct HTIterator<K, T, Hash, KeyOfT>;//*
public:
typedef HashTable<K, T, Hash, KeyOfT> HT;
typedef HTIterator<K, T, Hash, KeyOfT> Iterator;
HashTable()
:_n(0)
{}
Iterator begin()
{
for (int i = 0; i < _table.size(); i++)
{
if (_table[i])
return Iterator(_table[i], this);
}
return Iterator(nullptr, this);
}
Iterator end()
{
return Iterator(nullptr, this);
}
HashTable(const HT& ht)//拷贝构造
:_n(ht._n)
{
if (ht._table.size() == 0)
return;
KeyOfT kot;
_table.resize(ht._table.size(), nullptr);
for (int i = 0; i < ht._table.size(); i++)
{
Node* cur = ht._table[i];
while (cur)
{
Node* newnode = new Node(cur->_kv);
newnode->_next = _table[i];
_table[i] = newnode;
cur = cur->_next;
}
}
}
HT& operator=(const HT& ht)
{
if (&ht != this)
{
HT temp(ht);
_table.swap(temp._table);
_n = ht._n;
}
return *this;
}
~HashTable()
{
for (int i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;//置空
}
_n = 0;
}
pair<Iterator,bool> Insert(const T& data)
{
Hash hf;
KeyOfT kot;
//空哈希或者负载因子达到1
if (_table.size() == _n)
{
size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
//size_t newsize = GetNextPrime(_table.size());//获取新大小
vector<Node*> newdata;
newdata.resize(newsize, nullptr);//开新的数组并扩容
//将原数组中的节点重新插入到新数组
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];//遍历数组
while (cur)//挂有节点
{
Node* next = cur->_next;//记录下一个节点
size_t index = hf(kot(cur->_data)) % newsize;//重新计算下标
//头插到新位置
cur->_next = newdata[index];
newdata[index] = cur;
cur = next;//移动
}
_table[i] = nullptr;
}
_table.swap(newdata);
}
//遍历查找
size_t index = hf(kot(data)) % _table.size();
Node* cur = _table[index];
while (cur)
{
if (kot(cur->_data) == kot(data))
return make_pair(Iterator(cur,this),false);
else
cur = cur->_next;
}
//头插
Node* newnode = new Node(data);
newnode->_next = _table[index];
_table[index] = newnode;
++_n;
return make_pair(Iterator(newnode,this),true);
}
Node* Find(const K& key)
{
//空哈希
if (_table.size() == 0)
return nullptr;
Hash hf;
KeyOfT kot;
size_t index = hf(key) % _table.size();
Node* cur = _table[index];
while (cur)
{
if (kot(cur->_data) == key)
return cur;
else
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
//空哈希
if (_table.size() == 0)
return false;
Hash hf;
KeyOfT kot;
size_t index = hf(key) % _table.size();
Node* cur = _table[index];
Node* parent = nullptr;
while (cur)
{
if (kot(cur->_data) == key)
{
if (parent == nullptr)//头结点
_table[index] = cur->_next;
else
parent->_next = cur->_next;
delete cur;
--_n;
return true;
}
else
{
parent = cur;
cur = cur->_next;
}
}
return false;
}
private:
vector<Node*> _table;
size_t _n=0;
};
只需要在底层哈希桶的接口以及迭代器的接口,进行进一步的封装接口,便于外部进行调用
namespace cole
{
template<class K,class V,class Hash=HashFunc<K>>
class unordered_map
{
struct MapOfKey
{
const K& operator()(const pair<K,V>& kv)const
{
return kv.first;
}
};
typedef HashNode<pair<K, V>> Node;
public:
typedef HashTable<K, pair<K, V>, Hash, MapOfKey> HT;
typedef typename HT::Iterator iterator;
//获取类型中的类型需要加typename进行修饰,告诉编译器在实例化后进行查找对应的类型
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator,bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
V& operator[](const K& key)
{
auto ret = insert(make_pair(key, V()));
return ret.first->second;
}
Node* find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
HT _ht;
};
void test_unordered_map()
{
unordered_map<int, int> map;
int arr[] = { 1,2,22,34,3,4,54,4,2,6,18,48,56,16,45,16,23,156,49,153,45,81,6,6,16,16,151,84894,11,6 };
for (auto e : arr)
{
map.insert(make_pair(e, e));
}
for (auto& e : map)
{
cout << e.first << ":" << e.second << endl;
}
map[56] = 11;
auto ret = map.find(4);
cout << ret << endl;
cout << map[4] << endl;
map.erase(4);
cout << map[4] << endl;
cout << map[56] << endl;
for (auto e : arr)
{
map.erase(e);
}
for (auto& e : map)
{
cout << e.first << ":" << e.second << endl;
}
}
}
同样的对于set来说,也只需要在底层哈希桶的接口以及迭代器的接口,进行进一步的封装接口,便于外部进行调用
namespace cole
{
template<class K , class Hash = HashFunc<K>>
class unordered_set
{
struct SetOfKey
{
const K& operator()(const K& key)const
{
return key;
}
};
typedef HashNode<K> Node;
public:
typedef HashTable<K, K, Hash, SetOfKey> HT;
typedef typename HT::Iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator, bool> insert(const K& key)
{
return _ht.Insert(key);
}
/*V& operator[](const K& key)
{
auto ret = insert(make_pair(key, V()));
return ret.first->second;
}*/
Node* find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
HT _ht;
};
void test_unordered_set()
{
unordered_set<int> set;
int arr[] = { 1,2,22,34,3,4,54,4,2,6,18,48,56,16,45,16,23,156,49,153,45,81,6,6,16,16,151,84894,11,6 };
for (auto e : arr)
{
set.insert(e);
}
for (auto& e : set)
{
cout << e << endl;
}
auto ret = set.find(4);
cout << ret << endl;
set.erase(4);
for (auto& e : set)
{
cout << e << endl;
}
for (auto e : arr)
{
set.erase(e);
}
for (auto& e : set)
{
cout << e<< endl;
}
}
}
namespace cole
{
template<class K , class Hash = HashFunc<K>>
class unordered_set
{
struct SetOfKey
{
const K& operator()(const K& key)const
{
return key;
}
};
typedef HashNode<K> Node;
public:
typedef HashTable<K, K, Hash, SetOfKey> HT;
typedef typename HT::Iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator, bool> insert(const K& key)
{
return _ht.Insert(key);
}
/*V& operator[](const K& key)
{
auto ret = insert(make_pair(key, V()));
return ret.first->second;
}*/
Node* find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
HT _ht;
};
void test_unordered_set()
{
unordered_set<int> set;
int arr[] = { 1,2,22,34,3,4,54,4,2,6,18,48,56,16,45,16,23,156,49,153,45,81,6,6,16,16,151,84894,11,6 };
for (auto e : arr)
{
set.insert(e);
}
for (auto& e : set)
{
cout << e << endl;
}
auto ret = set.find(4);
cout << ret << endl;
set.erase(4);
for (auto& e : set)
{
cout << e << endl;
}
for (auto e : arr)
{
set.erase(e);
}
for (auto& e : set)
{
cout << e<< endl;
}
}
}