C++的哈希 哈希表 哈希桶

目录

Unordered系列关联式容器

什么是哈希

哈希表

闭散列

载荷因子α

扩容

查找

删除 

字符串哈希算法

最终代码

开散列

插入

查找

删除

最终代码

完整代码

Unordered系列关联式容器

C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可以达到log_2 N，即最差情况下要比较红黑树的高度次（树中的结点特别多且有序）：

        但又因为键值对与其存储位置之间没有对应的关系，查找一个元素时必须要多次比较键值对的键，而我们理想中的搜索方法应该是“可以不经过任何比较，一次直接从表中得到要搜索的元素”，而实现这一搜索方法应该需要构造一种存储结构，通过某种函数使元素的存储位置与它的键值对的键之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素，所以C++11中又提供了4个unordered系列的关联式容器unordered_map、unordered_set、unordered_multimap、unordered_multiset，它们与之前的map、set等容器的使用方式基本类似，只是底层结构不同，unordered序列的关联式容器的底层结构是哈希表，这使得它们在查询时的时间复杂度可以达到O（1）

什么是哈希

基本概念：哈希是一种将任意大小的数据映射到固定大小的值（通常为整数）的思想（建立值和值存储间的映射关系）

注意事项：哈希是一种思想，哈希表是基于哈希表的实现的一种数据结构 

哈希表

基本概念：本质是一个数组。这个数组的每个位置（称为桶或槽）用于存储键值对，哈希表需要使用哈希函数依据键值对中key将该键值对映射到数组的某个位置，因为如果直接映射会出现“值不易映射”和“值分散”的问题

  • 值不易映射：键的类型是string、结构体类型的对象
  • 值分散：多个值之间的差值过大导致的空间浪费（存放并建立10001、11、55、24、19与存放位置间的映射关系，如果不做特殊处理就需要开辟很大的数组来存放这些数

“除留余数法”可以解决值分散的问题（使得值的大小和空间无关），但会出现哈希冲突问题（此外引起哈希冲突的一个原因可能是：哈希函数设计不够合理）：

哈希函数： 将key转换为数组（哈希表）的索引（可能是一行代码，也可能是一个函数）

哈希函数的设计理念：

  • 均匀性：一个好的哈希函数应该能够尽可能地将不同的键映射到不同的哈希值，以确保数据在哈希表中分布均匀。这样可以减少哈希冲突的可能性，提高哈希表的效率

  • 确定性：哈希函数应该是确定性的，即对于相同的输入键，哈希函数应该始终返回相同的哈希值。这是保证哈希表中数据一致性的重要特性

  • 简单性：尽量设计简单的哈希函数，以降低计算成本和实现复杂度，计算哈希值所需的时间应该是常量级的，这样可以确保哈希表的操作效率高，不会成为性能瓶颈

  • 有效性：如果散列表有 m 个地址（桶），则哈希函数的值域（输出范围）必须在 0 到 m-1 之间，以确保哈希值可以映射到散列表的有效地址范围内

常见的哈希函数：

  • 除留余数法：hash = key % table_size
  • 直接定址法：
  • Multiplicative Hash Function：hash = floor(table_size * (key * A % 1))
  • 平方取中法：key = 1234，key^2 = 1522756，取中间的 227 作为哈希值
  • FNV Hash (Fowler-Noll-Vo)：
uint32_t fnv1a_hash(const std::string& key) {uint32_t hash = 2166136261u; // FNV offset basisfor (char c : key) {hash ^= c;hash *= 16777619;}return hash;
}
  • DJB2 Hash：
uint32_t djb2_hash(const std::string& key) {uint32_t hash = 5381;for (char c : key) {hash = ((hash << 5) + hash) + c; // hash * 33 + c}return hash;
}

注意事项：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

哈希冲突：当不同的键被哈希函数映射到相同的索引时，称为哈希冲突，哈希表需要处理这些冲突，常见的方法有链地址法（开散列）和开放地址法（闭散列）

闭散列

基本概念：发生冲突时，通过探测（如线性探测、二次探测或双重哈希等方法）来寻找下一个键可用的位置

优点：不需要额外的存储空间，访问速度快

缺点：探测过程中可能出现“聚集”现象使得存放效率降低，且它的删除操作复杂

删除操作复杂的原因：

1、寻找一个数字时，先去该数字的映射位置寻找，找不到就继续向后寻找，如果遇到空时还没找到就停止寻找（因为如果映射位置没有，那么该数字一定是在映射位置后的某个位置插入了，插入时应该是数字、新数字 ...而不是空 新数字 ...）

2、如果按照上述的方式寻找一个数字，那么当删除目标数字前的某个数字时就会导致虽然目标数字存在但是找不到目标数字的问题

删除操作：

1、映射位置除了要存放数值外，还要存放一个标志位，用于标识当前映射位置的状态

enum State
{EMPTY,//为空EXIST,//存在DELETE//删除
};
  • 当55被删除后，它的状态被设为删除而不是空，这样就可以接着继续向后寻找

进行插入操作前先进行依据上面的内容写出插入操作（负载因子后面有描述）：

bool Insert(const pair<K, V>& kv)
{//防止冗余if (Find(kv.first))return false;//当负载因子大于等于0.7时进行扩容，以空间换时间if (_n * 10 / _table.size() >= 0.7)//采用/取整得不到小数，所以直接令_n * 10 {//新建一个哈希表HashTable<K,V, Hash> newHT;//确定新哈希表的大小newHT._table.resize(_table.size() * 2);//将旧表中的键重新映射到新表中for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state ==  EXIST)//原表中某下标的状态为存在时，将原表某下标中存放的键值对插入新表中{newHT.Insert(_table[i]._kv);//直接复用Insert操作}}_table.swap(newHT._table);}size_t hashi = kv.first % _table.size();//获取映射位置，应该键值的key % 数组中有效元素的个数//线性探测while (_table[hashi]._state == EXIST)//探查到目标映射位置存在数字时就进行探测{++hashi;hashi %= _table.size();//取模的方式防止hashi越界}//确定好位置后进行插入_table[hashi]._kv = kv;//在合适的映射位置插入_table[hashi]._state = EXIST;//然后后将该位置的状态标识为EXIST++_n;//哈希表中有效数据元素+1return true;
}

注意事项：哈希表的大小（table_size）和底层数组的容量（capacity）是两个不同的概念， 假设我们有一个哈希表，初始大小为 7（即 table_size = 7），底层数组的容量为 10（即 capacity = 10）。我们有一组键需要插入到哈希表中：{10, 20, 30, 40, 50}:

哈希函数为 hash = key % table_size：

  • 10 % 7 = 3，键 10 存储在桶 3
  • 20 % 7 = 6，键 20 存储在桶 6
  • 30 % 7 = 2，键 30 存储在桶 2
  • 40 % 7 = 5，键 40 存储在桶 5
  • 50 % 7 = 1，键 50 存储在桶 1

哈希函数为 hash = key % capacity：

  • 10 % 10 = 0，键 10 存储在桶 0
  • 20 % 10 = 0，键 20 存储在桶 0（冲突）
  • 30 % 10 = 0，键 30 存储在桶 0（冲突）
  • 40 % 10 = 0，键 40 存储在桶 0（冲突）
  • 50 % 10 = 0，键 50 存储在桶 0（冲突）

        可以看出，使用 capacity 作为模数会导致所有键都存储在桶 0，导致严重的冲突和性能下降。而使用 table_size 作为模数可以确保键均匀地分布在不同的桶中，从而提高查找效率，此外，如果table_size 满了也会出现陷入死循环问题，为此引入了闭散列的另一个重要概念：载荷因子α（一定要分清底层容器大小capacity、哈希表的大小hash_table.size、哈希表中存放的有效数据个数n，一般情况下哈希表的大小和底层容器大小的设定是分开的，但也可以让它们两个相等）
 

载荷因子α

基本概念：载荷因子α表示哈希表中已存储元素数量与哈希表容量的比值，即哈希表的填充程度，载荷因子是开放定址法中十分重要的因素

计算公式：α = 填入表中的元素个数 / 哈希表的长度

α 越高，冲突率越高，插入等操作的效率越低，空间利用率越高

α 越低，冲突率越低，插入等操作的效率越高，空间利用率越低

α 的取值应该严格控制在0.7~0.8之间

扩容

中心思想：扩容时需要将原表中参与映射的键在新表中重新映射一次

vector的swap方法：vector：：swap - C++ 参考 (cplusplus.com)

问题：_table.swap（newHT._table）时都做了什么？

  1. 交换容量：当前可以存储的元素数量被交换
  2. 交换大小：当前已存储的元素数量被交换
  3. 结论：交换了双方的数据结构，_table 现在持有新表的数据结构，而 newHT 持有旧表的数据结构，函数结束后 newHT 会被自动销毁，从而实现了高效的扩容操作

  交换不会改变新旧表的地址：

cout <<"交换前旧表的地址为:" <<  & _table << endl;
cout <<"交换前新表的地址为:" <<  &newTable << endl;_table.swap(newTable);//交换cout << "交换后旧表的地址为:" << &_table << endl;
cout << "交换后新表的地址为:" << &newTable << endl;

查找

HashDate<K, V>* Find(const K& key)
{//计算要查早的键的映射位置size_t hashi = key % _table.size();//获取映射位置，应该键值的key % 数组中有效元素的个数//线性探测while (_table[hashi]._state != EMPTY)//到映射位置上去查找，如果该位置上不为空，{if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)//不为空还有两种删除和存在两种情况，需要满足位置的状态为存在时才可以//错误的：if (_table[hashi]._kv.first == key)//不为空还有两种删除和存在两种情况，需要满足位置的状态为存在时才可以{return &_table[hashi];//返回该位置的地址}++hashi;hashi %= _table.size();//取模的方式防止hashi越界}return nullptr;//找不到就返回空}

删除 

bool Erase(const K& key)
{HashDate<K, V>* ret = Find(key);if (ret == nullptr){return false;}else{ret->_state = DELETE;//这里只是将删除键所处位置的状态标识符改为了DELETE--_n;return true;}
}

字符串哈希算法

基本概念：key不支持强转为整型后取模，需要自己提供转换为整型的仿函数，仿函数中的()重载一般为将字符串映射成固定长度的哈希值的算法（stoi只能处理"1112"类型的字符串，但是除了不了"2115few"甚至是由汉字组成的字符串"样非分"），常见的字符串哈希算法如下：

1、DJB2

unsigned long djb2(const std::string& str) {unsigned long hash = 5381;for (char c : str) {hash = ((hash << 5) + hash) + c; // hash * 33 + c}return hash;
}

2、SDBM

unsigned long sdbm(const std::string& str) {unsigned long hash = 0;for (char c : str) {hash = c + (hash << 6) + (hash << 16) - hash;}return hash;
}

3、BKDR Hash

unsigned long bkdrHash(const std::string& str) {unsigned long seed = 131; // 31, 131, 1313, 13131, 131313, etc.unsigned long hash = 0;for (char c : str) {hash = hash * seed + c;}return hash;
}

4、ELF Hash 

unsigned long elfHash(const std::string& str) {unsigned long hash = 0;unsigned long x = 0;for (char c : str) {hash = (hash << 4) + c;if ((x = hash & 0xF0000000L) != 0) {hash ^= (x >> 24);}hash &= ~x;}return hash;
}

5、FNV-1a Hash

unsigned long fnv1aHash(const std::string& str) {const unsigned long fnv_prime = 0x100000001b3;const unsigned long offset_basis = 0xcbf29ce484222325;unsigned long hash = offset_basis;for (char c : str) {hash ^= c;hash *= fnv_prime;}return hash;
}

6、MD5

#include <openssl/md5.h>std::string md5Hash(const std::string& str) {unsigned char digest[MD5_DIGEST_LENGTH];MD5((unsigned char*)str.c_str(), str.size(), (unsigned char*)&digest);    char mdString[33];for(int i = 0; i < 16; i++)sprintf(&mdString[i*2], "%02x", (unsigned int)digest[i]);return std::string(mdString);
}

7. SHA-1 

#include <openssl/sha.h>std::string sha1Hash(const std::string& str) {unsigned char hash[SHA_DIGEST_LENGTH];SHA1((unsigned char*)str.c_str(), str.size(), hash);char buf[SHA_DIGEST_LENGTH*2];for (int i = 0; i < SHA_DIGEST_LENGTH; i++)sprintf((char*)&(buf[i*2]), "%02x", hash[i]);return std::string(buf);
}

 参考网址：各种字符串Hash函数 - clq - 博客园 (cnblogs.com)

BKDR Hash的综合评分是最高的，ELF Hash的综合评分是最低的

为了泛型编程一般需要两种仿函数：处理可以强转为int的仿函数 和 处理不能强转为int的仿函数

//可以直接强转的类型，将它们强转为size_t类型,因为即使是整数也可能为负
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
//这里采用的是BKDR Hash字符串哈希算法写的仿函数
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash = hash * 131 + ch;}return hash;}
};

最终代码

#pragma once#include <iostream>
#include <vector>
#include <utility>
using namespace std;//将该仿函数放在了命名空间外，使得开散列和闭散列都可以使用该仿函数
//可以直接强转的类型，将它们强转为size_t类型,因为即使是整数也可能为负
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};//对HashFunc采用特化处理，如果是int等就会用上面的仿函数，如果是string就会用该特化版本的HashFunc
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash = hash * 131 + ch;}return hash;}
};namespace open_address
{enum State{EMPTY,EXIST,DELETE};template<class K, class V>struct HashDate{pair<K, V> _kv;State _state = EMPTY;//默认情况下为EMPTY};//处理字符串类型的强制类型转换struct StringHashFunc{size_t operator()(const string& key){size_t hashi = 0;for (auto ch : key){hashi = hashi * 131 + ch;}return hashi;}};template <class K, class V, class Hash = HashFunc<K>>//强转方式的缺省值是强转为整型class HashTable{public://实例化哈希表时，将哈希表的大小和底层数组的容量均调整为10HashTable(){_table.resize(10);} bool Insert(const pair<K, V>& kv){//防止冗余if (Find(kv.first))return false;//当负载因子大于等于0.7时进行扩容，以空间换时间if (_n * 10 / _table.size() >= 0.7)//采用/取整得不到小数，所以直接令_n * 10 {//新建一个哈希表HashTable<K,V, Hash> newHT;//确定新哈希表的大小newHT._table.resize(_table.size() * 2);//将旧表中的键重新映射到新表中for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state ==  EXIST)//原表中某下标的状态为存在时，将原表某下标中存放的键值对插入新表中{newHT.Insert(_table[i]._kv);//直接复用Insert操作}}_table.swap(newHT._table);}Hash sh;//处理强转为整型的仿函数size_t hashi = sh(kv.first) % _table.size();//获取映射位置，应该键值的key % 数组中有效元素的个数//线性探测while (_table[hashi]._state == EXIST)//探查到目标映射位置存在数字时就进行探测{++hashi;hashi %= _table.size();//取模的方式防止hashi越界}//确定好位置后进行插入_table[hashi]._kv = kv;//在合适的映射位置插入_table[hashi]._state = EXIST;//然后后将该位置的状态标识为EXIST++_n;//哈希表中有效数据元素+1return true;}HashDate<K, V>* Find(const K& key){Hash hs;//处理强转为整型的仿函数//计算要查早的键的映射位置size_t hashi = hs(key) % _table.size();//获取映射位置，应该键值的key % 数组中有效元素的个数//线性探测while (_table[hashi]._state != EMPTY)//到映射位置上去查找，如果该位置上不为空，{if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)//不为空还有两种删除和存在两种情况，需要满足位置的状态为存在时才可以//错误的：if (_table[hashi]._kv.first == key)//不为空还有两种删除和存在两种情况，需要满足位置的状态为存在时才可以{return &_table[hashi];//返回该位置的地址}++hashi;hashi %= _table.size();//取模的方式防止hashi越界}return nullptr;//找不到就返回空}bool Erase(const K& key){HashDate<K, V>* ret = Find(key);if (ret == nullptr){return false;}else{ret->_state = DELETE;//删除时只是将该位置的标识符置为了DELETE该位置上还存放着一个键，只不过该键可以被随时替换--_n;return true;}}private:vector<HashDate<K, V>> _table;//哈希表的大小和底层数组的容量都是通过 _table来管理的，正常情况下哈希表的大小_table.size和底层数组的容量是要分开的size_t _n;//哈希表中的有效数据个数};void TeshHT1(){int a[] = { 10001,11,55,24,19,12,31 };HashTable<int, int>  ht;//使用缺省的强转方式for (auto e : a){ht.Insert(make_pair(e, e));}cout << ht.Find(55) << endl;cout << ht.Find(31) << endl;ht.Erase(55);cout << ht.Find(55) << endl;cout << ht.Find(31) << endl;}void TeshHT2(){使用StringHashFunc//HashTable<string, int, StringHashFunc> ht;//ht.Insert(make_pair("sort", 1));//ht.Insert(make_pair("left", 1));//ht.Insert(make_pair("insert", 1));//查看是否可以用仿函数StringHashFunc将string转换为整型（与上面的内容无关）StringHashFunc()实例化一个匿名的仿函数类对象，然后("bacd")向该仿函数传参//cout << StringHashFunc()("bacd") << endl;//cout << StringHashFunc()("abcd") << endl;//cout << StringHashFunc()("aadd") << endl;//使用特化版本HashTable<string, int> ht;ht.Insert(make_pair("sort", 1));ht.Insert(make_pair("left", 1));ht.Insert(make_pair("insert", 1));//查看是否可以用仿函数的特化版本HashFunc<string>将string转换为整型cout << HashFunc<string>()("bacd") << endl;cout << HashFunc<string>()("abcd") << endl;cout << HashFunc<string>()("aadd") << endl;}}

开散列

基本概念：将所有映射到相同哈希值的元素存储在一个链表或其他结构中，冲突发生时就将冲突位置的链表结点++，这样每个哈希表的桶实际上是一个指向链表头部的指针

优点：冲突处理简单，扩展容易，删除操作高效

缺点：需要额外的存储空间来存储链表节点，可能导致内存碎片

  • 可以是尾插但是尾插还要去寻找尾，而且发生冲突存入同一位置的结点也是有顺序的双向循环差入也行，但是没必要

插入

//采用头插的方式
bool Insert(const pair<K, V>& kv)
{//防止冗余if(Find(kv.first))return false;//如果还是重新建立映射关系，如果结点个数过多，在新表创建结点和移动后删除旧表的结点需要很多的资源//因为是队列是一个个挂在数组上的，所以当存放的有效元素个数 == 数组大小时才需要扩容//if (_n == _table.size())//{//	//新建一个哈希表//	HashTable<K, V> newHT;//	//确定新哈希表的大小//	newHT._table.resize(_table.size() * 2);//	//将旧表中的键重新映射到新表中//	for (size_t i = 0; i < _table.size(); i++)//每一次的for循环都是将某一个数组下标中的结点都链接到新表中//	{//		Node* cur = _table[i];//		while (cur)//		{//			newHT.Insert(_table[i]._kv);//直接复用Insert操作//			cur = cur->_next;//		}//	}//	_table.swap(newHT._table);//使用交换新旧表名中代表的地址信息//}//应该在确认了映射关系后，直接将旧表中的所有结点移动到新表中，这样移动后旧表中只用析构一个vector，且不用创建新的结点if (_n == _table.size()){vector<Node*> newTable(_table.size() * 2, nullptr);//设定新表大小及初始化各个位置for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];//cur指向旧表的下标为i位置的结点（该结点是一条链表的头结点）//遍历一条链表while (cur){Node* next = cur->_next;//next存放cur的下一个结点的位置//确定将旧表cur指向的结点要头插新表的哪个位置size_t hashi = cur->_kv.first % newTable.size();cur->_next = newTable[hashi];//头插（忘了回去看外面的注释，这点就是有点会让人发懵）newTable[hashi] = cur;cur = next;//cur指向自己的下一个结点}_table[i] = nullptr;//置空}/*cout <<"交换前旧表的地址为:" <<  & _table << endl;cout <<"交换前新表的地址为:" <<  &newTable << endl;*/_table.swap(newTable);//交换/*	cout << "交换后旧表的地址为:" << &_table << endl;cout << "交换后新表的地址为:" << &newTable << endl;*/}size_t hashi = kv.first % _table.size();Node* newnode = new Node(kv);//匿名结点对象//头插（数组中某个位置没有结点插入时_table[hashi] == nullptr）newnode->_next = _table[hashi];//_新结点的next结点指向当前链表的头指针指向的结点_table[hashi] = newnode;//令链表头指针指向新结点++_n;return true;//哈希桶的头插类似于://Node* head = nullptr; // 初始化一个空的链表，现在数组中每个位置都是一个空指针//void insertAtHead(int value) {//	Node* newNode = new Node(value); // 创建一个新节点//	newNode->next = head; // 将新节点的后继节点指向当前的头节点//	head = newNode; // 更新头节点指针，使其指向新节点//}
}

假设我们有以下插入过程：

  1. 初始状态：

    • _tables 被初始化为大小为 10 的向量，每个元素都是 nullptr。
    • 这意味着 _tables[0] 到 _tables[9] 都是 nullptr。

  2. 第一次插入：

    • 插入键值对 (key1, value1)。
    • 计算哈希值 hashi = key1 % 10，假设 hashi 为 2。
    • 创建新节点 newnode，其 _kv 为 (key1, value1)，且 _next 初始化为 nullptr。
    • newnode->_next = _tables[hashi]; 此时 _tables[2] 是 nullptr，因此 newnode->_next 也指向 nullptr。
    • 将 newnode 赋值给 _tables[hashi]，即 _tables[2] = newnode。

  3. 第二次插入：

    • 插入键值对 (key2, value2)。
    • 计算哈希值 hashi = key2 % 10，假设 hashi 仍然为 2。
    • 创建新节点 newnode，其 _kv 为 (key2, value2)，且 _next 初始化为 nullptr。
    • newnode->_next = _tables[hashi]; 此时 _tables[2] 已经指向第一个节点（即存储 (key1, value1) 的节点），所以 newnode->_next 指向这个第一个节点。
    • 将 newnode 赋值给 _tables[hashi]，即 _tables[2] = newnode。

通过这种方式，链表中的节点按插入顺序逆序排列，因为每次新节点都插入到链表的头部。

查看扩容过程的视频：20240526_213552-CSDN直播

结论：交换过程中结点的地址不发生改变，存放结点存放的位置一直在改变，且重新插入后一条链表中结点的先后顺序发生改变，原本的头变成了尾；交换结束后新旧表的地址不变使用&新表对象得到的依然是原地址，而不是旧表的地址，实际交换的是两个表的各个数据结构

查找

Node* Find(const K& key)
{size_t hashi = kv.first % _tables.size();Node* cur = _tables[hashi];//直接去映射位置上查找while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;
}

删除

bool Erase(const K& key)
{Hash hs;size_t hashi = hs(key) % _table.size();Node* prev = nullptr;Node* cur = _table[hashi];//直接去映射位置上查找while (cur){if (cur->_kv.first == key){delete cur;}	else{prev = cur->_next;cur = prev;}cur = cur->_next;}return nullptr;
}

最终代码

namespace hash_bucket
{template<class K, class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}};//template<class T>//struct HashNode//{//	T _data;//	HashNode<T>* _next;//	HashNode(const T& data)//		:_data(data)//		, _next(nullptr)//	{}//};template<class K,class V, class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:HashTable(){_table.resize(10, nullptr);//初始化时，数组中有十个位置，每个位置都存放的是空指针_n = 0;}//哈希表的底层容器vector函数结束后自动析构，但是vector中各个位置存放的都是自定义类型Node，自定义类型的析构时会调用它们的析构函数，所以还要重新写一个析构函数~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;//删除一个位置上的一整条链表就将该位置存放的指针置空}}//采用头插的方式bool Insert(const pair<K, V>& kv){//防止冗余if (Find(kv.first))return false;Hash hs;//如果还是重新建立映射关系，如果结点个数过多，在新表创建结点和移动后删除旧表的结点需要很多的资源//因为是队列是一个个挂在数组上的，所以当存放的有效元素个数 == 数组大小时才需要扩容//if (_n == _table.size())//{//	//新建一个哈希表//	HashTable<K, V> newHT;//	//确定新哈希表的大小//	newHT._table.resize(_table.size() * 2);//	//将旧表中的键重新映射到新表中//	for (size_t i = 0; i < _table.size(); i++)//每一次的for循环都是将某一个数组下标中的结点都链接到新表中//	{//		Node* cur = _table[i];//		while (cur)//		{//			newHT.Insert(_table[i]._kv);//直接复用Insert操作//			cur = cur->_next;//		}//	}//	_table.swap(newHT._table);//使用交换新旧表名中代表的地址信息//}//应该在确认了映射关系后，直接将旧表中的所有结点移动到新表中，这样移动后旧表中只用析构一个vector，且不用创建新的结点if (_n == _table.size()){vector<Node*> newTable(_table.size() * 2, nullptr);//设定新表大小及初始化各个位置for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];//cur指向旧表的下标为i位置的结点（该结点是一条链表的头结点）//遍历一条链表while (cur){Node* next = cur->_next;//next存放cur的下一个结点的位置//确定将旧表cur指向的结点要头插新表的哪个位置size_t hashi = hs(cur->_kv.first) % newTable.size();cur->_next = newTable[hashi];//头插（忘了回去看外面的注释，这点就是有点会让人发懵）newTable[hashi] = cur;cur = next;//cur指向自己的下一个结点}_table[i] = nullptr;//置空}/*cout <<"交换前旧表的地址为:" <<  & _table << endl;cout <<"交换前新表的地址为:" <<  &newTable << endl;*/_table.swap(newTable);//交换/*	cout << "交换后旧表的地址为:" << &_table << endl;cout << "交换后新表的地址为:" << &newTable << endl;*/}size_t hashi = hs(kv.first) % _table.size();Node* newnode = new Node(kv);//匿名结点对象//头插（数组中某个位置没有结点插入时_table[hashi] == nullptr）newnode->_next = _table[hashi];//_新结点的next结点指向当前链表的头指针指向的结点_table[hashi] = newnode;//令链表头指针指向新结点++_n;return true;//哈希桶的头插类似于://Node* head = nullptr; // 初始化一个空的链表，现在数组中每个位置都是一个空指针//void insertAtHead(int value) {//	Node* newNode = new Node(value); // 创建一个新节点//	newNode->next = head; // 将新节点的后继节点指向当前的头节点//	head = newNode; // 更新头节点指针，使其指向新节点//}}//链表的遍历Node* Find(const K& key){Hash hs;size_t hashi = hs(key) % _table.size();Node* cur = _table[hashi];//直接去映射位置上查找while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){Hash hs;size_t hashi = hs(key) % _table.size();Node* prev = nullptr;Node* cur = _table[hashi];//直接去映射位置上查找while (cur){if (cur->_kv.first == key){delete cur;}else{prev = cur->_next;cur = prev;}cur = cur->_next;}return nullptr;}private:vector<Node*> _table;//数组中的每个位置存放的都是结点的指针size_t _n;};void HashTest1(){int a[] = { 10001,11,55,24,19,12,31,4,34,44 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}//ht.Insert(make_pair(32, 32));//ht.Insert(make_pair(32, 32));}void HashTest2(){HashTable<string, int> ht;ht.Insert(make_pair("sort", 1));ht.Insert(make_pair("left", 1));ht.Insert(make_pair("insert", 1));}
}

完整代码

#pragma once#include <iostream>
#include <vector>
#include <utility>
using namespace std;//将该仿函数放在了命名空间外，使得开散列和闭散列都可以使用该仿函数
//可以直接强转的类型，将它们强转为size_t类型,因为即使是整数也可能为负
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};//对HashFunc采用特化处理，如果是int等就会用上面的仿函数，如果是string就会用该特化版本的HashFunc
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash = hash * 131 + ch;}return hash;}
};namespace open_address
{enum State{EMPTY,EXIST,DELETE};template<class K, class V>struct HashDate{pair<K, V> _kv;State _state = EMPTY;//默认情况下为EMPTY};//处理字符串类型的强制类型转换struct StringHashFunc{size_t operator()(const string& key){size_t hashi = 0;for (auto ch : key){hashi = hashi * 131 + ch;}return hashi;}};template <class K, class V, class Hash = HashFunc<K>>//强转方式的缺省值是强转为整型class HashTable{public://实例化哈希表时，将哈希表的大小和底层数组的容量均调整为10HashTable(){_table.resize(10);} bool Insert(const pair<K, V>& kv){//防止冗余if (Find(kv.first))return false;//当负载因子大于等于0.7时进行扩容，以空间换时间if (_n * 10 / _table.size() >= 0.7)//采用/取整得不到小数，所以直接令_n * 10 {//新建一个哈希表HashTable<K,V, Hash> newHT;//确定新哈希表的大小newHT._table.resize(_table.size() * 2);//将旧表中的键重新映射到新表中for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state ==  EXIST)//原表中某下标的状态为存在时，将原表某下标中存放的键值对插入新表中{newHT.Insert(_table[i]._kv);//直接复用Insert操作}}_table.swap(newHT._table);}Hash sh;//处理强转为整型的仿函数size_t hashi = sh(kv.first) % _table.size();//获取映射位置，应该键值的key % 数组中有效元素的个数//线性探测while (_table[hashi]._state == EXIST)//探查到目标映射位置存在数字时就进行探测{++hashi;hashi %= _table.size();//取模的方式防止hashi越界}//确定好位置后进行插入_table[hashi]._kv = kv;//在合适的映射位置插入_table[hashi]._state = EXIST;//然后后将该位置的状态标识为EXIST++_n;//哈希表中有效数据元素+1return true;}HashDate<K, V>* Find(const K& key){Hash hs;//处理强转为整型的仿函数//计算要查早的键的映射位置size_t hashi = hs(key) % _table.size();//获取映射位置，应该键值的key % 数组中有效元素的个数//线性探测while (_table[hashi]._state != EMPTY)//到映射位置上去查找，如果该位置上不为空，{if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)//不为空还有两种删除和存在两种情况，需要满足位置的状态为存在时才可以//错误的：if (_table[hashi]._kv.first == key)//不为空还有两种删除和存在两种情况，需要满足位置的状态为存在时才可以{return &_table[hashi];//返回该位置的地址}++hashi;hashi %= _table.size();//取模的方式防止hashi越界}return nullptr;//找不到就返回空}bool Erase(const K& key){HashDate<K, V>* ret = Find(key);if (ret == nullptr){return false;}else{ret->_state = DELETE;//删除时只是将该位置的标识符置为了DELETE该位置上还存放着一个键，只不过该键可以被随时替换--_n;return true;}}private:vector<HashDate<K, V>> _table;//哈希表的大小和底层数组的容量都是通过 _table来管理的，正常情况下哈希表的大小_table.size和底层数组的容量是要分开的size_t _n;//哈希表中的有效数据个数};void TeshHT1(){int a[] = { 10001,11,55,24,19,12,31 };HashTable<int, int>  ht;//使用缺省的强转方式for (auto e : a){ht.Insert(make_pair(e, e));}cout << ht.Find(55) << endl;cout << ht.Find(31) << endl;ht.Erase(55);cout << ht.Find(55) << endl;cout << ht.Find(31) << endl;}void TeshHT2(){使用StringHashFunc//HashTable<string, int, StringHashFunc> ht;//ht.Insert(make_pair("sort", 1));//ht.Insert(make_pair("left", 1));//ht.Insert(make_pair("insert", 1));//查看是否可以用仿函数StringHashFunc将string转换为整型（与上面的内容无关）StringHashFunc()实例化一个匿名的仿函数类对象，然后("bacd")向该仿函数传参//cout << StringHashFunc()("bacd") << endl;//cout << StringHashFunc()("abcd") << endl;//cout << StringHashFunc()("aadd") << endl;//使用特化版本HashTable<string, int> ht;ht.Insert(make_pair("sort", 1));ht.Insert(make_pair("left", 1));ht.Insert(make_pair("insert", 1));//查看是否可以用仿函数的特化版本HashFunc<string>将string转换为整型cout << HashFunc<string>()("bacd") << endl;cout << HashFunc<string>()("abcd") << endl;cout << HashFunc<string>()("aadd") << endl;}}namespace hash_bucket
{template<class K, class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}};//template<class T>//struct HashNode//{//	T _data;//	HashNode<T>* _next;//	HashNode(const T& data)//		:_data(data)//		, _next(nullptr)//	{}//};template<class K,class V, class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:HashTable(){_table.resize(10, nullptr);//初始化时，数组中有十个位置，每个位置都存放的是空指针_n = 0;}//哈希表的底层容器vector函数结束后自动析构，但是vector中各个位置存放的都是自定义类型Node，自定义类型的析构时会调用它们的析构函数，所以还要重新写一个析构函数~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;//删除一个位置上的一整条链表就将该位置存放的指针置空}}//采用头插的方式bool Insert(const pair<K, V>& kv){//防止冗余if (Find(kv.first))return false;Hash hs;//如果还是重新建立映射关系，如果结点个数过多，在新表创建结点和移动后删除旧表的结点需要很多的资源//因为是队列是一个个挂在数组上的，所以当存放的有效元素个数 == 数组大小时才需要扩容//if (_n == _table.size())//{//	//新建一个哈希表//	HashTable<K, V> newHT;//	//确定新哈希表的大小//	newHT._table.resize(_table.size() * 2);//	//将旧表中的键重新映射到新表中//	for (size_t i = 0; i < _table.size(); i++)//每一次的for循环都是将某一个数组下标中的结点都链接到新表中//	{//		Node* cur = _table[i];//		while (cur)//		{//			newHT.Insert(_table[i]._kv);//直接复用Insert操作//			cur = cur->_next;//		}//	}//	_table.swap(newHT._table);//使用交换新旧表名中代表的地址信息//}//应该在确认了映射关系后，直接将旧表中的所有结点移动到新表中，这样移动后旧表中只用析构一个vector，且不用创建新的结点if (_n == _table.size()){vector<Node*> newTable(_table.size() * 2, nullptr);//设定新表大小及初始化各个位置for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];//cur指向旧表的下标为i位置的结点（该结点是一条链表的头结点）//遍历一条链表while (cur){Node* next = cur->_next;//next存放cur的下一个结点的位置//确定将旧表cur指向的结点要头插新表的哪个位置size_t hashi = hs(cur->_kv.first) % newTable.size();cur->_next = newTable[hashi];//头插（忘了回去看外面的注释，这点就是有点会让人发懵）newTable[hashi] = cur;cur = next;//cur指向自己的下一个结点}_table[i] = nullptr;//置空}/*cout <<"交换前旧表的地址为:" <<  & _table << endl;cout <<"交换前新表的地址为:" <<  &newTable << endl;*/_table.swap(newTable);//交换/*	cout << "交换后旧表的地址为:" << &_table << endl;cout << "交换后新表的地址为:" << &newTable << endl;*/}size_t hashi = hs(kv.first) % _table.size();Node* newnode = new Node(kv);//匿名结点对象//头插（数组中某个位置没有结点插入时_table[hashi] == nullptr）newnode->_next = _table[hashi];//_新结点的next结点指向当前链表的头指针指向的结点_table[hashi] = newnode;//令链表头指针指向新结点++_n;return true;//哈希桶的头插类似于://Node* head = nullptr; // 初始化一个空的链表，现在数组中每个位置都是一个空指针//void insertAtHead(int value) {//	Node* newNode = new Node(value); // 创建一个新节点//	newNode->next = head; // 将新节点的后继节点指向当前的头节点//	head = newNode; // 更新头节点指针，使其指向新节点//}}//链表的遍历Node* Find(const K& key){Hash hs;size_t hashi = hs(key) % _table.size();Node* cur = _table[hashi];//直接去映射位置上查找while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){Hash hs;size_t hashi = hs(key) % _table.size();Node* prev = nullptr;Node* cur = _table[hashi];//直接去映射位置上查找while (cur){if (cur->_kv.first == key){delete cur;}else{prev = cur->_next;cur = prev;}cur = cur->_next;}return nullptr;}private:vector<Node*> _table;//数组中的每个位置存放的都是结点的指针size_t _n;};void HashTest1(){int a[] = { 10001,11,55,24,19,12,31,4,34,44 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}//ht.Insert(make_pair(32, 32));//ht.Insert(make_pair(32, 32));}void HashTest2(){HashTable<string, int> ht;ht.Insert(make_pair("sort", 1));ht.Insert(make_pair("left", 1));ht.Insert(make_pair("insert", 1));}
}

~over~

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/332731.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【数据结构】排序算法大全（快速、堆、归并、插入、折半、希尔、冒泡、计数、基数）各算法比较、解析＋完整代码

【数据结构】排序算法大全（快速、堆、归并、插入、折半、希尔、冒泡、计数、基数）各算法比较、解析＋完整代码

文章目录 八、排序1.插入排序1.1 直接插入排序1.2 折半插入排序1.3 希尔排序 2.交换排序2.1 冒泡排序2.2 快速排序 3.选择排序3.1 简单选择排序3.2 堆3.2.1 堆排序3.2.2 堆插入删除*完善代码 堆 4.归并、基数、计数排序4.1 归并排序4.2 基数排序4.3 计数排序 5.内部排序算法的比…
阅读更多...
基于遗传优化的Sugeno型模糊控制器设计matlab仿真

基于遗传优化的Sugeno型模糊控制器设计matlab仿真

目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 5.完整工程文件 1.课题概述 基于遗传优化的Sugeno型模糊控制器设计matlab仿真,通过遗传优化算法优化模糊控制器的隶属函数参数&#xff0c;从而获得较优的控制效果。 2.系统仿真结果 3.核心程序与模型 …
阅读更多...
如何将前端项目打包并部署到不同服务器环境

如何将前端项目打包并部署到不同服务器环境

学习源码可以看我的个人前端学习笔记 (github.com):qdxzw/frontlearningNotes 觉得有帮助的同学&#xff0c;可以点心心支持一下哈&#xff08;笔记是根据b站尚硅谷的前端讲师【张天禹老师】整理的&#xff0c;用于自己复盘&#xff0c;有需要学习的可以去b站学习原版视频&…
阅读更多...
新书推荐：7.3 for语句

新书推荐：7.3 for语句

本节必须掌握的知识点&#xff1a; 示例二十四 代码分析 汇编解析 7.3.1 示例二十四 ■for语句语法形式&#xff1a; for(表达式1;表达式2;表达式3) { 语句块; } ●语法解析&#xff1a; 第一步&#xff1a;执行表达式1&#xff0c;表达式1初始化循环变量&#xff1b; …
阅读更多...
基于PHP的物业管理的设计与实现

基于PHP的物业管理的设计与实现

第1章 绪论... 1 1.1 研究背景与意义... 1 1.2 国内外发展现状... 2 第2章 关键技术介绍... 3 2.1 PHP语言... 3 2.2 MySQL数据库... 3 2.3 Zend框架... 4 2.4 B/S架构... 4 第3章 系统需求分析... 5 3.1 可行性分析... 5 3.1.1 技术可行性分析... 5 3.1.2 经济可行…
阅读更多...
IDEA 2024.1安装与破解

IDEA 2024.1安装与破解

一、下载 官网地址&#xff1a;https://www.jetbrains.com/idea/download/other.html 二、安装 傻瓜式安装即可 三、破解 3.1 破解程序 网站&#xff1a;https://3.jetbra.in/ 3.2 获取激活码 点击*号部分即可复制成功
阅读更多...
IOC控制反转

IOC控制反转

IOC IOC&#xff0c;全称为Inversion of Control(控制反转)&#xff0c;是一种设计原则&#xff0c;它反转了传统编程中的控制流程。在传统的编程模式中&#xff0c;组件之间的依赖关系是由组件自身在内部创建和维护的。而在控制反转模式中&#xff0c;这种依赖关系由外部容器(…
阅读更多...
【Docker实战】进入四大数据库的命令行模式

【Docker实战】进入四大数据库的命令行模式

上一篇我们讲了docker exec命令&#xff0c;这一次我们使用docker exec命令来进入四大数据库的命令行模式。 我们进行游戏开发或软件开发是离不开四大数据库的&#xff0c;这四大数据库分别是关系型数据库mysql、postgres&#xff0c;nosql数据库redis、mongodb。将它们容器化…
阅读更多...
云上聚智——移动云云服务器进行后端的搭建及部署

云上聚智——移动云云服务器进行后端的搭建及部署

什么是移动云 移动云是指将移动设备和云计算技术相结合&#xff0c;为移动应用提供强大的计算和存储能力的服务模式。传统的移动应用通常在本地设备上进行计算和存储&#xff0c;而移动云将这些任务转移到云端进行处理。通过移动云&#xff0c;移动设备可以利用云端的高性能计算…
阅读更多...
【C++】——入门基础知识超详解

【C++】——入门基础知识超详解

​​​​​​​ 目录 ​编辑 1.C关键字 2. 命名空间 2.1 命名空间定义 2.2 命名空间使用 命名空间的使用有三种方式&#xff1a; 注意事项 3. C输入&输出 示例 1&#xff1a;基本输入输出 示例 2&#xff1a;读取多个值 示例 3&#xff1a;处理字符串输入 示例…
阅读更多...
神经网络不确定性综述(Part II)——Uncertainty estimation_Single deterministic methods

神经网络不确定性综述(Part II)——Uncertainty estimation_Single deterministic methods

相关链接&#xff1a; 神经网络不确定性综述(Part I)——A survey of uncertainty in deep neural networks-CSDN博客 神经网络不确定性综述(Part II)——Uncertainty estimation_Single deterministic methods-CSDN博客 神经网络不确定性综述(Part III)——Uncertainty est…
阅读更多...
Docker-Android安卓模拟器本地部署并实现远程开发测试

Docker-Android安卓模拟器本地部署并实现远程开发测试

文章目录 1. 虚拟化环境检查2. Android 模拟器部署3. Ubuntu安装Cpolar4. 配置公网地址5. 远程访问小结 6. 固定Cpolar公网地址7. 固定地址访问 本文主要介绍如何在Ubuntu系统使用Docker部署docker-android安卓模拟器&#xff0c;并结合cpolar内网穿透工具实现公网远程访问本地…
阅读更多...
用常识滚雪球：拼多多的内生价值，九年的变与不变

用常识滚雪球：拼多多的内生价值，九年的变与不变

2024年5月22日&#xff0c;拼多多公布了今年一季度财报&#xff0c;该季度拼多多集团营收868.1亿元&#xff0c;同比增长131%&#xff0c;利润306.0亿&#xff0c;同比增长了202%&#xff0c;数据亮眼。 市场对拼多多经历了“看不见”、“看不懂”、“跟不上”三个阶段。拼多多…
阅读更多...
STM32无源蜂鸣器播放音乐

STM32无源蜂鸣器播放音乐

开发板&#xff1a;野火霸天虎V2 单片机&#xff1a;STM32F407ZGT6 开发软件&#xff1a;MDKSTM32CubeMX 文章目录 前言一、找一篇音乐的简谱二、确定音调三、确定节拍四、使用STM32CubeMX生成初始化代码五、代码分析 前言 本实验使用的是低电平触发的无源蜂鸣器 无源蜂鸣器是…
阅读更多...
【数据库】通过一个实例来认识数据流图DFD

【数据库】通过一个实例来认识数据流图DFD

导读&#xff1a;通过一个实例&#xff08;数据中台&#xff09;说明数据流图DFD的作用、介绍了常见的数据流图元素及其标准符号以及如何画数据流图。数据流图主要被分析师、系统设计师、流程优化专家、系统管理员以及与系统开发和维护相关的人员查看和使用。对于刚考完2024年5…
阅读更多...
设计模式 18 迭代器模式 Iterator Pattern

设计模式 18 迭代器模式 Iterator Pattern

设计模式 18 迭代器模式 Iterator Pattern 1.定义 迭代器模式 (Iterator Pattern) 是一种行为型设计模式&#xff0c;它提供了一种访问集合元素的标准方法&#xff0c;而无需暴露集合的内部表示。 提供一种方法顺序访问一个聚合对象中的各个元素&#xff0c;而又不需要暴露该…
阅读更多...
B树与B+树区别

B树与B+树区别

B树和B树是常见的数据库索引结构&#xff0c;都具有相较于二叉树层级较少&#xff0c;查找效率高的特点&#xff0c;它们之间有以下几个主要区别&#xff1a; 1.节点存储数据的方式不同 B树的叶子结点和非叶子节点都会存储数据&#xff0c;指针和数据共同保存在同一节点中B树…
阅读更多...
vue 引入 emoji 表情包

vue 引入 emoji 表情包

vue 引入 emoji 表情包 一、安装二、组件内使用 一、安装 npm install --save emoji-mart-vue二、组件内使用 import { Picker } from "emoji-mart-vue"; //引入组件<picker :include"[people,Smileys]" :showSearch"false" :showPreview&q…
阅读更多...
YAML详情

YAML详情

一、kubernetes支持对象 Kubernetes支持YAML和JSON格式管理资源对象 JSON格式&#xff1a;主要用于api接口之间消息的传递YAML格式&#xff1a;用于配置和管理&#xff0c;YAML是一种简洁的非标记性语言&#xff0c;内容格式人性化&#xff0c;较易读 二、YAML语法格式注意点 …
阅读更多...
微信小程序开发 tabbar组件常见问题

微信小程序开发 tabbar组件常见问题

一、 tabbar不显示问题 问题 刚开始我在app.json中配置了下面的代码&#xff0c;但tabbar并没有显示。代码如下&#xff1a; "tabBar": {"custom": true,"color": "#7A7E83","selectedColor": "#3cc51f","…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023