全球观点：哈希表总结

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

全球观点：哈希表总结

2022-12-14 20:16:33 来源：博客园

哈希表

理论讲解

元素通过确定的映射关系找到其在表中的存储位置，这个映射关系叫做哈希函数(散列函数)，==这张表就叫做哈希表(散列表)

(资料图片)

优势：适用于快速的查找，时间复杂度为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 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)
多线程环境中，线性探测所用到的基于数组实现的哈希表，只能给全局的表加互斥锁来保证对哈希表操作的原子性，保证线程安全！

分析

链式哈希表中每个桶都放一个链表，把发生哈希冲突的元素都挂到对应的桶上
哈希函数采用除留余数法，表长为素数

优化策略：
- 如果每个桶的链表比较长，那么链表搜索花费的时间就会比较长，时间复杂度会趋于O(1) ，这时可以考虑把链表转化成红黑树，红黑树的查找时间复杂度达到O(logn)
- 在多线程环境下，可以为链式哈希表的每个桶创建自己的分段锁，不同桶中的链表操作是可以并发执行的!

实现

#include #include #include #include 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> 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> 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是不一样的，即拥有不同的内存管理方式，那么就需要采用效率低的整个数据的交换

总结

关键词：时间复杂度成员变量计算数据