删除函数
bool Erase(const K& key) { HashData<K, V>* ret = Find(key); if (ret) { ret->_state = DELETE; --_size; return true; } else { return false; } }
Erase 方法的实现，用于删除指定键对应的数据项。以下是该方法的主要步骤和逻辑：
- 首先，调用
Find方法来查找指定键key对应的数据项。如果找到了匹配的数据项，Find方法会返回一个指向该数据项的指针，并将其存储在ret中。如果未找到匹配的数据项，Find方法返回nullptr。 - 接下来，检查
ret是否为非空指针。如果ret不为空，表示找到了匹配的数据项，可以执行删除操作。 - 在删除操作中，将匹配数据项的状态
_state设置为DELETE，表示该数据项已删除。 - 同时，减少哈希表中有效数据项数量
_size的计数，以反映删除操作。 - 最后，返回
true表示删除成功。 - 如果
ret为空（即未找到匹配的数据项），则返回false表示删除失败。
这个 Erase 方法实现了哈希表中数据项的逻辑删除，通过将状态标记为 DELETE 来表示删除状态，而不是实际地从哈希表中移除数据。这种方法允许在查找时跳过已删除的数据，同时保留了哈希表的完整性。
全部代码
#pragma once #include<iostream> using namespace std; enum State { EMPTY, EXIST, DELETE }; template<class K, class V> struct HashData { pair<K, V> _kv; State _state = EMPTY; }; template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<> struct HashFunc<string>//对字符型特化给定值乘以固定质数131降低冲突 { size_t operator()(const string& key) { size_t val = 0; for (auto ch : key) { val *= 131; val += ch; } return val; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; // 负载因子到了就扩容 if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7) // 扩容 { size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; HashTable<K, V, Hash> newHT; newHT._tables.resize(newSize); // 旧表的数据映射到新表 for (auto e : _tables) { if (e._state == EXIST) { newHT.Insert(e._kv); } } _tables.swap(newHT._tables); } Hash hash; size_t hashi = hash(kv.first) % _tables.size(); while (_tables[hashi]._state == EXIST) { hashi++; hashi %= _tables.size(); } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; ++_size; return true; } HashData<K, V>* Find(const K& key) { if (_tables.size() == 0) { return nullptr; } Hash hash; size_t start = hash(key) % _tables.size(); size_t hashi = start; while (_tables[hashi]._state != EMPTY) { if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key) { return &_tables[hashi]; } hashi++; hashi %= _tables.size(); if (hashi == start) { break; } } return nullptr; } bool Erase(const K& key) { HashData<K, V>* ret = Find(key); if (ret) { ret->_state = DELETE; --_size; return true; } else { return false; } } void Print() { for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]._state == EXIST) { printf("[%d:%d] ", i, _tables[i]._kv.first); } else { printf("[%d:*] ", i); } } cout << endl; } private: vector<HashData<K, V>> _tables; size_t _size = 0; // 存储多少个有效数据 };
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。
1.2 二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：H_i = (H_0 + i^2 )% m, 或者：H_i = (H_0 - i^2)% m。其中：i =1,2,3…， H_0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。
修改线性探测中的插入函数：
Hash hash; size_t start = hash(kv.first) % _tables.size(); size_t i = 0; size_t hashi = start; // 二次探测 while (_tables[hashi]._state == EXIST) { ++i; hashi = start + i*i; hashi %= _tables.size(); } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; ++_size;
代码的主要步骤和逻辑：
- 创建一个哈希函数对象
hash。 - 计算给定键
kv.first的哈希值，并使用取模运算% _tables.size()得到槽位索引start，表示开始查找的位置。 - 初始化一个整数
i，用于追踪尝试的次数，并初始化hashi为start，表示当前要查找的槽位。 - 进入循环，使用二次探测来查找可用的槽位。在每次迭代中，增加
i，然后计算新的哈希索引hashi，通过start + i*i计算。接着，使用取模运算% _tables.size()确保哈希索引不超出哈希表的大小。 - 检查当前槽位
_tables[hashi]的状态。如果状态为EXIST，表示该槽位已经被占用，继续下一个迭代以尝试下一个槽位。 - 如果找到一个空槽位
_tables[hashi]._state不为EXIST，表示该槽位可以存储数据。将键值对kv存储在该槽位，并将状态标记为EXIST，表示该槽位包含有效数据。 - 递增有效数据项数量
_size，表示成功插入数据。
通过使用二次探测，可以更均匀地分布数据项，并减少了线性探测时的聚集效应。
当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。因此，闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷
2. 开散列
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
开散列中每个桶中放的都是发生哈希冲突的元素
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) {} };
定义结构体 HashNode，用于表示哈希表中的节点。这个节点包含以下成员：
_kv：这是一个键值对（pair<K, V>），用于存储节点中的键值数据。_next：这是一个指向下一个节点的指针，用于构建链表结构，处理哈希冲突。如果发生哈希冲突，多个节点可能被映射到同一个哈希桶（槽位），这时链表的_next指针被用来连接具有相同哈希值的节点。
在链地址法中，每个哈希桶（槽位）维护一个链表，当多个键映射到同一个槽位时，它们会按顺序添加到链表中，通过 _next 指针连接。通过这种方式，可以在同一哈希桶中存储多个键值对，解决了哈希冲突的问题。当需要查找或删除键值对时，可以遍历链表来定位具体的节点。这种链地址法的实现使得哈希表可以有效地管理数据，并保持高效性能。
template<class K, class V> class HashTable { typedef HashNode<K, V> Node; private: vector<Node*> _tables; size_t _size = 0; // 存储有效数据个数 };
定义哈希表的模板类 HashTable，用于存储键值对数据。以下是该类的主要成员和属性：
typedef HashNode<K, V> Node;：这是一个类型别名声明，将HashNode<K, V>简化为Node，以提高代码可读性。private:：这是一个私有访问标识符，表示以下成员变量和方法是类的私有成员，外部不可直接访问。vector<Node*> _tables;：这是一个vector容器，用于存储哈希表的哈希桶（槽位）。每个元素是一个指向HashNode<K, V>类型的指针，即链表的头节点。这个容器存储了哈希表的所有数据。size_t _size = 0;：这是一个计数器，用于记录哈希表中有效数据的个数。在哈希表的插入、删除等操作中，会更新这个计数器来维护数据的准确数量。
HashTable 类的作用是实现一个哈希表数据结构，支持存储键值对数据，并提供插入、查找、删除等基本操作。该哈希表采用链地址法解决哈希冲突，使用一个 vector 来存储哈希桶，每个桶对应一个链表用于存储数据。此外，_size 用于跟踪有效数据的数量，帮助管理哈希表的负载因子和自动扩容等操作。
插入函数
和闭散列一样，插入时我们需要考虑扩容问题，那么桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容
bool Insert(const pair<K, V>& kv) { // 去重 if (Find(kv.first)) { return false; } // 负载因子到1就扩容 if (_size == _tables.size()) { size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; vector<Node*> newTables; newTables.resize(newSize, nullptr); // 旧表中节点移动映射新表 for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; size_t hashi = cur->_kv.first % newTables.size(); cur->_next = newTables[hashi]; newTables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newTables); } size_t hashi = kv.first % _tables.size(); // 头插 Node* newnode = new Node(kv); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_size; return true; }
- 首先，检查是否已经存在具有相同键的节点，即通过调用
Find(kv.first)来查找键kv.first是否已存在于哈希表中。如果已存在，就返回false，表示插入失败，因为不允许重复键。 - 接着，检查负载因子（load factor），负载因子是指已存储数据个数
_size与哈希桶个数_tables.size()的比值。如果负载因子达到1（表示每个哈希桶平均存储一个数据），则进行扩容操作。 - 如果需要扩容，首先计算新哈希表的大小
newSize，如果当前哈希表为空（即_tables.size()为0），则将新大小设置为10，否则将新大小设置为当前大小的两倍。然后，创建一个新的vector容器newTables，并将其大小设置为newSize，同时初始化所有元素为nullptr。 - 遍历当前哈希表
_tables中的每个槽位（每个槽位对应一个链表），将链表中的节点重新映射到新的哈希桶中。具体操作是遍历链表，将每个节点的键通过哈希函数计算新的槽位索引hashi，然后将节点插入到新的哈希桶中（采用头插法），同时更新节点的_next指针以构建链表。完成后，将旧的槽位设置为nullptr。 - 最后，使用
swap操作交换新旧哈希表，将新哈希表取代旧哈希表，以完成扩容操作。 - 如果不需要扩容（负载因子未达到1），则计算键的哈希值
hashi，确定要插入的槽位，然后采用头插法将新节点插入到对应槽位的链表中。增加有效数据个数_size并返回true，表示插入成功。
这段代码的核心思想是维护哈希表的负载因子，当负载因子过高时触发扩容操作，以保持哈希表的性能。同时，它通过链表处理哈希冲突，支持多个键映射到同一个哈希桶的情况。需要注意的是，对于已存在的键，不会进行插入操作，以保证键的唯一性。
查找函数
Node* Find(const K& key) { if (_tables.size() == 0) { return nullptr; } size_t hashi = key % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) { return cur; } cur = cur->_next; } return nullptr; }
- 首先，检查哈希表是否为空，即
_tables.size() == 0。如果哈希表为空，表示没有数据，直接返回nullptr，因为无法找到任何数据。 - 计算键的哈希值
hashi，通过对键key取模操作% _tables.size()得到一个槽位索引，确定要在哪个哈希桶中查找。 - 初始化一个指针
cur，将其指向选定的哈希桶_tables[hashi]中的头节点，即链表的起始位置。 - 进入循环，遍历链表中的节点。在每次迭代中，检查当前节点
cur是否为空。如果为空，表示已经遍历到链表末尾，仍然未找到匹配的键，此时返回nullptr表示未找到。 - 如果节点
cur不为空，继续检查当前节点的键值对中的键_kv.first是否等于目标键key。如果相等，表示找到了匹配的键值对，返回指向当前节点cur的指针，以便访问或修改该数据。 - 如果当前节点不匹配，将
cur指向下一个节点，即cur = cur->_next，以继续搜索链表中的下一个节点。 - 循环直到找到匹配的节点或遍历完整个链表。
删除函数
bool Erase(const K& key) { if (_tables.size() == 0) { return false; // 哈希表为空，无法删除 } size_t hashi = key % _tables.size(); Node* cur = _tables[hashi]; Node* prev = nullptr; // 用于记录当前节点的前一个节点 // 遍历链表 while (cur) { if (cur->_kv.first == key) { // 找到匹配的节点，进行删除操作 if (prev) { prev->_next = cur->_next; // 从链表中移除当前节点 } else { // 如果当前节点是链表的头节点，则更新哈希桶的头指针 _tables[hashi] = cur->_next; } delete cur; // 释放当前节点的内存 --_size; // 减少有效数据个数 return true; // 删除成功 } prev = cur; cur = cur->_next; // 移动到下一个节点 } return false; // 未找到匹配的键，删除失败 }
- 如果当前节点不是链表的头节点，将前一个节点
prev的_next指针指向当前节点的下一个节点，从而将当前节点从链表中移除。 - 如果当前节点是链表的头节点，直接更新哈希桶的头指针
_tables[hashi]为当前节点的下一个节点，以确保链表头的正确更新。 - 释放当前节点的内存，并减少有效数据个数
_size。 - 返回
true表示删除成功。 - 如果未找到匹配的键，最终返回
false表示删除失败。
析构函数
~HashTable() { for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; free(cur); cur = next; } _tables[i] = nullptr; } }
遍历哈希表的每个槽位，释放链表中的节点，然后将槽位设为 nullptr，确保释放了所有分配的内存。以下是代码的主要逻辑：
- 使用一个
for循环遍历_tables容器，其中_tables存储了哈希表的所有槽位。 - 在每次迭代中，获取当前槽位
_tables[i]对应的链表头节点Node* cur。 - 进入内部的
while循环，遍历链表中的每个节点。在每次迭代中，首先将下一个节点指针Node* next设置为当前节点的下一个节点。 - 使用
free函数释放当前节点cur占用的内存。注意，这里使用free函数而不是delete，因为cur对象的内存分配可能是通过malloc或类似的函数进行的，而不是new。 - 将当前节点
cur指向下一个节点next，以继续遍历链表。 - 循环直到链表中没有更多节点，即
cur变为nullptr。 - 在每次迭代结束后，将当前槽位
_tables[i]设置为nullptr，确保该槽位不再包含任何节点。
全部代码
#pragma once #include<iostream> using namespace std; 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 K, class V> class HashTable { typedef HashNode<K, V> Node; public: ~HashTable() { for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; free(cur); cur = next; } _tables[i] = nullptr; } } bool Insert(const pair<K, V>& kv) { // 去重 if (Find(kv.first)) { return false; } // 负载因子到1就扩容 if (_size == _tables.size()) { size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; vector<Node*> newTables; newTables.resize(newSize, nullptr); // 旧表中节点移动映射新表 for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; size_t hashi = cur->_kv.first % newTables.size(); cur->_next = newTables[hashi]; newTables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newTables); } size_t hashi = kv.first % _tables.size(); // 头插 Node* newnode = new Node(kv); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_size; return true; } Node* Find(const K& key) { if (_tables.size() == 0) { return nullptr; } size_t hashi = key % _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) { if (_tables.size() == 0) { return false; // 哈希表为空，无法删除 } size_t hashi = key % _tables.size(); Node* cur = _tables[hashi]; Node* prev = nullptr; // 用于记录当前节点的前一个节点 // 遍历链表 while (cur) { if (cur->_kv.first == key) { // 找到匹配的节点，进行删除操作 if (prev) { prev->_next = cur->_next; // 从链表中移除当前节点 } else { // 如果当前节点是链表的头节点，则更新哈希桶的头指针 _tables[hashi] = cur->_next; } delete cur; // 释放当前节点的内存 --_size; // 减少有效数据个数 return true; // 删除成功 } prev = cur; cur = cur->_next; // 移动到下一个节点 } return false; // 未找到匹配的键，删除失败 } private: vector<Node*> _tables; size_t _size = 0; // 存储有效数据个数 };
开散列和闭散列对比
链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <=0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间
