目录
四、unordered系列关联式容器（以unordered_map为例）
引言
在计算机科学领域，哈希是一种非常重要的数据结构和算法思想，广泛应用于各种场景，如关联式容器、海量数据处理等。本文将深入探讨哈希的相关知识，包括哈希函数、哈希冲突及其解决方法，还会结合C++代码实现进行详细说明。
一、哈希概念
哈希的基本原理
在顺序结构和平衡树中，元素关键码与其存储位置之间没有直接对应关系，查找元素时往往需要多次比较关键码。而哈希结构通过哈希函数（hashFunc），让元素的存储位置与关键码建立映射关系，这样在查找元素时，能直接通过哈希函数快速定位，大大提高了查找效率。
例如，对于数据集合{1, 7, 6, 4, 5, 9} ，设定哈希函数为 hash(key) = key % capacity （这里 capacity 为10 ）。那么：
- hash(1) = 1%10 = 1
- hash(7) = 7%10 = 7
- hash(6) = 6%10 = 6
- hash(4) = 4%10 = 4
- hash(5) = 5%10 = 5
- hash(9) = 9%10 = 9
哈希冲突
当不同的关键码通过相同的哈希函数计算出相同的哈希地址时，就会发生哈希冲突。比如，若要插入元素44 ，按照上述哈希函数 hash(44) = 44%10 = 4 ，而位置4 已经被元素4 占据，这就产生了冲突。
二、哈希函数
哈希函数设计原则
1. 定义域覆盖：哈希函数的定义域必须涵盖需要存储的全部关键码。若散列表允许有 m 个地址，其值域应在0到 m - 1 之间。
2. 地址均匀分布：计算出的地址能均匀分布在整个空间中，这样可以减少冲突的发生。
3. 简单性：哈希函数应尽量简单，以提高计算效率。
常见哈希函数
1. 直接定址法
- 原理：取关键字的某个线性函数为散列地址，公式为 Hash(Key) = A*Key + B 。
- 优点：简单、均匀。
- 缺点：需要事先知道关键字的分布情况。
- 使用场景：适合查找比较小且连续的情况。
- C++示例代码：
// 简单示例，假设A = 1, B = 0
size_t DirectAddressHash(int key) {
return key;
}2. 除留余数法
- 原理：设散列表允许的地址数为 m ，取一个不大于 m ，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数 Hash(key) = key % p (p<=m) 将关键码转换成哈希地址。
- 优点：常用且简单有效。
- 缺点：选择合适的质数 p 很关键。
- C++示例代码：
size_t RemainderHash(int key, int m) {
// 假设已经获取到合适的质数p
int p = GetAppropriatePrime(m);
return key % p;
}3. 平方取中法
- 原理：假设关键字为1234 ，对它平方就是1522756 ，抽取中间的3位227作为哈希地址；再比如关键字为4321 ，对它平方就是18671041 ，抽取中间的3位671(或710)作为哈希地址 。
- 优点：适合不知道关键字的分布，而位数又不是很大的情况 。
- 缺点：计算相对复杂。
- C++示例代码：
size_t MidSquareHash(int key) {
long long square = (long long)key * key;
// 假设取中间3位，这里根据实际情况调整
int mid = (square / 100) % 1000;
return mid;
}4. 折叠法
- 原理：将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址 。
- 优点：适合事先不需要知道关键字的分布，适合关键字位数比较多的情况 。
- 缺点：可能会导致分布不均匀。
- C++示例代码：
size_t FoldHash(const string& key, int tableSize) {
size_t sum = 0;
int partSize = 4; // 假设每部分4位，可调整
for (size_t i = 0; i < key.size(); i += partSize) {
size_t part = 0;
for (int j = 0; j < partSize && i + j < key.size(); ++j) {
part = part * 10 + (key[i + j] - '0');
}
sum += part;
}
return sum % tableSize;
}5. 随机数法
- 原理：选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 H(key) = random(key) ，其中 random 为随机函数 。
- 优点：适用于关键字长度不等时 。
- 缺点：随机性可能导致分布不佳。
- C++示例代码：
size_t RandomHash(int key) {
srand(static_cast<unsigned int>(time(nullptr)));
return rand() % 100; // 假设哈希表大小为100，可调整
}6. 数学分析法
- 原理：设有 n 个 d 位数，每一位可能有 r 种不同的符号，这 r 种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址 。
- 优点：针对特定数据分布有较好效果。
- 缺点：需要分析数据特征。
- C++示例代码：略（因具体实现依赖数据特征分析）
三、哈希冲突解决方法
闭散列（开放定址法）
当发生哈希冲突时，如果哈希表未被装满，就把 key 存放到冲突位置中的“下一个”空位置中。寻找下一个空位置的方式有多种，这里介绍线性探测和二次探测。
线性探测
- 原理：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
- 插入示例：比如要插入元素44 ，哈希地址为4 ，但位置4 已被占用，就依次探测位置5、6、7等，直到找到空位置插入。
- 删除注意事项：不能直接物理删除哈希表中已有的元素，否则会影响其他元素的搜索，一般采用标记的伪删除法。
- C++代码实现：
template<class K, class V>
class HashTable {
struct Elem {
pair<K, V> _val;
State _state = EMPTY;
};
public:
bool Insert(const pair<K, V>& val) {
_CheckCapacity();
size_t hashAddr = HashFunc(val.first);
size_t startAddr = hashAddr;
while (_ht[hashAddr]._state != EMPTY) {
if (_ht[hashAddr]._state == EXIST && _ht[hashAddr]._val.first == val.first)
return false;
hashAddr++;
if (hashAddr == _ht.capacity())
hashAddr = 0;
if (hashAddr == startAddr)
return false;
}
_ht[hashAddr]._state = EXIST;
_ht[hashAddr]._val = val;
_size++;
return true;
}
int Find(const K& key) {
size_t hashAddr = HashFunc(key);
while (_ht[hashAddr]._state != EMPTY) {
if (_ht[hashAddr]._state == EXIST && _ht[hashAddr]._val.first == key)
return hashAddr;
hashAddr++;
if (hashAddr == _ht.capacity())
hashAddr = 0;
}
return -1;
}
bool Erase(const K& key) {
int index = Find(key);
if (-1 != index) {
_ht[index]._state = DELETE;
_size--;
return true;
}
return false;
}
private:
void _CheckCapacity() {
if (_size * 10 / _ht.capacity() >= 7) {
HashTable<K, V, HF> newHt(GetNextPrime(_ht.capacity()));
for (size_t i = 0; i < _ht.capacity(); ++i) {
if (_ht[i]._state == EXIST)
newHt.Insert(_ht[i]._val);
}
_ht.swap(newHt._ht);
}
}
size_t HashFunc(const K& key) {
return key % _ht.capacity();
}
private:
vector<Elem> _ht;
size_t _size = 0;
};
二次探测
- 原理：为了避免线性探测产生的数据堆积问题，二次探测找下一个空位置的方法为： H_i = (H_0 + i^2) % m 或者 H_i = (H_0 - i^2) % m ，其中 H_0 是通过散列函数 Hash(x) 对元素的关键码 key 进行计算得到的位置， m 是表的大小 。
- 优点：相比线性探测，能一定程度缓解数据堆积。
- 缺点：实现相对复杂。
- C++代码实现（插入部分示例）：
bool Insert(const pair<K, V>& val) {
_CheckCapacity();
size_t hashAddr = HashFunc(val.first);
size_t i = 1;
size_t startAddr = hashAddr;
while (_ht[hashAddr]._state != EMPTY) {
if (_ht[hashAddr]._state == EXIST && _ht[hashAddr]._val.first == val.first)
return false;
hashAddr = startAddr + i * i;
hashAddr %= _ht.capacity();
if (hashAddr == startAddr)
return false;
i++;
}
_ht[hashAddr]._state = EXIST;
_ht[hashAddr]._val = val;
_size++;
return true;
}开散列（链地址法）
原理
首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
C++代码实现
template<class V>
struct HashBucketNode {
HashBucketNode(const V& data) : _pNext(nullptr), _data(data) {}
HashBucketNode<V>* _pNext;
V _data;
};
template<class V>
class HashBucket {
public:
HashBucket(size_t capacity = 3) : _size(0) {
_ht.resize(GetNextPrime(capacity), nullptr);
}
~HashBucket() {
Clear();
}
void Insert(const V& data) {
_CheckCapacity();
size_t bucketNo = HashFunc(data);
HashBucketNode<V>* pCur = _ht[bucketNo];
while (pCur) {
if (pCur->_data == data)
return;
pCur = pCur->_pNext;
}
pCur = new HashBucketNode<V>(data);
pCur->_pNext = _ht[bucketNo];
_ht[bucketNo] = pCur;
_size++;
}
void Erase(const V& data) {
size_t bucketNo = HashFunc(data);
HashBucketNode<V>* pCur = _ht[bucketNo];
HashBucketNode<V>* pPrev = nullptr;
while (pCur) {
if (pCur->_data == data) {
if (pPrev)
pPrev->_pNext = pCur->_pNext;
else
_ht[bucketNo] = pCur->_pNext;
delete pCur;
_size--;
return;
}
pPrev = pCur;
pCur = pCur->_pNext;
}
}
private:
void _CheckCapacity() {
if (_size == BucketCount()) {
HashBucket<V, HF> newHt(BucketCount());
for (size_t bucketIdx = 0; bucketIdx < BucketCount(); ++bucketIdx) {
HashBucketNode<V>* pCur = _ht[bucketIdx];
while (pCur) {
_ht[bucketIdx] = pCur->_pNext;
size_t bucketNo = newHt.HashFunc(pCur->_data);
pCur->_pNext = newHt._ht[bucketNo];
newHt._ht[bucketNo] = pCur;
pCur = _ht[bucketIdx];
}
}
newHt._size = _size;
this->Swap(newHt);
}
}
size_t HashFunc(const V& data) {
return data % _ht.capacity();
}
private:
vector<HashBucketNode<V>*> _ht;
size_t _size;
};四、unordered系列关联式容器（以unordered_map为例）
底层结构
unordered_map 底层使用哈希结构，通过哈希函数将键值对映射到不同的桶中，实现快速查找。
接口说明
1. 构造函数： unordered_map 用于构造不同格式的 unordered_map 对象。
2. 容量相关：
- bool empty() const ：检测 unordered_map 是否为空。
- size_t size() const ：获取 unordered_map 的有效元素个数。
3. 迭代器相关：
- begin ：返回 unordered_map 第一个元素的迭代器。
- end ：返回 unordered_map 最后一个元素下一个位置的迭代器。
- cbegin ：返回 unordered_map 第一个元素的 const 迭代器。
- cend ：返回 unordered_map 最后一个元素下一个位置的 const 迭代器。
4. 元素访问： operator[] 用于返回与 key 对应的 value ，如果 key 不存在则插入一个默认值。
5. 查询：
- iterator find(const K& key) ：返回 key 在哈希桶中的位置。
- size_t count(const K& key) ：返回哈希桶中关键码为 key 的键值对的个数（在 unordered_map 中最大为1 ）。
6. 修改操作：
- insert ：向容器中插入键值对。
- erase ：删除容器中的键值对。
- void clear() ：清空容器中有效元素个数。
- void swap(unordered_map&) ：交换两个容器中的元素。
7. 桶操作：
- size_t bucket_count()const ：返回哈希桶中桶的总个数。
- size_t bucket_size(size_t n)const ：返回 n 号桶中有效元素的总个数。
- size_t bucket(const K& key) ：返回元素 key 所在的桶号 。
代码实现细节
unordered_map 在C++中是基于哈希表实现的关联式容器，它存储的是 pair<K, V> 键值对， K 为 key 的类型， V 为 value 的类型，通过哈希函数（ HF 类型）来实现快速的键值查找。以下是其具体实现的代码剖析：
类模板定义与类型别名
#include <vector>
#include <memory>
// 假设已有默认哈希函数定义
template <class T>
class DefHashF {
public:
size_t operator()(const T& val) const {
// 简单示例，对于整数直接返回值，实际应用中需更复杂哈希计算
return static_cast<size_t>(val);
}
};
// 哈希桶节点定义
template<class V>
struct HashBucketNode {
HashBucketNode(const V& data) : _pNext(nullptr), _data(data) {}
HashBucketNode<V>* _pNext;
V _data;
};
// 哈希桶类
template<class K, class V, class KeyOfValue, class HF = DefHashF<K>>
class HashBucket {
friend class unordered_map<K, V, HF>;
using PNode = HashBucketNode<V>*;
public:
// 迭代器类型定义（内部迭代器类后续补齐）
class Iterator;
Iterator Begin() {
size_t bucketNo = 0;
for (; bucketNo < _ht.size(); ++bucketNo) {
if (_ht[bucketNo])
break;
}
if (bucketNo < _ht.size())
return Iterator(_ht[bucketNo], this);
else
return Iterator(nullptr, this);
}
Iterator End() { return Iterator(nullptr, this); }
Iterator Find(const K& key);
Iterator Insert(const V& data);
Iterator Erase(const K& key);
size_t Count(const K& key) {
auto it = Find(key);
return (it != End())? 1 : 0;
}
size_t BucketCount() const { return _ht.size(); }
size_t BucketSize(size_t bucketNo) const {
size_t count = 0;
PNode pCur = _ht[bucketNo];
while (pCur) {
count++;
pCur = pCur->_pNext;
}
return count;
}
private:
void _CheckCapacity() {
if (_size == _ht.size()) {
std::vector<PNode> newHt(_ht.size() * 2, nullptr);
for (size_t bucketIdx = 0; bucketIdx < _ht.size(); ++bucketIdx) {
PNode pCur = _ht[bucketIdx];
while (pCur) {
PNode next = pCur->_pNext;
size_t bucketNo = HF{}(KeyOfValue{}(pCur->_data));
pCur->_pNext = newHt[bucketNo];
newHt[bucketNo] = pCur;
pCur = next;
}
_ht[bucketIdx] = nullptr;
}
_ht = std::move(newHt);
}
}
std::vector<PNode> _ht;
size_t _size = 0;
};
// 哈希桶迭代器类
template<class K, class V, class KeyOfValue, class HF>
class HashBucket<K, V, KeyOfValue, HF>::Iterator {
public:
using Self = Iterator;
using PNode = HashBucketNode<V>*;
using HashBucketPtr = HashBucket<K, V, KeyOfValue, HF>*;
Iterator(PNode pNode = nullptr, HashBucketPtr pHT = nullptr) : _pNode(pNode), _pHT(pHT) {}
Self& operator++() {
if (_pNode->_pNext) {
_pNode = _pNode->_pNext;
}
else {
size_t bucketNo = _pHT->HF{}(KeyOfValue{}( _pNode->_data)) + 1;
for (; bucketNo < _pHT->_ht.size(); ++bucketNo) {
if (_pHT->_ht[bucketNo]) {
_pNode = _pHT->_ht[bucketNo];
break;
}
}
if (bucketNo == _pHT->_ht.size()) {
_pNode = nullptr;
}
}
return *this;
}
Self operator++(int) {
Self tmp = *this;
++(*this);
return tmp;
}
V& operator*() { return _pNode->_data; }
V* operator->() { return &(_pNode->_data); }
bool operator==(const Self& it) const { return _pNode == it._pNode; }
bool operator!=(const Self& it) const { return _pNode != it._pNode; }
private:
PNode _pNode;
HashBucketPtr _pHT;
};
template<class K, class V, class HF = DefHashF<K>>
class unordered_map {
typedef pair<K, V> ValueType;
typedef HashBucket<K, ValueType, KeyOfValue, HF> HT;
struct KeyOfValue {
const K& operator()(const ValueType& data) {
return data.first;
}
};
public:
typedef typename HT::Iterator iterator;
unordered_map() = default;
iterator begin() { return _ht.Begin(); }
iterator end() { return _ht.End(); }
size_t size() const { return _ht._size; }
bool empty() const { return _ht._size == 0; }
V& operator[](const K& key) {
auto it = _ht.Find(key);
if (it != _ht.End()) {
return *it;
}
else {
auto newIt = _ht.Insert(ValueType(key, V()));
return *newIt;
}
}
const V& operator[](const K& key) const {
auto it = _ht.Find(key);
if (it != _ht.End()) {
return *it;
}
else {
// 对于const版本，这里可根据需求决定是否抛出异常等处理
// 简单示例返回默认V值
return V();
}
}
iterator find(const K& key) { return _ht.Find(key); }
size_t count(const K& key) { return _ht.Count(key); }
std::pair<iterator, bool> insert(const ValueType& value) {
auto [it, success] = _ht.Insert(value);
return {it, success};
}
iterator erase(iterator position) {
return _ht.Erase(KeyOfValue{}(*position));
}
size_t bucket_count() { return _ht.BucketCount(); }
size_t bucket_size(const K& key) {
size_t bucketNo = HF{}(key);
return _ht.BucketSize(bucketNo);
}
private:
HT _ht;
};
这里定义了 unordered_map 的类模板， HF 有默认的哈希函数类型 DefHashF<K> 。 ValueType 别名表示键值对类型， HT 则是对底层 HashBucket 类的实例化别名， KeyOfValue 结构体用于从键值对中提取 key 。
迭代器相关
public:
typename typedef HT::Iterator iterator;
public:
unordered_map() : _ht() {}
iterator begin() { return _ht.Begin(); }
iterator end() { return _ht.End(); }
通过 typedef 引入底层 HashBucket 的迭代器类型， begin 和 end 函数直接调用 HashBucket 类对应的函数，返回容器起始和结束位置的迭代器。
容量相关操作
size_t size()const { return _ht.Size(); }
bool empty()const{return _ht.Empty(); }
size 函数返回容器中有效元素的个数， empty 函数判断容器是否为空，都是通过调用底层 HashBucket 类的对应方法实现。
元素访问操作
V& operator[](const K& key) {
return (*(_ht.InsertUnique(ValueType(key, V()))).first).second;
}
const V& operator[](const K& key)const;
operator[] 操作符用于通过 key 访问 value 。如果 key 不存在，会插入一个默认值的键值对。这里调用 HashBucket 的 InsertUnique 方法插入（若不存在）并返回对应 value 。
查询操作
iterator find(const K& key) { return _ht.Find(key); }
size_t count(const K& key) { return _ht.Count(key); }
find 函数用于查找指定 key 的位置，返回对应的迭代器； count 函数返回指定 key 在容器中出现的次数（在 unordered_map 中最多为1 ），均是转发给底层 HashBucket 类的相应函数处理。
修改操作
pair<iterator, bool> insert(const ValueType& value) {
return _ht.Insert(value);
}
iterator erase(iterator position) {
return _ht.Erase(position);
}
insert 函数用于插入键值对，返回一个 pair ，包含迭代器和表示插入是否成功的 bool 值； erase 函数用于删除指定位置的元素，返回删除元素后的下一个元素的迭代器，同样是依赖底层 HashBucket 类的实现。
桶相关操作
size_t bucket_count() { return _ht.BucketCount(); }
size_t bucket_size(const K& key) { return _ht.BucketSize(key); }
bucket_count 函数返回哈希桶的总数， bucket_size 函数返回指定 key 所在桶中的元素个数，也是通过调用 HashBucket 类的对应方法来实现。
底层HashBucket类的部分实现
template<class K, class V, class KeyOfValue, class HF = DefHashF<K>>
class HashBucket {
friend HBIterator<K, V, KeyOfValue, HF>;
public:
typedef HBIterator<K, V, KeyOfValue, HF> Iterator;
Iterator Begin() {
size_t bucketNo = 0;
for (; bucketNo < _ht.capacity(); ++bucketNo) {
if (_ht[bucketNo])
break;
}
if (bucketNo < _ht.capacity())
return Iterator(_ht[bucketNo], this);
else
return Iterator(nullptr, this);
}
Iterator End() { return Iterator(nullptr, this); }
Iterator Find(const K& key);
Iterator Insert(const V& data);
Iterator Erase(const K& key);
size_t Count(const K& key) {
if (Find(key) != End())
return 1;
return 0;
}
size_t BucketCount()const { return _ht.capacity(); }
size_t BucketSize(size_t bucketNo) {
size_t count = 0;
PNode pCur = _ht[bucketNo];
while (pCur) {
count++;
pCur = pCur->_pNext;
}
return count;
}
private:
vector<PNode*> _ht;
size_t _size;
};
HashBucket 类是 unordered_map 的底层实现基础，它包含了哈希桶数组（ _ht ）和元素个数（ _size ）等成员。 Begin 函数用于找到第一个有元素的桶并返回对应的迭代器， End 函数返回表示结束的迭代器。 Find 、 Insert 、 Erase 等函数分别实现元素的查找、插入和删除操作， Count 函数统计指定 key 的个数， BucketCount 函数返回桶的总数， BucketSize 函数统计指定桶中的元素个数。
通过上述代码实现， unordered_map 借助底层 HashBucket 类，利用哈希表的特性，实现了高效的键值对存储、查找和修改等操作。在实际应用中，合理使用 unordered_map 能极大提升程序处理大量键值数据的效率。
五、哈希的应用
1. 海量数据处理面试题场景
- 问题示例：在海量数据中找出出现次数超过一定阈值的元素。
- 解决思路：可以利用 unordered_map 来统计每个元素出现的次数。例如，对于一个包含大量整数的数组，要找出出现次数超过数组长度1% 的元素。
- 代码示例：
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
vector<int> findFrequentElements(vector<int>& nums) {
unordered_map<int, int> countMap;
for (int num : nums) {
countMap[num]++;
}
vector<int> result;
int threshold = nums.size() / 100; // 1%阈值
for (const auto& p : countMap) {
if (p.second > threshold) {
result.push_back(p.first);
}
}
return result;
}
2. 其他应用场景
- 缓存系统：利用哈希快速查找的特性，判断数据是否在缓存中，提高数据访问效率。
- 数据库索引：一些数据库采用哈希索引来加速数据的检索。
完整代码
HashTable.h
#define _CRT_SECURE_NO_WARNINGS
#include<vector>
template<class K>
struct DefaultHashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct DefaultHashFunc<string>
{
size_t operator()(const string& str)
{
// BKDR
size_t hash = 0;
for (auto ch : str)
{
hash *= 131;
hash += ch;
}
return hash;
}
};
namespace open_address
{
enum STATE
{
EXIST,
EMPTY,
DELETE
};
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
STATE _state = EMPTY;
};
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
public:
/*HashTable()
{
_table.resize(10);
}*/
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
// 扩容
//if ((double)_n / (double)_table.size() >= 0.7)
if (_n * 10 / _table.size() >= 7)
{
size_t newSize = _table.size() * 2;
// 遍历旧表，重新映射到新表
HashTable<K, V, HashFunc> 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);
}
// 线性探测
HashFunc hf;
size_t hashi = hf(kv.first) % _table.size();
while (_table[hashi]._state == EXIST)
{
++hashi;
hashi %= _table.size();
}
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_n;
return true;
}
HashData<const K, V>* Find(const K& key)
{
// 线性探测
HashFunc hf;
size_t hashi = hf(key) % _table.size();
while (_table[hashi]._state != EMPTY)
{
if (_table[hashi]._state == EXIST
&& _table[hashi]._kv.first == key)
{
return (HashData<const K, V>*) & _table[hashi];
}
++hashi;
hashi %= _table.size();
}
return nullptr;
}
// 按需编译
bool Erase(const K& key)
{
HashData<const K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_n;
return true;
}
return false;
}
private:
vector<HashData<K, V>> _table;
size_t _n = 0; // 存储有效数据的个数
};
}
///
// 泛型编程：不是针对某种具体类型，针对广泛的类型(两种及以上) -- 模板
namespace hash_bucket
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{
}
};
// 前置声明
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable;
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;
Node* _node;
const HashTable<K, T, KeyOfT, HashFunc>* _pht;
/*HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
:_node(node)
,_pht(pht)
{}*/
HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht)
:_node(node)
, _pht(pht)
{
}
// 普通迭代器时，他是拷贝构造
// const迭代器时，他是构造
HTIterator(const Iterator& it)
:_node(it._node)
, _pht(it._pht)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next)
{
// 当前桶还没完
_node = _node->_next;
}
else
{
KeyOfT kot;
HashFunc hf;
size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
// 从下一个位置查找查找下一个不为空的桶
++hashi;
while (hashi < _pht->_table.size())
{
if (_pht->_table[hashi])
{
_node = _pht->_table[hashi];
return *this;
}
else
{
++hashi;
}
}
_node = nullptr;
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
// 1、哈希表
// 2、封装map和set
// 3、普通迭代器
// 4、const迭代器
// 5、insert返回值 operator[]
// 6、key不能修改的问题
// set -> hash_bucket::HashTable<K, K> _ht;
// map -> hash_bucket::HashTable<K, pair<K, V>> _ht;
template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
typedef HashNode<T> Node;
// 友元声明
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
friend struct HTIterator;
public:
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
iterator begin()
{
// 找第一个桶
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
{
return iterator(cur, this);
}
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
const_iterator begin() const
{
// 找第一个桶
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
{
return const_iterator(cur, this);
}
}
return const_iterator(nullptr, this);
}
const_iterator end() const
{
return const_iterator(nullptr, this);
}
size_t GetNextPrime(size_t prime)
{
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 < PRIMECOUNT; ++i)
{
if (primeList[i] > prime)
return primeList[i];
}
return primeList[i];
}
HashTable()
{
_table.resize(GetNextPrime(1), nullptr);
}
~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;
}
}
///
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot;
iterator it = Find(kot(data));
if (it != end())
{
return make_pair(it, false);
}
HashFunc hf;
// 负载因子到1就扩容
if (_n == _table.size())
{
//size_t newSize = _table.size() * 2;
size_t newSize = GetNextPrime(_table.size());
vector<Node*> newTable;
newTable.resize(newSize, nullptr);
// 遍历旧表，顺手牵羊，把节点牵下来挂到新表
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = hf(kot(cur->_data)) % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
size_t hashi = hf(kot(data)) % _table.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return make_pair(iterator(newnode, this), true);
}
iterator Find(const K& key)
{
HashFunc hf;
KeyOfT kot;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur, this);
}
cur = cur->_next;
}
return end();
}
bool Erase(const K& key)
{
HashFunc hf;
KeyOfT kot;
size_t hashi = hf(key) % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
_table[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
void Print()
{
for (size_t i = 0; i < _table.size(); i++)
{
printf("[%d]->", i);
Node* cur = _table[i];
while (cur)
{
cout << cur->_kv.first << ":" << cur->_kv.second << "->";
cur = cur->_next;
}
printf("NULL\n");
}
cout << endl;
}
private:
vector<Node*> _table; // 指针数组
size_t _n = 0; // 存储了多少个有效数据
};
}UnOrderedSet.h
#pragma once
#include"HashTable.h"
namespace bit
{
template<class K>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;
const_iterator begin() const
{
return _ht.begin();
}
const_iterator end() const
{
return _ht.end();
}
pair<const_iterator, bool> insert(const K& key)
{
//return _ht.Insert(key);
pair<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
return pair<const_iterator, bool>(ret.first, ret.second);
}
private:
hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};
}
UnorderedMap.h
#pragma once
#include"HashTable.h"
namespace bit
{
template<class K, class V>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
const_iterator begin() const
{
return _ht.begin();
}
const_iterator end() const
{
return _ht.end();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
};
}test.cpp
#pragma once
#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<set>
using namespace std;
//int main()
//{
// // 去重
// unordered_set<int> us;
// size_t old = us.bucket_count();
// cout << old << endl;
// for (size_t i = 0; i < 10000; i++)
// {
// us.insert(i);
//
// if (old != us.bucket_count())
// {
// old = us.bucket_count();
// cout << old << endl;
// }
// }
//
// /*unordered_set<int>::iterator it = us.begin();
// while (it != us.end())
// {
// cout << *it << " ";
// ++it;
// }
// cout << endl;*/
//
// /*unordered_map<string, string> dict;
// dict["sort"] = "排序";
// dict["insert"] = "插入";
// dict["string"] = "字符串";
// dict["left"];
//
// for (auto& kv : dict)
// {
// cout << kv.first << ":" << kv.second << endl;
// }
// cout << endl;*/
//
//
//
//
// return 0;
//}
//int main()
//{
// const size_t N = 100000;
//
// unordered_set<int> us;
// set<int> s;
//
// vector<int> v;
// v.reserve(N);
// srand(time(0));
// for (size_t i = 0; i < N; ++i)
// {
// v.push_back(rand());
// //v.push_back(rand()+i);
// //v.push_back(i);
// }
//
//
// size_t begin1 = clock();
// for (auto e : v)
// {
// s.insert(e);
// }
// size_t end1 = clock();
// cout << "set insert:" << end1 - begin1 << endl;
//
// size_t begin2 = clock();
// for (auto e : v)
// {
// us.insert(e);
// }
// size_t end2 = clock();
// cout << "unordered_set insert:" << end2 - begin2 << endl;
//
//
// size_t begin3 = clock();
// for (auto e : v)
// {
// s.find(e);
// }
// size_t end3 = clock();
// cout << "set find:" << end3 - begin3 << endl;
//
// size_t begin4 = clock();
// for (auto e : v)
// {
// us.find(e);
// }
// size_t end4 = clock();
// cout << "unordered_set find:" << end4 - begin4 << endl << endl;
//
// cout <<"插入数据个数："<< s.size() << endl;
// cout <<"插入数据个数：" << us.size() << endl << endl;;
//
// size_t begin5 = clock();
// for (auto e : v)
// {
// s.erase(e);
// }
// size_t end5 = clock();
// cout << "set erase:" << end5 - begin5 << endl;
//
// size_t begin6 = clock();
// for (auto e : v)
// {
// us.erase(e);
// }
// size_t end6 = clock();
// cout << "unordered_set erase:" << end6 - begin6 << endl << endl;
//
// return 0;
//}
#include"HashTable.h"
//int main()
//{
// open_address::HashTable<int, int> ht;
// int a[] = { 1,111,4,7,15,25,44,9 };
// for (auto e : a)
// {
// ht.Insert(make_pair(e, e));
// }
//
// ht.Erase(15);
//
// auto ret = ht.Find(4);
// //ret->_kv.first = 41;
// ret->_kv.second = 400;
//
// //HashTable<string, string, StringHashFunc> dict;
// open_address::HashTable<string, string> dict;
// dict.Insert(make_pair("sort", "排序"));
// dict.Insert(make_pair("left", "xxx"));
// auto dret = dict.Find("left");
// //dret->_kv.first = "xx";
// dret->_kv.second = "左边";
//
// string s1("xxx");
// string s2("xxx");
//
//
// open_address::DefaultHashFunc<string> hf;
// cout << hf(s1) << endl;
// cout << hf(s2) << endl;
// cout << hf("bacd") << endl;
// cout << hf("abcd") << endl;
// cout << hf("abbe") << endl;
// cout << hf("https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=65081411_1_oem_dg&wd=STATE&fenlei=256&rsv_pq=0xdd48647300054f47&rsv_t=1cd5rO%2BE6TJzo6qf9QKcibznhQ9J3lFwGEzmkc0Goazr3HuQSIIc2zD78Pt0&rqlang=en&rsv_enter=1&rsv_dl=tb&rsv_sug3=2&rsv_n=2&rsv_sug1=1&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&prefixsug=STAT%2526gt%253B&rsp=5&inputT=656&rsv_sug4=796") << endl;
//
// return 0;
//}
//int main()
//{
// hash_bucket::HashTable<int, int> ht;
// int a[] = { 1,111,4,7,15,25,44,9 };
// for (auto e : a)
// {
// ht.Insert(make_pair(e, e));
// }
// ht.Print();
//
// ht.Insert(make_pair(14, 14));
// ht.Print();
//
// ht.Insert(make_pair(24, 24));
// ht.Print();
//
// ht.Insert(make_pair(34, 34));
// ht.Print();
//
// ht.Erase(44);
// ht.Erase(4);
// ht.Erase(24);
// ht.Print();
//
// hash_bucket::HashTable<string, string> dict;
// dict.Insert(make_pair("sort", "排序"));
// dict.Insert(make_pair("left", "xxx"));
// dict.Insert(make_pair("insert", "插入"));
// dict.Insert(make_pair("string", "字符串"));
// dict.Insert(make_pair("bucket", "桶"));
//
// auto dret = dict.Find("left");
// //dret->_kv.first = "xx";
// dret->_kv.second = "左边";
// dict.Print();
//
// return 0;
//}
#include"UnOrderedSet.h"
#include"UnOrderedMap.h"
//int main()
//{
// bit::unordered_set<int> us;
// us.insert(3);
// us.insert(1);
// us.insert(3);
// us.insert(4);
// us.insert(5);
// us.insert(0);
//
// bit::unordered_set<int>::iterator it = us.begin();
// while (it != us.end())
// {
// // 不能修改key
// //*it += 10;
// cout << *it << " ";
// ++it;
// }
// cout << endl;
//
// bit::unordered_map<string, string> dict;
// dict.insert(make_pair("sort", "排序"));
// dict.insert(make_pair("left", "左边"));
// dict.insert(make_pair("insert", "插入"));
// dict.insert(make_pair("sort", "xxx"));
//
// bit::unordered_map<string, string>::iterator dit = dict.begin();
// while (dit != dict.end())
// {
// // 不能修改key
// //dit->first += 'x';
// dit->second += 'x';
//
// cout << dit->first << ":" << dit->second << endl;
//
//
// ++dit;
// }
// cout << endl;
//
// dict["sort"] = "排序";
// dict["insert"] = "插入";
// dict["string"] = "字符串";
// dict["right"];
//
// for (auto& kv : dict)
// {
// cout << kv.first << ":" << kv.second << endl;
// }
//
// return 0;
//}六、总结
哈希是一种强大且应用广泛的数据结构和算法思想。通过合理设计哈希函数和解决哈希冲突，能够实现高效的数据存储和查找。 unordered 系列关联式容器是哈希在C++中的典型应用，理解其底层原理有助于我们在实际编程中更好地选择和使用数据结构，提升程序性能。同时，哈希在海量数据处理等领域也发挥着重要作用，掌握相关知识对解决复杂问题大有裨益。
希望通过这篇博客，能让大家对哈希有更深入、全面的理解。在实际编程中，根据不同的需求和场景，灵活运用哈希相关知识，打造出更高效、稳定的程序。