数据结构 - 哈希表

前言

一、哈希思想

哈希思想（Hashing）是计算机科学中一种非常重要的思想，它主要用于实现数据的快速查找、去重、以及作为数据结构如哈希表（HashTable）或哈希集合（Hash Set）的基础。哈希思想的核心在于通过一个哈希函数（Hash Function）将任意长度的输入（通常称为键或关键字）映射到一个固定长度的输出，这个输出通常是一个整数，我们称之为哈希值（Hash Value）或哈希码（Hash Code）。

二、哈希表概念

哈希表（Hash Table）是一种使用哈希函数组织数据，以支持快速插入、删除和查找操作的数据结构。它是通过把键（Key）映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数称为哈希函数，存放记录的数组称为哈希表。

三、哈希函数

1、哈希函数设计原则

（1）哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值 域必须在0到m-1之间。
（2）哈希函数计算出来的地址能均匀分布在整个空间中。
（3）哈希函数应该比较简单。

2、常用的哈希函数

（1） 直接定址法–(常用)

A. 直接定址法通过某种固定的计算方式，直接将关键字映射到哈希表的某个位置上。这种映射通常是线性的，即哈希地址与关键字之间存在一种直接的、确定的数学关系。

B. 计算公式 直接定址法的计算公式一般形式为： H(key)=a×key+b
其中，H(key) 表示关键字 key 的哈希地址，a 和 b 是根据哈希表长度和关键字分布情况确定的常数。这个公式可以根据具体情况进行调整，但核心思想是通过简单的数学运算将关键字映射到哈希表的一个位置。

C.特点
简单直接：直接定址法的计算过程简单直接，没有复杂的迭代或递归过程。
确定性：对于同一个关键字，无论计算多少次，其哈希地址都是相同的，这保证了哈希表的确定性。
适用范围有限：直接定址法通常适用于关键字分布均匀且范围较小的情况。如果关键字范围过大或分布不均匀，可能会导致哈希表的某些位置空闲而另一些位置拥挤。
D. 应用场景 直接定址法适用于一些特定的应用场景，如：
关键字集合已知且固定不变的情况。 关键字范围较小且分布均匀的情况。 对哈希表的性能要求不是特别高的情况。
E.注意事项:在使用直接定址法时，需要注意以下几点：
根据关键字集合的实际情况选择合适的 a 和 b 值，以确保哈希地址分布均匀。
如果关键字范围过大或分布不均匀，可能需要考虑使用其他哈希函数构造方法，如除留余数法、平方取中法等。
在实际应用中，还需要考虑哈希表的扩容和冲突解决机制，以确保哈希表的性能。
综上所述，直接定址法是哈希表中一种简单直观的哈希函数构造方法，适用于特定的应用场景。在使用时需要根据实际情况进行选择和调整。

（2）除留余数法

A.除留余数法取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。 即：H(key)=key%p
其中，p是一个整数，且通常满足p≤m（m为散列表的长度）。为了确保哈希表的性能，p的选择很关键，一般推荐p为质数，或者至少是一个不包含小于20质因子的合数。

B.特点与优势
简单性：除留余数法的计算过程相对简单，容易实现。
灵活性：通过调整p的值，可以在一定程度上控制哈希表的性能。
适用性：适用于大多数关键字分布的情况，尤其是当关键字范围较大时。
C.缺点
可能造成key冲突。

四、哈希冲突

1、什么是哈希冲突

对于两个数据元素的关键字$k_i$和 $k_j$(i != j)，有$k_i$ != $k_j$，但有：Hash($k_i$) == Hash($k_j$)，即：不同关键字通过相同哈希函数计算出相同的哈希地址(哈希函数设计不够合理)，该种现象称为哈希冲突或哈希碰撞，如上述除留余数法中的5和13。

2、解决哈希冲突

闭散列

闭散列的基本原理是，当发生哈希冲突时，如果哈希表未被装满，那么在哈希表中必然还有空位置。因此，可以把产生冲突的元素存放到冲突位置的“下一个”空位置中去。这个“下一个”空位置可以通过某种探测方法找到，如线性探测、二次探测等。

（1）探测方法
线性探测：

从发生冲突的位置开始，依次向后探测，直到找到空位置为止。 例如，如果元素A的哈希地址为i，但位置i已被占用，则依次检查i+1, i+2, …，直到找到空位置。

二次探测：

发生哈希冲突时，通过二次探测法寻找“下一个”空位置。 公式为：Hi = (H0 + i2) % m 或 Hi = (H0 - i2) %m，其中H0是通过哈希函数计算得到的初始位置，m是哈希表的大小，i是探测次数（i=1,2,3,…，(m-1)/2）。

（2）使用闭散列实现哈希表
基本框架

//将K转化为整形
template<class K>
class InvertSize_t
{
public:size_t operator()(const K & key){return (size_t)key;}
};
//string类特化
template<>
class InvertSize_t<string>
{
public:size_t operator()(const string& key){size_t sum = 0;for (auto& e : key){sum = sum * 31 + e;}return sum;}
};//状态表示
enum State { EMPTY, EXIST, DELETE };//闭散列
template<class K, class V,class InvertKey = InvertSize_t<K>>
class HashTable
{//节点struct Elem{pair<K, V> _val;	//数据State _state;	//状态表示Elem(pair<K, V> val = pair<K, V>()):_val(val),_state(EMPTY){}};public://默认容量为10HashTable(size_t capacity = 10): _ht(capacity), _size(0){}private:vector<Elem> _ht;size_t _size;
};

模板参数：

K：键值类型
V：数据类型
InvertKey：将键值类型转化为整形的哈希函数，关于该函数的设计可参考：字符串哈希算法

节点成员变量：

标志当前位置的状态_state（空、存在、删除）
键值与数据构成的对组_val

闭散列哈希表类成员变量：

当前存在元素个数_size
储存哈希表的线性表_ht（默认长度为10）

插入
负载因子：
哈希表中的负载因子（Load Factor）是一个重要的概念，它用于衡量哈希表的填充程度，即哈希表中已存储元素的占用程度，当超过一定程度就进行扩容。

步骤：

（1）判断键值是否存在，若存在插入失败，不存在找到适合位置插入。
（2）判断是否需要扩容
（3）将键值转化为整形再通过哈希函数找到哈希值，再通过线性探测（也可以使用二次探测）找到合适位置（为空或者被删除的位置）进行元素储存。
（4）元素个数+1，状态修改为存在。

查找
步骤：

（1）将键值转化为整形再通过哈希函数找到哈希值，再通过线性探测（也可以使用二次探测）查找。
（2）当前哈希值位置如果为空，说明不存在该值，如果为删除就继续使用线性探测，如果为存在且键值不相同则继续，如果为存在且键值相同则成功找到。

删除
步骤：

（1）判断键值是否存在，若不存在删除失败，存在找到并删除。
（2）将键值转化为整形再通过哈希函数找到哈希值，再通过线性探测（也可以使用二次探测）找到该元素。
（3）元素个数-1，状态修改为删除。

当前元素个数

直接返回 _size即可。

判断是否为空

通过判断_size是否等于0

代码实现

//状态表示
enum State { EMPTY, EXIST, DELETE };//闭散列
template<class K, class V,class InvertKey = InvertSize_t<K>>
class HashTable
{//节点struct Elem{pair<K, V> _val;	//数据State _state;	//状态表示Elem(pair<K, V> val = pair<K, V>()):_val(val),_state(EMPTY){}};public:HashTable(size_t capacity = 10): _ht(capacity), _size(0){}// 插入bool Insert(const pair<K, V>& val){//是否存在，存在就不会插入if (Find(val.first))	return false;//转化为整数InvertKey ik;//除留余数法查找int hashi = ik(val.first) % _ht.size();//超过负载因子if (_size * 10 / _ht.size() >= 7){HashTable tmp(_ht.size() * 2);for (int i = 0; i < _ht.size(); i++){if (_ht[i]._state == EXIST){tmp.Insert(_ht[i]._val);}}_ht.swap(tmp._ht);}//当删除或者为空储存while (_ht[hashi]._state == EXIST){hashi = ++hashi % _ht.size();}_ht[hashi] = Elem(val);_ht[hashi]._state = EXIST;_size++;return true;}// 查找Elem* Find(const K& key){InvertKey ik;	//转化整形仿函数int hashi = ik(key) % _ht.size();	//除留余数法求哈希地址//查到为空即停止while (_ht[hashi]._state != EMPTY){//符合条件if (_ht[hashi]._state == EXIST && _ht[hashi]._val.first == key){return &_ht[hashi];}hashi = ++hashi % _ht.size();}return nullptr;}// 删除bool Erase(const K& key){//查找该值Elem* cur = Find(key);//不存在情况if (cur == nullptr)	return false;cur->_state = DELETE;//改变状态_size--;	//元素个数--return true;}//存在个数size_t Size()const{return _size;}//是否为空bool Empty() const{return _size == 0;}private:vector<Elem> _ht;size_t _size;
};

开散列

（1）开散列概念

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地 址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

（2）使用开散列实现哈希表

基础框架

//将K转化为整形
template<class K>
class InvertSize_t
{
public:size_t operator()(const K & key){return (size_t)key;}
};//string类特化
template<>
class InvertSize_t<string>
{
public:size_t operator()(const string& key){size_t sum = 0;for (auto& e : key){sum = sum * 31 + e;}return sum;}
};//哈希表节点
template<class T>
struct HashBucketNode
{HashBucketNode(const T& val): _pNext(nullptr), _val(val){}HashBucketNode<T>* _pNext;	//前驱指针T _val;	//数据
};template<class K,class T, class KeyOfValue, class HF >
class HashBucket
{typedef HashBucketNode<T> Node;	//节点重命名typedef HashBucket<K,T, KeyOfValue, HF> Self;	//自身重命名
public://构造函数 哈希桶初始化大小为10HashBucket(size_t capacity = 10): _table(10), _size(0)
{}
private:vector<Node*> _table;	//储存哈希桶头节点指针size_t _size;      // 哈希表中有效元素的个数
};

哈希表节点模板参数

T：数据类型

哈希表节点成员变量

_pNext：前驱指针
_val：数据

哈希表类模板参数

K：键值类型
T：数据类型
KeyOfValue：将数据转化为键值的仿函数类型
HF：将键值类型转化为整形的哈希函数

哈希表成员变量

_table：储存链表头节点指针的线性表
_size：元素个数

迭代器

迭代器类：
根据开散列哈希表的特性设计该迭代器为正向迭代器。

基础框架：

template<class K,class T,class  KeyOfValue,class HF,class Ptr,class Ref>
struct HsIterator
{
//重命名
typedef HashBucketNode<T> Node;
typedef HashBucket<K, T, KeyOfValue, HF> Hash;
typedef HsIterator<K, T, KeyOfValue, HF,Ptr,Ref> Self;
//成员变量
Node* _cur;	//当前指针
const Hash* _hash;	//哈希表指针
//构造函数
HsIterator(const  Hash* hash,  Node* cur ):_cur(cur),_hash(hash){}
}

迭代器类模板参数

K：键值类型
T：数据类型
KeyOfValue：将数据转化为键值的仿函数类型
HF：将键值类型转化为整形的哈希函数
Ptr: T* /const T*
Ref: T& / const T&

迭代器类成员变量

_cur：哈希节点指针
_hash:哈希表指针

重载前置++
步骤：

（1）判断迭代器中_cur的前驱指针是否为空。
（2）_cur的前驱指针不为空，说明该哈希桶没有遍历完，_cur =_cur->_pNext 即可。
（3）_cur的前驱指针为空，说明该哈希桶已经遍历完了，此时需要通过_cur->_val找到当前哈希桶的哈希值，哈希值++，再通过哈希表找到下一个哈希桶，如果不为空，_cur等于哈希桶的头节点，结束，否则继续++，直到找到不为空的或者将所有桶都遍历一遍。

重载 == 和 !=

通过指针是否相等来判断。

重载解引用

通过返回_cur->_val的引用。

重载->

通过返回_cur->_val的地址。

迭代器类代码实现：

//迭代器
template<class K,class T,class  KeyOfValue,class HF,class Ptr,class Ref>
struct HsIterator
{typedef HashBucketNode<T> Node;typedef HashBucket<K, T, KeyOfValue, HF> Hash;typedef HsIterator<K, T, KeyOfValue, HF,Ptr,Ref> Self;Node* _cur;const Hash* _hash;HsIterator(const  Hash* hash,  Node* cur ):_cur(cur),_hash(hash){}Self& operator++(){	KeyOfValue func;HF hf;if (_cur->_pNext != nullptr){_cur = _cur->_pNext;}else{int hashi = hf(func(_cur->_val)) % _hash->_table.size();Node* cur = _hash->_table[++hashi];while (hashi < _hash->_table.size() && cur == nullptr){cur = _hash->_table[hashi];hashi++;	}_cur = cur;}return *this;}bool operator==(const Self& it){return _cur == it._cur;}bool operator!= (const Self& it){return _cur != it._cur;}Ref operator*(){return _cur->_val;}Ptr operator->(){return &(_cur->_val);}
}; 

哈希表迭代器
begin()

找到第一个不为空的哈希桶，用该哈希桶头节点去构造迭代器。

end()

直接利用nullptr构造迭代器。

插入
步骤：

（1）判断哈希表中是否存在该键值 。
（2）如果存在，插入失败，结束。
加粗样式 （3）如果不存在，判断是否超过负载因子，超过就需要扩容。
（4）通过KeyOfValue 和 HF 函数来求哈希值，通过哈希值找到哈希桶，通过头插法将数据插入。

删除
步骤：

（1）判断哈希表中是否存在该键值 。
（2）如果不存在，删除失败，结束。
（3）通过KeyOfValue 和 HF 函数来求哈希值，通过哈希值找到哈希桶，将节点重新连接，再进行删除。

查找

通过KeyOfValue 和 HF 函数来求哈希值，通过哈希值找到哈希桶，在该桶遍历该桶。

大小

直接返回_size。

判断是否为空

通过_size是否等于0来判断。

清空

遍历哈希表，如果哈希桶不为空，再将哈希桶中的每个节点删除，最后在置空。

析构函数

复用清空接口即可。

拷贝构造

遍历需要拷贝的哈希表，如果哈希桶不为空，再将哈希桶中的每个节点插入新哈希表即可。

赋值重载

先清理原来的哈希表，再利用传过来的临时哈希表然后复用交换接口，进行交换即可。

开散列哈希表代码实现：

//将数据转化为整数
template<class	K>
class HashFunc
{
public:size_t operator()(const K& val){return val;}
};template<>
class HashFunc<string>
{
public:size_t operator()(const string& s){const char* str = s.c_str();unsigned int seed = 131; // 31 131 1313 13131 131313unsigned int hash = 0;while (*str){hash = hash * seed + (*str++);}return hash;}
};//将数据转化为键值
template<class K>
struct KeyOfValue
{const K& operator()(const K& data){return data;}
};//前置声明 -->给迭代器向上查找
template<class K, class T, class KeyOfValue, class HF >
class HashBucket;//哈希节点
template<class T>
struct HashBucketNode
{HashBucketNode(const T& val): _pNext(nullptr), _val(val){}HashBucketNode<T>* _pNext;	T _val;	//数据
};//迭代器
template<class K,class T,class  KeyOfValue,class HF,class Ptr,class Ref>
struct HsIterator
{typedef HashBucketNode<T> Node;typedef HashBucket<K, T, KeyOfValue, HF> Hash;typedef HsIterator<K, T, KeyOfValue, HF,Ptr,Ref> Self;Node* _cur;const Hash* _hash;HsIterator(const  Hash* hash,  Node* cur ):_cur(cur),_hash(hash){}Self& operator++(){	KeyOfValue func;HF hf;if (_cur->_pNext != nullptr){_cur = _cur->_pNext;}else{int hashi = hf(func(_cur->_val)) % _hash->_table.size();Node* cur = _hash->_table[++hashi];while (hashi < _hash->_table.size() && cur == nullptr){cur = _hash->_table[hashi];hashi++;	}_cur = cur;}return *this;}bool operator==(const Self& it){return _cur == it._cur;}bool operator!= (const Self& it){return _cur != it._cur;}Ref operator*(){return _cur->_val;}Ptr operator->(){return &(_cur->_val);}
}; template<class K,class T, class KeyOfValue, class HF >
class HashBucket
{typedef HashBucketNode<T> Node;	//节点重命名typedef HashBucket<K,T, KeyOfValue, HF> Self;	//自身重命名
public:typedef  HsIterator<K, T, KeyOfValue, HF, T*, T&> Iterator;	//迭代器重命名typedef HsIterator<K, T, KeyOfValue, HF,const T*,const T&> ConstIterator;	//const迭代器重命名//迭代器作为有友元template<class K, class T, class  KeyOfValue, class HF, class Ptr, class Ref>friend struct HsIterator;//构造函数 哈希桶初始化大小为10HashBucket(size_t capacity = 10): _table(10), _size(0){}//拷贝构造HashBucket(const Self& self){_table.resize(10);//通过遍历Self和插入接口即可for (int i = 0; i < self._table.size(); i++){Node* cur = self._table[i];while (cur){Insert(cur->_val);cur = cur->_pNext;}}}//赋值重载Self& operator=(Self self){Clear();Swap(self);return *this;}~HashBucket(){Clear();}Iterator Begin(){//找到第一个不为空的桶int i = 0;while (_table[i] == nullptr){i++;}return Iterator(this, _table[i]);}Iterator End(){//用nullptr代表最后一个元素的后一个位置return Iterator(this, nullptr);}ConstIterator Begin() const{int i = 0;while (_table[i] == nullptr){i++;}return ConstIterator(this, _table[i]);}ConstIterator End() const{return ConstIterator(this, nullptr);}//返回值：为了unordered_map的重载[]能够使用pair<bool, Iterator>Insert(const T & val){//将数据转化为键值KeyOfValue func;//不允许重复键值Iterator it = Find(func(val));if ( it != End()){return make_pair(false,it);}//将键值转化为整形（哈希地址）HF ik;int hashi = ik(func(val)) % _table.size();//超过负载因子if (_size == _table.size()){//库容2倍vector<Node*> tmp(_table.size() * 2);//将原来的数据转移到tmpfor (int i = 0; i < _table.size(); i++){if (_table[i] != nullptr){Node* cur = _table[i];while (cur){//重新获取哈希地址int k = ik(func(cur->_val)) % tmp.size();//头插入tmpNode* next = cur->_pNext;cur->_pNext = tmp[k];tmp[k] = cur;cur = next;}}}//将容器进行交换_table.swap(tmp);}//插入Node* cur = new Node(val);cur->_pNext = _table[hashi];_table[hashi] = cur;_size++;return make_pair(true, Iterator(this,cur));}// 删除哈希桶中为data的元素(data不会重复)bool Erase(const K& key){//将数据转化为键值KeyOfValue func;//将数据转化为键值HF ik;int hashi = ik(func(key)) % _table.size();//获取头节点Node* cur = _table[hashi];//前驱指针Node* prev = nullptr;while (cur){//找到，重新连接if (func(cur->_val) == key){if (prev == nullptr){_table[hashi] = cur->_pNext;}else{prev->_pNext = cur->_pNext;}_size--;delete cur;return true;}prev = cur;cur = cur->_pNext;}return false;}Iterator Find(const K& key){//将数据转化为键值KeyOfValue func;//将数据转化为键值HF ik;int hashi = ik(key) % _table.size();//获取头节点Node* cur = _table[hashi];//查找while (cur){if (func(cur->_val) == key){return Iterator(this,cur);}cur = cur->_pNext;}return Iterator(this, nullptr);}//大小size_t Size()const{return _size;}//是否为空bool Empty()const{return 0 == _size;}//清空void Clear(){//遍历容器清空每个节点for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_pNext;delete cur;cur = next;}//最后置空_table[i] = nullptr;}//大小为0_size = 0;}//交换void Swap(Self& ht){//交换内部容器即可_table.swap(ht._table);swap(_size, ht._size);}private:vector<Node*> _table;	//储存哈希桶头节点指针size_t _size = 0;      // 哈希表中有效元素的个数
};

五、哈希表的性能分析

时间复杂度分析

1、哈希表的时间复杂度分析主要关注其三个基本操作：查找（Search）、插入（Insert）和删除（Delete）。这些操作的时间复杂度通常依赖于几个关键因素：哈希函数的质量、哈希表的负载因子（即表中元素数量与表容量的比值）、以及冲突解决策略。
2、链地址法（Separate Chaining）：
在链地址法中，每个槽位维护一个链表，所有映射到该槽位的关键字都存储在这个链表中。查找、插入和删除操作的时间复杂度取决于链表的长度。在最坏情况下（即所有关键字都映射到同一个槽位），这些操作的时间复杂度会退化到O(n)，其中n是哈希表中元素的数量。但在平均情况下，如果哈希函数设计得当且负载因子适中，这些操作的时间复杂度可以接近O(1)。
3、开放地址法（Open Addressing）：
在开放地址法中，当发生哈希冲突时，算法会尝试在哈希表中的另一个槽位找到空闲位置来存储新的关键字。查找、插入和删除操作可能需要遍历多个槽位，直到找到所需的关键字或空闲位置。最常用的开放地址法是线性探测（Linear
Probing）、二次探测（Quadratic Probing）。这些方法的时间复杂度同样取决于负载因子和哈希函数的质量。在平均情况下，如果负载因子适中且哈希函数分布均匀，这些操作的时间复杂度也可以接近O(1)。但在最坏情况下（例如，所有关键字都映射到连续的槽位，并且这些槽位都被占满），这些操作的时间复杂度可能会退化到O(n)。
4、总结
哈希表的时间复杂度通常取决于哈希函数的质量、装载因子以及冲突解决策略。在理想情况下，哈希表的操作可以达到O(1)的时间复杂度。但在实际情况中，由于哈希冲突的存在，这些操作的时间复杂度可能会退化。然而，通过优化哈希函数、控制装载因子和选择合适的冲突解决策略，我们可以将哈希表的操作保持在接近O(1)的时间复杂度范围内。

空间复杂度分析

1、哈希表的空间复杂度通常是O(n)，其中n是哈希表中存储的元素个数。这是因为哈希表通过分配一个固定大小的数组（或类似的连续存储空间）来存储元素，并且这个数组的大小通常是基于预期的元素数量来选择的。尽管哈希表可能会预留一些额外的空间以减少哈希冲突和提高性能，但总体上，哈希表所需的空间与存储的元素数量成线性关系。
2、链地址法（Separate Chaining）：在链地址法中，每个槽位维护一个链表来存储所有映射到该槽位的关键字。这种情况下，哈希表的空间复杂度仍然是O(n)，因为虽然链表的长度可能随着冲突的增加而增长，但总体上，所有链表占用的空间仍然与存储的元素数量成线性关系。
3、开放地址法（Open Addressing）：在开放地址法中，哈希表通过探测空闲槽位来解决冲突。这种方法不需要额外的数据结构来存储冲突的元素，因此从空间复杂度的角度来看，它通常比链地址法更节省空间。然而，它可能会导致哈希表在达到其容量之前就开始拒绝新的插入操作（因为找不到空闲槽位），从而需要更频繁地进行扩容操作。