1. 哈希表的基本原理
哈希表是一种通过 哈希函数 将元素的键（Key）映射到存储位置的数据结构。
哈希函数 的作用：通过键值计算存储位置，公式一般为
index = hash(key) % capacity。哈希冲突：不同的键可能被映射到同一个位置（例如
hash("abc") % 10 == hash("xyz") % 10），这种情况称为 哈希冲突 或 哈希碰撞。
2. 解决哈希冲突的两种方法
(1) 闭散列（开放定址法，Open Addressing）
核心思想：如果目标位置已被占用，就按照某种探测方法在哈希表内 寻找下一个可用位置。
常用探测方法：
线性探测（Linear Probing）
冲突时，依次检查下一个位置：
index = (hash(key) + i) % capacity, i=1, 2, 3...
二次探测（Quadratic Probing）
冲突时，按平方步长跳跃检查：
index = (hash(key) + i²) % capacity, i=1, 2, 3...
双重哈希（Double Hashing）
第一个哈希函数计算基础地址，使用第二个哈希函数计算步长：
index = (hash1(key) + i * hash2(key)) % capacity, i=1,2,3...
开放定址法的特点：
所有数据都存在哈希表内，没有额外资源。
删除元素需特殊处理（标记为“逻辑删除”），否则会破坏探测链。
负载因子（Load Factor）通常需较低（如 ≤0.7），否则性能急剧下降。
(2) 开散列（链地址法，Separate Chaining）
核心思想：将哈希表的每个槽作为 链表头节点，冲突的元素直接追加到链表中。
优化：
当链表过长时（如 Java 8 的
HashMap），可能转换为 红黑树，将查找时间从 O(n) 优化到 O(log n)。
链地址法的特点：
实现简单，允许负载因子 >1（即元素数量可以超过哈希表容量）。
删除操作直接（直接移除链表节点即可）。
内存开销较大，除了哈希表外，还有额外资源节点。
#pragma once
#include<vector>//只包头文件不展开命名空间白搭
#include<utility>//
#include<iostream>
using namespace std;
namespace OpenAdress//开放定址法
{
enum State
{
EMPTY,
DELETE,
EXIST
};
template<class K,class V>
struct HashData//为了能直接访问hashdata设为struct
{
pair<K, V> _kv;
State _state=EMPTY;
//使用默认构造，初始化列表使用缺省值
};
template<class K,class V>
class HashTable
{
public:
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
if (_tables.size() == 0 || (double)_n / _tables.size() >= 0.7)//负载因子设为0.7
{
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
vector<HashData<K, V>> newtable;
newtable.resize(newsize);
for (HashData<K, V>& e : _tables)//已经扩容过了必定可以插入
{
if (e._state == EXIST)
{
size_t hashi = e._kv.first % newtable.size();
size_t i = 1;
size_t index = hashi;
while (newtable[index]._state == EXIST)
{
index = hashi + i;
index %= newtable.size();
i++;
}
newtable[index]._kv = e._kv;
newtable[index]._state = EXIST;
}
}
_tables.swap(newtable);
}
size_t hashi = kv.first % _tables.size();
size_t i = 1;
size_t index = hashi;
while (_tables[index]._state == EXIST)
{
index = hashi + i;
index %= _tables.size();
i++;
}
_tables[index]._kv = kv;
_tables[index]._state = EXIST;
_n++;
return true;
}
HashData<K,V>* Find(const K& key)
{
if (_tables.size() == 0)
{
return nullptr;
}
size_t hashi = key % _tables.size();
size_t i = 1;
size_t index = hashi;
while (_tables[index]._state!=EMPTY)//插入是从hashi开始向后找不EXIST的位置，按插入方式找的时候如果遇到空说明没有该值，找了一圈没有找到那也是没有
{
if (_tables[index]._state == EXIST && _tables[index]._kv.first == key)
{
return &_tables[index];
}
index =hashi+ i;
index %= _tables.size();
i++;
if (index == hashi)//找了一圈
{
break;//直接返回报警不是所有路径有返回值
}
}
return nullptr;
}
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
_n--;
return true;
}
else
{
return false;
}
}
private:
vector<HashData<K, V>> _tables;//全部建立在栈区上，无需释放
size_t _n = 0;//有效数据个数
};
}
//在全局作用域定义Hash仿函数，包了头文件就能直接用
template<class K>
struct HashFunc//可作为Hash的缺省值
{
size_t operator()(const K& key)
{
return key;//可隐式类型转换
}
};
template<>//特化 仿函数
struct HashFunc<string>
{
size_t operator()(const string& str)
{
size_t i= 0;
for (auto e : str)
{
i += e;
i *= 31;
}
return i;
}
};
namespace HashBucket
{
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 Hash>//前置声明
class HashTable;
template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash>
struct __HashIterator
{
typedef HashNode<T> Node;
typedef __HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
typedef __HashIterator< K, T, T&, T*, KeyOfT, Hash> iterator;
typedef HashTable<K, T, KeyOfT, Hash> HT;//不前置声明的话会报<前缺少；的错误
Node* _node;
HT* _ht;
__HashIterator(Node* node,HT* ht)
:_node(node)
,_ht(ht)
{}
__HashIterator(const iterator& it)
:_node(it._node)
,_ht(it._ht)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
//哈希表为单向迭代器
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
break;
}
else
{
KeyOfT kot;
Hash hash;
size_t hashi = hash(kot(_node->_data)) % _ht->GetSize();
hashi++;
while (hashi < _ht->GetSize())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
else
{
hashi++;
}
}
if (hashi == _ht->GetSize())
{
_node = nullptr;
}
}
return *this;
}
};
template<class K,class T,class KeyOfT,class Hash>//Hash仿函数将key转换为整形
class HashTable
{
//需要访问_tables
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
friend struct __HashIterator;
typedef HashNode<T> Node;
public:
typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
typedef __HashIterator<K, T, const T&,const T*, KeyOfT, Hash> const_iterator;
iterator begin()
{
Node* cur = nullptr;
for (int i = 0;i < _tables.size();i++)
{
if (_tables[i])
{
cur = _tables[i];
break;
}
}
return iterator(cur, this);
}
iterator end()
{
return iterator(nullptr, this);
}
const_iterator begin()const
{
Node* cur = nullptr;
for (int i = 0;i < _tables.size();i++)
{
if (_tables[i])
{
break;
}
}
return const_iterator(cur, this);
}
const_iterator end()const
{
return const_iterator(nullptr, this);
}
~HashTable()
{
for (Node* cur : _tables)
{
while (cur)
{
Node* tmp = cur;
cur = cur->_next;
delete tmp;
}
}
}
size_t GetSize()
{
return _tables.size();
}
iterator Find(const K& key)
{
if (_tables.size() == 0)
return iterator(nullptr,this);
KeyOfT kot;
Hash hash;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur,this);
}
cur = cur->_next;
}
return iterator(nullptr, this);
}
bool Erase(const K& key)
{
KeyOfT kot;
Hash hash;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
Node* prev = nullptr;
while (cur)
{
if (kot(cur->_data) != key)
{
prev = cur;
cur = cur->_next;
}
else
{
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
}
return false;
}
pair<iterator,bool> Insert(const T& data)
{
KeyOfT kot;
iterator it = Find(kot(data));
if ( it!=end())
{
return make_pair(it,false);
}
Hash hash;
if (_n == _tables.size())//先判断是否要扩容,且该代码包含为空的情况
{
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
vector<Node*> newtable(newsize,nullptr);
for (Node* cur : _tables)
{
while (cur)
{
Node* tmp = cur;
cur = cur->_next;
size_t hashi = hash(kot(tmp->_data)) % newtable.size();
tmp->_next = newtable[hashi];
newtable[hashi] = tmp;
}
}
_tables.swap(newtable);
}
size_t hashi = hash(kot(data)) % _tables.size();
Node* tmp = new Node(data);
tmp->_next = _tables[hashi];
_tables[hashi] = tmp;
return make_pair(iterator(tmp,this),true);
}
private:
vector<Node*> _tables;
size_t _n;
};
}1.闭散列也就是发放定址法（线性探测）实现哈希表
a.哈希表节点设计
两个模板参数一个键类型K，一个值类型V，有一个数据，然后数据类型是pair<K,V>,一个状态值是枚举类型，不去设置泛型的数据类型T，而是设计成这种数据格式，这个设计和AVL树节点设计很像
b.哈希表设计
哈希表的成员有一个vector，vector的元素就是哈希表节点，还有一个size_t,是节点个数
哈希表模板参数本应由三个，第一个是键的类型K，第二个是值类型V，第三个是将K转换成size_t的仿函数类，但这里偷懒了没有加，测试直接用的K是int，而且因为节点数据类型不是T，所以也不用加把T变成K的仿函数类
c.哈希表节点为什么有三种状态而不是只有empty和exist两种
插入一个元素，如果键映射的位置已经是exist那就往后探测，如果是delete或empty，那直接存就是了。
查找一个元素，如果是exist那就看看键是不是我要的，如果不是那就下一个，如果是delete，那说明这个已经被删了，但后面可能还有，所以继续往后探测，如果是empty那真到头了，直接结束吧，没有对应键的节点
也就是说delete这种状态是因为我们要用empty来表示查找结束，所以删除一个元素不能用empty来表示，所以加一个delete状态
d.哈希表中存储节点，没有额外资源
2.开散列也就是链地址法实现哈希表
a.哈希表节点设计
一个模板参数T表示数据类型，然后节点里有一个T类型数据，一个指针，因为节点是用单链表串起来的
b.哈希表设计
模板参数是，键的类型K，哈希表节点数据类型T，把数据类型T变成K的仿函数类keyOfT，把键类型K变成size_t的仿函数类类型Hash
成员是，一个vector,vector的元素是节点指针，存的是一个哈希桶单链表的头结点指针，还有一个size_t成员,表示节点个数
c.哈希表的插入
插入就是头插节点
d.哈希表的迭代器设计
哈希表的迭代器就是封装了结点指针的类
成员有结点指针，这个自然。节点是以单链表的形式存在的，我们为了支持迭代器++能够找到下一个节点，要在迭代器对象里加一个哈希表对象的指针，不然下一个节点不在这个单链表我们就没法弄
迭代器的模板参数K，T，keyOfT，Hash都是为了有结点类型和哈希表类型，剩下俩ref和ptr是为了实现迭代器和const迭代器
ps：迭代器的解引用*返回的是节点里数据的引用，迭代器的成员访问->，返回的是节点里数据的指针。编译器在编 迭代器->成员 时，先是 迭代器.operator->(),返回节点里数据的指针，然后 编译器自动 指针->成员，最终实现访问节点里数据的成员的效果