引入:
顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(
l
o
g
2
N
log_2 N
log2?N),搜索的效率取决于搜索过程中元素的比较次数。
尽管平衡二叉搜索树的查找方式已经很快了,但我们仍然认为该方法不够极致,理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。
如果构造一种存储结构,通过某种函数(HashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。
当向该结构中:
该方式即为哈希方法(或散列法),哈希方法中使用的转换函数称为哈希函数(或散列函数),构造出来的结构称为哈希表(Hash Table)(或散列表)
[!Example] 例如:数据集合{1,7,6,4,5,9};
哈希函数设置为:hash(key) = key % capacity
(capacity为存储元素底层空间总的大小)
用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快
问题:按照上述哈希方式,向集合中插入元素44,会出现什么问题?发现该位置已经有元素,这就是哈希冲突。
对于两个数据元素的关键字
k
i
k_i
ki?和
k
j
k_j
kj? (i != j),有
k
i
k_i
ki? !=
k
j
k_j
kj?
但有:Hash(
k
i
k_i
ki?) == Hash(
k
j
k_j
kj?)
即:不同关键字通过相同哈希函数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。
哈希冲突指的是:不同的输入数据经过哈希函数计算后,产生了相同的哈希值。当两个或多个不同的输入数据生成相同的哈希值时,就发生了哈希冲突。
由于哈希函数将无限的输入域映射到有限的输出域,所以在理论上,哈希冲突是不可避免的。好的哈希函数应该尽量减少哈希冲突的概率,使其发生的概率非常低。如果哈希冲突的概率过高,将会降低哈希函数的效率和可靠性,因为哈希冲突可能会导致数据的错误匹配或冲突。
引起哈希冲突的一个原因可能是:哈希函数设计不够合理
直接定址法 (常用)
取关键字的某个线性函数为散列地址:
H
a
s
h
(
K
e
y
)
=
A
?
K
e
y
+
B
Hash(Key)= A*Key + B
Hash(Key)=A?Key+B
优点:简单、均匀
缺点:需要事先知道关键字的分布情况
使用场景:适合查找比较小且连续的情况
下面这道题是哈希直接定址法的典型例子:387. 字符串中的第一个唯一字符 - 力扣(LeetCode)
class Solution
{
public:
int firstUniqChar(string s)
{
int countA[26]={0};
for(auto ch:s)
{
countA[ch-'a']++;
}
for(int i=0;i<s.size();i++)
{
if(countA[s[i]-'a']==1)
{
return i;
}
}
return -1;
}
};
除留余数法 (常用)
设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:
H
a
s
h
(
k
e
y
)
=
k
e
y
(
m
o
d
)
p
Hash(key) = key (mod) p
Hash(key)=key(mod)p,(其中 mod 是取余操作),将关键码转换成哈希地址
平方取中法 (了解)
哈希函数:
H
a
s
h
(
k
e
y
)
=
(
k
e
y
2
>
>
r
)
Hash(key)=(key^2>>r)
Hash(key)=(key2>>r) 按位与 (m?1)
(其中 >> 是右移操作,r 是一个常数,通常选取为关键字位数的一半)
假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址;
再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况
折叠法 (了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况
随机数法 (了解)
选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数函数。
通常应用于关键字长度不等时采用此法
数学分析法 (了解)
设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。例如:
假设要存储某家公司员工登记表,如果用手机号作为关键字,那么极有可能前7位都是 相同的,那么我们可以选择后面的四位作为散列地址,如果这样的抽取工作还容易出现 冲突,还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。
数字分析法通常适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的若干位分布较均匀的情况
注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突
闭散列也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去;那如何寻找下一个空位置呢?有两种方法 – 线性探测法和二次探测法。
线性探测是从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止
#pragma once
#include <vector>
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// 闭散列
namespace chen
{
enum Status
{
EMPTY,
EXIST,
DELETE
};
template<class K,class V>
struct HashData
{
pair<K, V> _kv;
Status _s; //状态
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
HashTable()
{
_tables.resize(10);
}
// 插入
bool Insert(const std::pair<K, V>& kv) { ... }
// 查找
HashData<K,V>* Find(const K& key) { ... }
// 删除
bool Erase(const K& key) { ... }
void Print()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._s == EXIST)
{
cout << "[" << i << "]->" << _tables[i]._kv.first
<< ":" << _tables[i]._kv.second << endl;
}
else if (_tables[i]._s == EMPTY)
{
printf("[%ud]->\n", i);
}
else
{
printf("[%ud]->D\n", i);
}
}
cout << endl;
}
private:
std::vector<HashData<K,V>> _tables;
size_t _n = 0; // 存储的关键字个数
};
void TestHT1()
{
chen::HashTable<int, int> ht;
int a[] = { 42,45,345,4,37,45,23 };
for (auto e : a)
{
ht.Insert(std::make_pair(e, e));
}
ht.Print();
ht.Insert(std::make_pair(42, 42));
ht.Print();
ht.Erase(42);
ht.Erase(45);
ht.Print();
}
void TestHT2()
{
string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
//HashTable<string, int, HashFuncString> ht;
HashTable<string, int, HashFunc<string>> ht;
for (auto& e : arr)
{
//auto ret = ht.Find(e);
HashData<string, int>* ret = ht.Find(e);
if (ret)
{
ret->_kv.second++;
}
else
{
ht.Insert(make_pair(e, 1));
}
}
ht.Print();
ht.Insert(make_pair("apple", 1));
ht.Insert(make_pair("sort", 1));
ht.Insert(make_pair("abc", 1));
ht.Insert(make_pair("acb", 1));
ht.Insert(make_pair("aad", 1));
ht.Print();
}
}
bool Insert(const std::pair<K, V>& kv)
{
if (Find(kv.first))
{
return false; // 如果关键字已存在,则返回false
}
// 负载因子_n/size == 0.7 就扩容
if (_n * 10 / _tables.size() == 7)
{
size_t newSize = _tables.size() * 2;
HashTable<K, V, Hash> newHT;
newHT._tables.resize(newSize);
// 遍历旧表,将数据插入新表
for (size_t i = 0;i < _tables.size();i++)
{
if (_tables[i]._s == EXIST)
{
newHT.Insert(_tables[i]._kv);
}
}
_tables.swap(newHT._tables); // 交换旧表和新表
}
Hash hf;
// 线性探测,找到合适的位置插入数据
size_t hashi = hf(kv.first) % _tables.size();
while (_tables[hashi]._s == EXIST)
{
hashi++;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv; // 插入数据
_tables[hashi]._s = EXIST; // 设置状态为存在
++_n; // 更新关键字个数
return true; // 插入成功,返回true
}
HashData<K,V>* Find(const K& key)
{
Hash hf;
size_t hashi = hf(key) % _tables.size();
while (_tables[hashi]._s != EMPTY)
{
if (_tables[hashi]._s==EXIST
&& _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
hashi++;
hashi %= _tables.size();
}
return NULL;
}
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_s = DELETE;
--_n;
return true;
}
else
{
return false;
}
}
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// 原始写法
struct HashFuncString
{
size_t operator()(const string& key)
{
// BKDR方法
size_t hash = 0;
for (auto ch : key)
{
hash *= 31;
hash += ch;
}
return hash;
}
};
// 模板特化写法
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
// BKDR方法
size_t hash = 0;
for (auto ch : key)
{
hash *= 31;
hash += ch;
}
return hash;
}
};
线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为: H i H_i Hi? = ( H 0 H_0 H0? + i 2 i^2 i2 )% m, 或者: H i H_i Hi? = ( H 0 H_0 H0? - i 2 i^2 i2 )% m。其中:i =1,2,3…, H 0 H_0 H0?是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。
研究表明:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a不超过0.5,如果超出必须考虑增容。
开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中,如图:
从上图可以看出,开散列中每个桶中放的都是发生哈希冲突的元素。
namespace HashBucket
{
template<class K, class V>
struct HashNode
{
HashNode<K, V>* _next;
pair<K, V> _kv;
HashNode(const pair<K, V>& kv)
:_next(nullptr)
, _kv(kv)
{}
};
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return key;
}
};
// 特化
template<>
struct HashFunc<string>
{
// BKDR
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 31;
}
return hash;
}
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
~HashTable()
{
for (auto& cur : _tables)
{
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
cur = nullptr;
}
}
Node* Find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
Hash hash;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
Hash hash;
size_t hashi = hash(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
size_t GetNextPrime(size_t prime)
{
// SGI
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
size_t i = 0;
for (; i < __stl_num_primes; ++i)
{
if (__stl_prime_list[i] > prime)
return __stl_prime_list[i];
}
return __stl_prime_list[i];
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
Hash hash;
// 负载因因子==1时扩容
if (_n == _tables.size())
{
size_t newsize = GetNextPrime(_tables.size());
vector<Node*> newtables(newsize, nullptr);
for (auto& cur : _tables)
{
while (cur)
{
Node* next = cur->_next;
size_t hashi = hash(cur->_kv.first) % newtables.size();
// 头插到新表
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
}
_tables.swap(newtables);
}
size_t hashi = hash(kv.first) % _tables.size();
// 头插
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
size_t MaxBucketSize()
{
size_t max = 0;
for (size_t i = 0; i < _tables.size(); ++i)
{
auto cur = _tables[i];
size_t size = 0;
while (cur)
{
++size;
cur = cur->_next;
}
//printf("[%d]->%d\n", i, size);
if (size > max)
{
max = size;
}
}
return max;
}
private:
vector<Node*> _tables; // 指针数组
size_t _n = 0; // 存储有效数据个数
};
void TestHT2()
{
string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
HashTable<string, int, HashFunc<string>> ht;
for (auto& e : arr)
{
//auto ret = ht.Find(e);
HashNode<string, int>* ret = ht.Find(e);
if (ret)
{
ret->_kv.second++;
}
else
{
ht.Insert(make_pair(e, 1));
}
}
}
}
unordered_map 是存储 <key, value> 键值对的关联式容器,其允许通过 key 快速的索引到与其对应的value – 计算出余数找到下标位置。
在 unordered_map 中,键值通常用于惟一地标识元素,而映射值是一个对象,其内容与此键关联。键和映射值的类型可能不同。
在内部, unordered_map 没有对 <kye, value> 按照任何特定的顺序排序, 为了能在常数范围内找到 key 所对应的 value, unordered_map 将相同哈希值的键值对放在相同的桶中 – 开散列解决哈希冲突。
unordered_map 容器通过 key 访问单个元素要比 map 快,但它在遍历元素子集的范围迭代方面效率较低。
unordered_map 也重载了直接访问操作符 (operator[]),它允许使用 key 作为参数直接访问 value。
unordered_map 的迭代器是一个单向迭代器 – 哈希桶的结构是单链表。
测试:
#include <iostream>
#include <unordered_map>
int main()
{
// (constructor) 构造函数
std::unordered_map<int, std::string> myMap;
// (insert) 插入元素
myMap.insert({1, "One"});
myMap.insert({2, "Two"});
myMap.insert({3, "Three"});
// (constructor) 通过范围构造函数
std::unordered_map<int, std::string> rangeMap(myMap.begin(), myMap.end());
// (constructor) 通过初始化列表构造函数
std::unordered_map<int, std::string> initListMap = {{4, "Four"}, {5, "Five"}, {6, "Six"}};
// (empty) 测试容器是否为空
std::cout << "Is map empty? " << (myMap.empty() ? "Yes" : "No") << std::endl;
// (size) 返回容器大小
std::cout << "Size of map: " << myMap.size() << std::endl;
// (find) 查找元素
auto it = myMap.find(2);
if (it != myMap.end()) {
std::cout << "Element with key 2 found in map: " << it->second << std::endl;
}
// (count) 计算特定键的元素数量
int count = myMap.count(3);
std::cout << "Number of elements with key 3: " << count << std::endl;
// (emplace) 构造并插入元素
myMap.emplace(7, "Seven");
// (erase) 删除元素
myMap.erase(1);
// (clear) 清空容器
myMap.clear();
// (hash_function) 获取哈希函数
std::hash<int> hashFunction = myMap.hash_function();
// (key_eq) 获取键的等价比较谓词
auto keyEqual = myMap.key_eq();
// (get_allocator) 获取分配器
auto allocator = myMap.get_allocator();
// (constructor) 拷贝构造函数
std::unordered_map<int, std::string> copyMap(rangeMap);
// (operator=) 赋值运算符
std::unordered_map<int, std::string> assignedMap = initListMap;
// (emplace_hint) 构造并插入元素带有提示位置
auto hint = assignedMap.begin();
assignedMap.emplace_hint(hint, 10, "Ten");
// (swap) 交换内容
myMap.swap(assignedMap);
// (begin) 返回迭代器指向开头
for (auto iter = myMap.begin(); iter != myMap.end(); ++iter) {
std::cout << "Key: " << iter->first << ", Value: " << iter->second << std::endl;
}
// (cbegin) 返回 const 迭代器指向开头
for (auto iter = myMap.cbegin(); iter != myMap.cend(); ++iter) {
std::cout << "Key: " << iter->first << ", Value: " << iter->second << std::endl;
}
// (bucket_count) 返回桶的数量
std::cout << "Bucket count: " << myMap.bucket_count() << std::endl;
// (max_bucket_count) 返回最大桶的数量
std::cout << "Max bucket count: " << myMap.max_bucket_count() << std::endl;
// (bucket) 返回元素的桶号
std::cout << "Bucket for key 2: " << myMap.bucket(2) << std::endl;
// (bucket_size) 返回桶中元素的数量
std::cout << "Bucket size for key 2: " << myMap.bucket_size(myMap.bucket(2)) << std::endl;
// (load_factor) 返回当前负载因子
std::cout << "Load factor: " << myMap.load_factor() << std::endl;
// (max_load_factor) 获取或设置最大负载因子
std::cout << "Max load factor: " << myMap.max_load_factor() << std::endl;
myMap.max_load_factor(0.7);
// (rehash) 设置桶的数量
myMap.rehash(10);
// (reserve) 请求容器容量变化
myMap.reserve(20);
return 0;
}
unordered_set 和 unordered_map 的区别再于 unordered_set 是 K模型 的容器,而 unordered_map 是 KV模型 的容器,虽然二者底层都是开散列的哈希表,但是哈希表中每个节点的 data 的类型是不同的 – unordered_set 是单纯的 key,而 unordered_map 是 KV 构成的键值对,只是 哈希表 通过 KeyOfT 仿函数使得自己能够兼容 K模型 的 unordered_set 和 KV模型 的 unordered_map 而已。
unordered_set 和 unordered_map 的功能与要求基本一样:
与 unordered_map 为数不多的不同的地方在于,unordered_set 不需要修改 value,所以也就不支持 operator[] 函数;
测试:
int main()
{
// (constructor) 构造函数
std::unordered_set<int> mySet;
// (insert) 插入元素
mySet.insert(1);
mySet.insert(2);
mySet.insert(3);
// (constructor) 通过范围构造函数
int arr[] = { 4, 5, 6 };
std::unordered_set<int> rangeSet(arr, arr + 3);
// (constructor) 通过初始化列表构造函数
std::unordered_set<int> initListSet = { 7, 8, 9 };
// (empty) 测试容器是否为空
std::cout << "Is set empty? " << (mySet.empty() ? "Yes" : "No") << std::endl;
// (size) 返回容器大小
std::cout << "Size of set: " << mySet.size() << std::endl;
// (find) 查找元素
auto it = mySet.find(2);
if (it != mySet.end()) {
std::cout << "Element 2 found in set." << std::endl;
}
// (count) 计算特定键的元素数量
int count = mySet.count(3);
std::cout << "Number of elements with key 3: " << count << std::endl;
// (emplace) 构造并插入元素
mySet.emplace(4);
// (erase) 删除元素
mySet.erase(1);
// (clear) 清空容器
mySet.clear();
// (hash_function) 获取哈希函数
std::hash<int> hashFunction = mySet.hash_function();
// (key_eq) 获取键的等价比较谓词
auto keyEqual = mySet.key_eq();
// (get_allocator) 获取分配器
auto allocator = mySet.get_allocator();
// (constructor) 拷贝构造函数
std::unordered_set<int> copySet(rangeSet);
// (operator=) 赋值运算符
std::unordered_set<int> assignedSet = initListSet;
// (emplace_hint) 构造并插入元素带有提示位置
auto hint = assignedSet.begin();
assignedSet.emplace_hint(hint, 10);
// (swap) 交换内容
mySet.swap(assignedSet);
// (begin) 返回迭代器指向开头
for (auto iter = mySet.begin(); iter != mySet.end(); ++iter) {
std::cout << *iter << " ";
}
std::cout << std::endl;
// (cbegin) 返回 const 迭代器指向开头
for (auto iter = mySet.cbegin(); iter != mySet.cend(); ++iter) {
std::cout << *iter << " ";
}
std::cout << std::endl;
// (bucket_count) 返回桶的数量
std::cout << "Bucket count: " << mySet.bucket_count() << std::endl;
// (max_bucket_count) 返回最大桶的数量
std::cout << "Max bucket count: " << mySet.max_bucket_count() << std::endl;
// (bucket) 返回元素的桶号
std::cout << "Bucket for key 2: " << mySet.bucket(2) << std::endl;
// (bucket_size) 返回桶中元素的数量
std::cout << "Bucket size for key 2: " << mySet.bucket_size(mySet.bucket(2)) << std::endl;
// (load_factor) 返回当前负载因子
std::cout << "Load factor: " << mySet.load_factor() << std::endl;
// (max_load_factor) 获取或设置最大负载因子
std::cout << "Max load factor: " << mySet.max_load_factor() << std::endl;
mySet.max_load_factor(0.7);
// (rehash) 设置桶的数量
mySet.rehash(10);
// (reserve) 请求容器容量变化
mySet.reserve(20);
return 0;
}
和 multimap 和 map 的区别一样,unordered_multimap 和 unordered_map 的区别在于 unordered_multimap 中允许出现重复元素,所以 unordered_multimap 中 count 用来计算 哈希表 中同一 key 值的元素的数量比较方便,但 unordered_multimap 也因此不再支持 operator[] 运算符重载,其他的地方都差不多,对细节有疑惑的建议查阅官方文档 unordered_multimap - C++ Reference (cplusplus.com)
unordered_multiset 也一样,与 unordered_set 不同的地方在于其允许出现重复元素:unordered_set - C++ Reference (cplusplus.com)
为了使哈希表能够同时封装 KV模型的 unordered_map 和 K模型的 unordered_set,哈希表不能将节点的数据类型直接定义为 pair<K, V>,而是需要通过参数 T 来确定
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// HashFunc的模板特化
// 原因:不存在string类到size_t的显示类型转换
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
// BKDR
size_t hash = 0;
for (auto e : key)
{
hash *= 31;
hash += e;
}
return hash;
}
};
namespace hash_bucket
{
// 哈希表节点
template<class T>
struct HashNode
{
HashNode<T>* _next;
T _data;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
// 这里前置声明HashTable是因为在下面迭代器的定义里要用到HashTable这个类名(相互引用)
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
// K :Key的类型
// T :T的类型(set就放key的类型,map就放std::pair(key,value))迭代器封装的就是T类型的对象
// Ref :T的引用类型
// Ptr :T的指针类型
// KeyOfT:用来取出T中的key的仿函数类型,因为T不一定是纯key,如果存放pair,要从中取出key
// Hash :用来把key转换成size_t的仿函数类,就是算key的哈希值
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct __HTIterator
{
typedef HashNode<T> Node;
typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
public:
Node* _node; // 哈希表节点指针
size_t _hashi; // 哈希桶编号
const HashTable<K, T, KeyOfT, Hash>* _pht; // 哈希表指针 为什么是const???
public:
__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
:_node(node)
, _pht(pht)
, _hashi(hashi)
{}
__HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
:_node(node)
, _pht(pht)
, _hashi(hashi)
{}
Self& operator++()
{
if (_node->_next != nullptr)
{
// 当前桶还有节点,走到下一个节点
_node = _node->_next;
}
else
{
// 当前桶已经走完了,从下一个桶开始找
++_hashi;
while (_hashi < _pht->_tables.size())
{
if (_pht->_tables[_hashi])
{
_node = _pht->_tables[_hashi];
break;
}
++_hashi;
}
if (_hashi == _pht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node; // 迭代器不等,就是节点指针不等
}
};
// unordered_set -> Hashtable<K, K>
// unordered_map -> Hashtable<K, pair<K, V>>
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
public:
typedef HashNode<T> Node;
typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
// 友元类声明
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
friend struct __HTIterator;
public:
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return iterator(_tables[i], this, i);
}
}
return end(); // 遍历完发现没有元素,返回一个尾后迭代器
}
iterator end()
{
// 尾后迭代器,是一个无效迭代器
return iterator(nullptr, this, -1);
}
const_iterator begin() const
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return const_iterator(_tables[i], this, i);
}
}
return end();
}
const_iterator end() const
{
// this的类型:const HashTable<K, T, KeyOfT, Hash>*
return const_iterator(nullptr, this, -1);
}
HashTable()
{
_tables.resize(10);
}
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
// bool用来标记是否开辟新节点
// 待插入数据已存在:false
// 待插入数据不存在:ture
std::pair<iterator, bool> Insert(const T& data)
{
Hash hf;
KeyOfT kot;
iterator it = Find(kot(data));
if (it != end())
{
return std::make_pair(it, false);
}
// 负载因子最大到1 ,到1扩容
if (_n == _tables.size())
{
vector<Node*> newTables;
newTables.resize(_tables.size() * 2, nullptr);
// 遍历旧表
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next; // 旧的哈希桶(链表)的头节点的下一个先存着
// 把旧的节点映射到新表
size_t hashi = hf(kot(cur->_data)) % newTables.size();
cur->_next = newTables[i];
newTables[hashi] = cur;
cur = next; // 迭代
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t hashi = hf(kot(data)) % _tables.size();
Node* newnode = new Node(data);
// 头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return std::make_pair(iterator(newnode, this, hashi), true);
}
iterator Find(const K& key)
{
Hash hf;
KeyOfT kot;
size_t hashi = hf(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur, this, hashi);
}
cur = cur->_next;
}
return end();
}
bool Erase(const K& key)
{
Hash hf;
KeyOfT kot;
size_t hashi = hf(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
void Some()
{
size_t bucketCount = 0; // 哈希桶数量
size_t maxBucketLen = 0; // 最大哈希桶(链表)长度
size_t sum = 0; // 总节点数
double averageBucketLen = 0; // 平均桶长度
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
++bucketCount;
}
size_t bucketLen = 0;
while (cur)
{
++bucketLen;
cur = cur->_next;
}
sum += bucketLen;
if (bucketLen > maxBucketLen)
{
maxBucketLen = bucketLen;
}
}
averageBucketLen = (double)sum / (double)bucketCount;
printf("all bucketSize:%d\n", _tables.size());
printf("bucketSize:%d\n", bucketCount);
printf("maxBucketLen:%d\n", maxBucketLen);
printf("averageBucketLen:%lf\n\n", averageBucketLen);
}
private:
std::vector<Node*> _tables;
size_t _n = 0;
};
namespace chen
{
// 外层是<key,value>
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
// 提取T中的key的仿函数类
struct MapKeyOfT
{
const K& operator()(const std::pair<K, V>& kv)
{
return kv.first;
}
};
public:
// 去HashTable里面拿HashTable的迭代器 作unordered_map的迭代器
// 这里迭代器里封装的是pair<const K, V>
typedef typename hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
typedef typename hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
std::pair<iterator, bool> insert(const std::pair<K, V>& kv)
{
return _ht.Insert(kv);
}
V& operator[](const K& key)
{
std::pair<iterator, bool> ret = _ht.Insert(std::make_pair(key, V()));
return ret.first->second;
}
const V& operator[](const K& key) const
{
std::pair<iterator, bool> ret = _ht.Insert(std::make_pair(key, V()));
return ret.first->second;
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}
namespace chen
{
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;
const_iterator begin() const
{
return _ht.begin();
}
const_iterator end() const
{
return _ht.end();
}
std::pair<const_iterator, bool> insert(const K& key)
{
auto ret = _ht.Insert(key);
return pair<const_iterator, bool>(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
};
}
https://gitee.com/chenzhuowen4384/My_STL