哈希表
理论讲解
元素通过确定的映射关系找到其在表中的存储位置,这个映射关系叫做哈希函数(散列函数),==这张表就叫做哈希表(散列表)
优势:适用于快速的查找,时间复杂度为O(1)
缺点:占用内存空间比较大,哈希表的空间效率还是不够高。链式哈希表,每个桶上存一个链表,而链表的每一个节点除了数据域外,还有地址域,1个地址要占4字节(8字节),如果数据规模很大的话,那么内存的占用量就会非常大,甚至无法进行完全存储。
无序关联容器unordered_set、unordered_map的底层实现就是哈希表
哈希函数
设计特点:
- 计算简单(太复杂会降低查询时间)
- 散列地址分布均匀(减少哈希冲突发生概率)
哈希函数:
- 除留余数法
- 数字分析法
- 平方取中法
- md5,sha加密hash算法等
哈希冲突(哈希碰撞)
元素通过哈希函数映射到同一个地址,就表示发生了哈希冲突
发生哈希冲突时的解决方法:
- 线性探测法 (开放定址法)
- 当前地址发生冲突了,就往后继续找空闲的位置
- 缺陷:当表中的元素越来越多时,线性探测法为了找到空闲位置需要遍历的长度就会越来越长,性能由O(1)逐渐达到O(n)
- 二次探测法:是对线性探测法的改进
- 链地址法
尽可能减少发生哈希冲突的概率:
- 哈希函数是除留余数法时,将哈希表的长度设为素数,确保计算后的哈希地址能够尽可能离散
- 哈希表的装载因子 loadfactor
已占用的桶的个数 / 桶的总个数 > loadfactor
时,哈希表就要进行扩容了,扩容时原来哈希表中的元素需要重新进行哈希,代价是比较大的, 时间复杂度达到O(n)
线性探测哈希表实现
分析
-
每个位置的状态:
-
正在使用
-
从未使用
-
当前位置的元素被删除
-
-
添加元素
扩容操作:如果 (已占用的桶的个数 / 桶的总个数 > loadfactor)则需要先进行扩容!!
通过哈希函数计算数据存放的位置(哈希地址)
-
如果该地址是空闲的,直接存储元素,完成
-
如果该位置被占用(发生冲突了),那么采用线程探测法继续往后找空闲的位置来存放元素
-
-
查询操作
通过哈希函数计算数据存放的位置,从该位置取值(需要判断该位置的状态是否为正在使用中)
-
如果取出的值 == 要查询的元素值,查询成功
-
如果取出的值 != 要查询的元素值(之前往这个位置放元素时,发生了哈希冲突),继续往后遍历查找该元素
-
-
删除操作
过哈希函数计算数据存放的位置,从该位置取值,判断状态是否为正在使用中
-
如果取出的值 == 要删除的值,直接修改当前位置的状态即可(置为已删除状态)
-
如果取出的值 != 要删除的值,继续往后遍历查找该元素,如果遇到某个位置为从未使用的状态,那么就说明哈希表中没有该元素
-
-
关于素数表
我们的哈希函数采用除留余数法,为了让地址更离散,表的长度设置为素数,我们能够通过程序得到固定范围内的所有素数(只能被1和本身整除),但是并不是每次扩容都是紧挨着进行扩容的,因为扩容的开销比较大,所以每次扩容的时候都扩大一点,素数的选择最好比较离散些。
可以参考该素数表:[3, 7, 23, 47, 97, 251, 443, 911, 1471, 42773]
实现
#include <iostream>
using namespace std;
// 桶状态
enum State
{
STATE_USEING,
STATE_UNUSED,//从未被用过
STATE_DEL,//用过但是已经删除
};
//桶结构
struct Bucket
{
Bucket(int key=0, State state = STATE_UNUSED)
:key_(key)
,state_(state)
{}
int key_;//桶存放的数据
State state_;//桶的状态信息
};
// 定义哈希表
class HashTable
{
public:
HashTable(int size=primeTable_[0], double loadfactor=0.75)
:tableSize_(size)
,useBucketNum_(0)
,loadfactor_(loadfactor)
,primeIdx_(0)
{
//我们要保证保证表长是素数(从线性表里取),所以需要对传入的size进行调整
int i = 0;
for (; i < PRIME_SIZE; i++)
{
if (primeTable_[i] >= size)
{
tableSize_ = primeTable_[i];
primeIdx_ = i;
break;
}
}
//传入的值过大,可以调整到最后一个素数
if (i == PRIME_SIZE)
{
primeIdx_--;
}
pBucket_ = new Bucket[tableSize_];
}
~HashTable()
{
delete[]pBucket_;
pBucket_ = nullptr;
}
// 增加元素操作
bool insert(int val)
{
//判断是否是要扩容
double factor = useBucketNum_ * 1.0 / tableSize_;
cout << "factor:" << factor << endl;
if (factor >= loadfactor_)
{
expand();//按照素数表进行扩容
}
// 采用除留余数法找到元素在哈希表中对应的位置
int idx = val % tableSize_;
int k = idx;
do
{
if (pBucket_[k].state_ != STATE_USEING)
{
pBucket_[k].state_ = STATE_USEING;
pBucket_[k].key_ = val;
useBucketNum_++;
return true;
}
k = (k + 1) % tableSize_;
} while (k != idx);//k遍历了一边后(实际上由于设置了装载因子并不会出现遍历一边的情况)还无法找到插入位置,则插入失败
return false;
}
// 查询操作
bool find(int val)
{
int idx = val % tableSize_;
int k = idx;
do
{
if (pBucket_[k].state_ == STATE_USEING && pBucket_[k].key_ == val)
{
return true;
}
k = (k + 1) % tableSize_;
} while (pBucket_[k].state_==STATE_UNUSED && k != idx);
return false;
}
// 删除操作
bool erase(int val)
{
if (useBucketNum_ == 0)
throw "哈希表为空,没有可删除元素!";
int idx = val % tableSize_;
int k = idx;
do
{
if (pBucket_[k].state_ == STATE_USEING && pBucket_[k].key_ == val)
{
pBucket_[k].state_ = STATE_DEL;
useBucketNum_--;
}
k = (k + 1) % tableSize_;
} while (pBucket_[k].state_ == STATE_UNUSED && k != idx);
return true;
}
private:
void expand()
{
//按照素数表进行扩容
if (primeIdx_+1 == PRIME_SIZE)
throw "the HashTable is too large,expand false!";
primeIdx_++;
Bucket* p = new Bucket[primeTable_[primeIdx_]];
// 遍历原哈希表中的元素,并对它们进行重新哈希
for (int i = 0; i < tableSize_; i++)
{
if (pBucket_[i].state_ == STATE_USEING)
{
// 用新表长哈希
int idx = pBucket_[i].key_% primeTable_[primeIdx_];
int k = idx;
do
{
if (p[k].state_ != STATE_USEING)
{// 不要再useBucketNum_++,因为已用桶的数量没有变
p[k].state_ = STATE_USEING;// 注意修改状态
p[k].key_ = pBucket_[i].key_;
break;
}
//线性探测用的也是新表长
k = (k + 1) % primeTable_[primeIdx_];
} while (k != idx);
}
}
tableSize_ = primeTable_[primeIdx_];
delete[]pBucket_;
pBucket_ = p;
}
Bucket* pBucket_;
int tableSize_;//哈希表长度
int useBucketNum_;//已用桶的数目
double loadfactor_;//装载因子,用于扩容
//素数表用于扩容
//所有哈希表对象都使用同一个素数表
//c++11中对静态整形常量可以在类内部初始化
static const int PRIME_SIZE = 10;//素数表大小
static int primeTable_[PRIME_SIZE];
int primeIdx_;//素数表索引,不同对象的索引值可能不同
};
int HashTable::primeTable_[PRIME_SIZE] = { 3,7,23,47,97,251,443,911,1471,42773 };
测试代码
int main()
{
HashTable htable;
htable.insert(21);
htable.insert(32);
htable.insert(14);
htable.insert(15);
htable.insert(22);
cout << htable.find(21) << endl;
htable.erase(21);
cout << htable.find(21) << endl;
}
链式哈希表实现
线性探测哈希表的缺陷:
- 发生哈希冲突时,采用线性探测法,时间复杂度会逐渐靠近O(n)
- 多线程环境中,线性探测所用到的基于数组实现的哈希表,只能给全局的表加互斥锁来保证对哈希表操作的原子性,保证线程安全!
分析
- 链式哈希表中每个桶都放一个链表,把发生哈希冲突的元素都挂到对应的桶上
- 哈希函数采用除留余数法,表长为素数
![](https://raw.githubusercontent.com/XIAJIUFAN/ImagesTwo/main/%E7%BD%91%E7%BB%9C%E7%BC%96%E7%A8%8B/202212141728361.png)
- 优化策略:
- 如果每个桶的链表比较长,那么链表搜索花费的时间就会比较长,时间复杂度会趋于O(1) ,这时可以考虑把链表转化成红黑树,红黑树的查找时间复杂度达到O(logn)
- 在多线程环境下,可以为链式哈希表的每个桶创建自己的分段锁,不同桶中的链表操作是可以并发执行的!
实现
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
class HashTable
{
public:
HashTable(int size = primeTable_[0], double loadfactor = 0.75)
:useBucketNum_(0)
,loadfactor_(loadfactor)
,primeIdx_(0)
{
// 需要将哈希表的长度调整到素数长度
for (; primeIdx_ < PRIME_SIZE; primeIdx_++)
{
if (primeTable_[primeIdx_] >= size)
{
table_.resize(primeTable_[primeIdx_]);
break;
}
}
if (primeIdx_ == PRIME_SIZE)
{
table_.resize(primeTable_[--primeIdx_]);
}
}
// 不需要再自定义析构函数了,vector成员变量会调用它的析构函数来释放占用的外部内存
void insert(int val)
{
// 1.插入前先判断需不需要扩容
// 先查看当前的装载程度
double factor = (useBucketNum_ * 1.0) / primeTable_[primeIdx_];
cout << "(当前装载程度)factor:" << factor << endl;
if (factor >= loadfactor_)
{
expand();
}
// 利用除留余数法(哈希函数)找到桶索引
int idx = val % primeTable_[primeIdx_];
if (table_[idx].empty())
{
// 仅当桶中的链表容器为空,要插入第一个元素时useBucketNum_++
useBucketNum_++;
// 头插法插入第一个元素
table_[idx].emplace_front(val);
}
else
{
// 去重操作-->或者说如果元素已经存在就不再进行插入操作
// 使用C++算法库提供的泛形函数
auto it = ::find(table_[idx].begin(), table_[idx].end(), val);
if (it == table_[idx].end()) //
{
// 要插入的是新元素
table_[idx].emplace_front(val);
}
}
}
bool erase(int val)
{
int idx = val % primeTable_[primeIdx_];
auto it = ::find(table_[idx].begin(), table_[idx].end(), val);
if (it != table_[idx].end())
{
table_[idx].erase(it);
// 删除后需要判断当前桶是否为空,空的话需要useBucketNum_--
if (table_[idx].empty())
{
useBucketNum_--;
}
return true;
}
return false;
}
bool find(int val)
{
int idx = val % primeTable_[primeIdx_];
auto it = ::find(table_[idx].begin(), table_[idx].end(), val);
if (it != table_[idx].end())
{
return true;
}
return false;
}
private:
void expand()
{
// 先判断是否允许再扩容
if (primeIdx_ + 1 == PRIME_SIZE)
throw "the HashTable is too large!";
primeIdx_++;
// 千万注意,由于扩容后需要重新哈希,所以链表的分布极有可能发生变化,所以要将useBucketNum_=0,重新记录!!!
useBucketNum_ = 0;
vector<list<int>> oldTable;
// 发生交换后,table_就是一张空表了
table_.swap(oldTable);
table_.resize(primeTable_[primeIdx_]);
// 把原来表中的每个元素重新哈希到扩容后的表中
for (auto list : oldTable)
{
for (auto key : list)
{
int idx = key % primeTable_[primeIdx_];
if (table_[idx].empty())
{
useBucketNum_++;
}
table_[idx].emplace_front(key);
}
}
}
vector<list<int>> table_; // 哈希表
int useBucketNum_; // 已用桶的数目
double loadfactor_; // 装载因子
static const int PRIME_SIZE = 10;
static int primeTable_[PRIME_SIZE];
int primeIdx_;
};
int HashTable::primeTable_[PRIME_SIZE] = { 3,7,23,47,97,251,443,911,1471,42773 };
测试代码
int main()
{
HashTable htable;
htable.insert(21);
htable.insert(32);
htable.insert(14);
htable.insert(15);
htable.insert(22);
htable.insert(23);
cout << htable.find(21) << endl;
htable.erase(21);
cout << htable.find(21) << endl;
return 0;
}
关于代码中的table_.swap()
操作,这个操作的效率会不会比较低?
-
实际上,这里两个容器只是把成员变量做了一个交换,也就是底层指针的指向做了交换,并没有涉及内存的构造,拷贝,所以效率是很高的
-
**注意: **
- 如果两个容器使用的空间配置器allocator是一样的,即拥有相同的内存管理方式,那么可以使用swap操作,成员变量直接交换,效率高!
- 如果两个容器使用的空间配置器allocator是不一样的,即拥有不同的内存管理方式,那么就需要采用效率低的整个数据的交换