文章目录

• 哈希表的概念
• 线性探测哈希表的实现
• • 哈希表的结构
  • 哈希表数据的结构
  • 插入
  • 查找
  • 删除
• 二次探测哈希表的实现
• • 哈希表的结构
  • 哈希表数据的结构
  • 插入
  • 查找
  • 删除
• 链式哈希表(哈希桶)的实现
• • 哈希表的结构
  • 哈希表数据的结构
  • 插入
  • 查找
  • 删除
• 整体的代码

哈希表的概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log2Nlog_2 Nlog2​N)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
这篇博客我们简单的介绍一下哈希表，重点是哈希表的实现，下次的博客会为大家详细的介绍一下哈希表。

线性探测哈希表的实现

哈希表的结构

哈希表数据的结构

插入

查找

删除

二次探测哈希表的实现

哈希表的结构

哈希表数据的结构

插入

查找

删除

链式哈希表(哈希桶)的实现

哈希表的结构

哈希表数据的结构

插入

查找

删除

整体的代码

#pragma once
#include 
template
struct Hash
{size_t operator()(const K& key){return key;}
};
template<>
struct Hash
{size_t operator()(const string& s){size_t value = 0;for (auto& ch : s){value += ch;}return value;}
};
namespace LinearDetectionHash
{enum status{EMPTY,//空EXIST,//存在DELETE//删除};templatestruct HashData{pair _kv;//要存的值status _status = EMPTY;//状态};template>class HashTable{public:HashTable(){}bool Erase(const K& key){HashData* ret = Find(key);if (ret){ret->_status = DELETE;_size--;return true;}else{return false;}}HashData* Find(const K& key){if (_tables.size() == 0){return nullptr;}HashFunc hf;size_t index = hf(key) % _tables.size();while (_tables[index]._status == EXIST){if (_tables[index]._kv.first == key && _tables[index]._status == EXIST){return &_tables[index];}index++;}return nullptr;}bool Insert(const pair& kv){HashData* ret = Find(kv.first);HashFunc hf;if (ret){return false;}if (_tables.size() == 0 || _size*10 / _tables.size() > 7){size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();HashTable newHT;newHT._tables.resize(newsize);for (int i = 0; i < _tables.size(); i++){if (_tables[i]._status == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}size_t index = hf(kv.first) % _tables.size();while (_tables[index]._status == EXIST){index++;index %= _tables.size();}_tables[index]._kv = kv;_tables[index]._status = EXIST;_size++;return true;}private:vector> _tables;size_t _size = 0;};void TestHashTable1(){HashTable kv;kv.Insert(make_pair(1, 1));kv.Insert(make_pair(2, 2));kv.Insert(make_pair(3, 3));kv.Insert(make_pair(4, 4));kv.Insert(make_pair(14, 14));kv.Insert(make_pair(24, 24));kv.Insert(make_pair(34, 34));kv.Insert(make_pair(11, 11));kv.Insert(make_pair(21, 21));kv.Insert(make_pair(31, 31));kv.Insert(make_pair(32, 32));/*cout << kv.Find(1) << endl;cout << kv.Find(3) << endl;cout << kv.Find(14) << endl;cout << kv.Find(32) << endl;cout << kv.Find(33) << endl;*/}void TestHashTable2(){HashTable kv;kv.Insert(make_pair("sort", "排序"));kv.Insert(make_pair("soda", "苏打水"));kv.Erase("sort");cout << kv.Find("sort") << endl;cout << kv.Find("test") << endl;}
}
namespace SecondaryDetectionHash
{enum status{EMPTY,EXIST,DELETE};templatestruct HashData{pair _kv;status _status = EMPTY;};template>class HashTable{public:HashTable(){}bool Erase(const K& key){HashData* ret = Find(key);if (ret){ret->_status = DELETE;_size--;return true;}else{return false;}}HashData* Find(const K& key){if (_tables.size() == 0){return nullptr;}HashFunc hf;size_t i = 0;size_t index = hf(key) % _tables.size();while (_tables[index]._status == EXIST){if (_tables[index]._kv.first == key && _tables[index]._status == EXIST){return &_tables[index];}i++;index += i*i;index %= _tables.size();}return nullptr;}bool Insert(const pair& kv){HashData* ret = Find(kv.first);HashFunc hf;if (ret){return false;}if (_tables.size() == 0 || _size * 10 / _tables.size() > 7){size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();HashTable newHT;newHT._tables.resize(newsize);for (int i = 0; i < _tables.size(); i++){if (_tables[i]._status == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}size_t i = 0;size_t index = hf(kv.first) % _tables.size();while (_tables[index]._status == EXIST){i++;index += i * i;index %= _tables.size();}_tables[index]._kv = kv;_tables[index]._status = EXIST;_size++;return true;}private:vector> _tables;size_t _size = 0;};void TestHashTable1(){HashTable kv;kv.Insert(make_pair(1, 1));kv.Insert(make_pair(2, 2));kv.Insert(make_pair(3, 3));kv.Insert(make_pair(4, 4));kv.Insert(make_pair(14, 14));kv.Insert(make_pair(24, 24));kv.Insert(make_pair(34, 34));kv.Insert(make_pair(11, 11));kv.Insert(make_pair(21, 21));kv.Insert(make_pair(31, 31));kv.Insert(make_pair(32, 32));cout << kv.Find(1) << endl;cout << kv.Find(3) << endl;cout << kv.Find(14) << endl;cout << kv.Find(32) << endl;cout << kv.Find(33) << endl;}void TestHashTable2(){HashTable kv;kv.Insert(make_pair("sort", "排序"));kv.Insert(make_pair("soda", "苏打水"));//kv.Erase("sort");cout << kv.Find("sort") << endl;cout << kv.Find("test") << endl;}
}
namespace LinkHash
{templatestruct HashNode{pair _kv;HashNode* next;HashNode(const pair& kv):_kv(kv),next(nullptr){}};template>class HashTable{typedef HashNode Node;public:bool Erase(const K& key){if (_size == 0){return false;}HashFunc hf;size_t index = hf(key) % _tables.size();Node* cur = _tables[index];Node* prev = nullptr;while (cur){if (cur->_kv.first == key){Node* next = cur->next;if(prev)prev->next = next;else_tables[index] = next;delete cur;cur = nullptr;_size--;return true;}else{prev = cur;cur = cur->next;}}return false;}Node* Find(const K& key){if (_size == 0){return nullptr;}HashFunc hf;size_t index = hf(key) % _tables.size();Node* cur = _tables[index];while (cur){if (cur->_kv.first == key){return cur;}else{cur = cur->next;}}return nullptr;}bool Insert(const pair& kv){Node* ret = Find(kv.first);if (ret){return false;}if (_tables.size() == 0 || _size*10 / _tables.size() == 10){size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();HashTable newHT;newHT._tables.resize(newsize);HashFunc hf;for (int i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->next;size_t index = hf(cur->_kv.first) % newHT._tables.size();if (newHT._tables[index]){Node* next = newHT._tables[index];newHT._tables[index] = cur;cur->next = next;}else{newHT._tables[index] = cur;newHT._tables[index]->next = nullptr;;}newHT._size++;cur = next;}_tables[i] = nullptr;	}_tables.swap(newHT._tables);}HashFunc hf;Node* cur = new Node(kv);size_t index = hf(kv.first) % _tables.size();if (_tables[index]){Node* next = _tables[index];_tables[index] = cur;cur->next = next;}else{_tables[index] = cur;}_size++;return true;}private:vector _tables;size_t _size = 0;};void TestHashTable1(){HashTable kv;kv.Insert(make_pair(1, 1));kv.Insert(make_pair(2, 2));kv.Insert(make_pair(3, 3));kv.Insert(make_pair(4, 4));kv.Insert(make_pair(14, 14));kv.Insert(make_pair(24, 24));kv.Insert(make_pair(34, 34));kv.Insert(make_pair(11, 11));kv.Insert(make_pair(21, 21));kv.Insert(make_pair(31, 31));kv.Insert(make_pair(32, 32));kv.Insert(make_pair(10, 10));cout << kv.Find(1) << endl;cout << kv.Find(100) << endl;}void TestHashTable2(){HashTable kv;kv.Insert(make_pair(1, 1));kv.Insert(make_pair(11, 11));kv.Insert(make_pair(2, 2));cout << kv.Erase(4) << endl;cout << kv.Erase(11) << endl;cout << kv.Erase(2) << endl;cout << kv.Erase(1) << endl;}
}