哈希相關的模擬實現

哈希表的模擬實現
- 閉散列除留取余法
- - 查找、插入和刪除
  - 閉散列參考程序
- 開散列除留取余法（數組+鏈表）
- - 迭代器
  - 查找和刪除
  - 插入
  - 開散列參考程序
unordered_map和unordered_set的模擬實現
- unordered_map
- unordered_set

建議先看哈希的概念及其應用-CSDN博客

哈希表的模擬實現

學習c++，最大的樂趣個人認為是搓天搓地搓空氣，包括底層的操作系統也是由和c++很接近的c語言和匯編語言等搓出來的（不排除后期可能有別的）。

閉散列除留取余法

這里選用開放定址法和閉散列的線性探測。但需要用枚舉或其他變量來表示狀態標識，因為線性探測在原來的位置滿了的時候會向后探測找空位，需要根據狀態來進行判斷空位是否真的是否為空。

根據紅黑樹的模擬實現的經驗，這里將通過模板參數來推演 Key 模型和 Key-Value 模型。

template<class Key,class Type,
class KeyOfType = mapKeyOfType<Key, Type>,
class Hash = HashFunc<Key> >
class HashTable {
private:vector<HashData<Type> >tables;size_t size;KeyOfType kot;Hash hashfunc;typedef HashData<Type> HashData;
};

其中的模板參數：

Key：查找哈希地址的鍵的類型。

Type：存儲的數據的類型。

KeyOfType：從Type類型數據中獲得Key型鍵值的仿函數。

Hash：通過Key型鍵值查找哈希地址的哈希函數。

查找、插入和刪除

查找

查找時根據Key型鍵值來查找。獲取哈希地址后，要查找的數據可能通過開放尋址法放到其他空位，所以需要從獲取的哈希地址向后查找。

插入

首先查找要插入的數據是否存在，不存在就不插入。

然后檢測負載因子。若負載因子大于 0.7 （推薦設置為0.7），則擴容。擴容時推薦創建新表，將舊表的數據重新插入新表，再刪除舊表。

最后就是通過哈希函數找到哈希地址，從哈希地址開始通過線性探測尋找空位，找到后進行插入。

刪除

首先查找要刪除的數據是否存在，不存在直接返回。

找到要刪除的數據后，將狀態設置為EMPTY即可。

閉散列參考程序

因為閉散列造成數據堆積的情況相對嚴重，因此只適合數據量小的情況，閉散列也不是重點，這里給 Key 模型實現參考用于復習即可。

#pragma once
#include<string>
#include<vector>
#include<algorithm>
#include<iostream>
using std::string;
using std::vector;
using std::lower_bound;
using std::cout;
using std::pair;
using std::make_pair;//開放尋址法 + 除留取余法 的哈希表
namespace open_adress {enum State {EMPTY,EXIST,DELETE};template<class Key, class Type>struct mapKeyOfType {const Key& operator()(const Type& aim) {return aim.first;}};template<class Key>struct HashFunc {size_t operator()(const Key& aim) {return size_t(aim);}};template<>struct HashFunc<string> {size_t operator()(const string& aim) {size_t val = 0;for (auto& x : aim)val = val * 131 + x;return val;}};template<class Type>struct HashData {Type data;State state;HashData(const Type& data = Type(), const State& state = EMPTY):data(data), state(state) {}HashData(const HashData& aim):data(aim.data), state(aim.state) {}};inline unsigned long __stl_next_prime(unsigned long n) {// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] = {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}template<class Key,class Type,class KeyOfType = mapKeyOfType<Key, Type>,class Hash = HashFunc<Key> >class HashTable {private:vector<HashData<Type> >tables;size_t size;KeyOfType kot;Hash hashfunc;typedef HashData<Type> HashData;public:HashTable(const size_t& capacity = __stl_next_prime(0)) {tables.resize(capacity);size = 0;}bool insert(const Type& data) {if (find(kot(data)))return false;// 負載因子0.7就擴容if (size * 10 / tables.size() >= 7) {HashTable<Key, Type, KeyOfType>newht(__stl_next_prime(tables.size() + 1));for (auto& x : tables)if (x.state == EXIST)newht.insert(x.data);tables.swap(newht.tables);}size_t hashi = hashfunc(kot(data)) % tables.size();while (tables[hashi].state == EXIST) {hashi++;hashi %= tables.size();}tables[hashi].data = data;tables[hashi].state = EXIST;++size;return true;}HashData* find(const Key& aim) {size_t hashi = hashfunc(aim) % tables.size();while (tables[hashi].state != EMPTY) {if (kot(tables[hashi].data) == aim)return &tables[hashi];hashi = (hashi + 1) % tables.size();}return nullptr;}bool erase(const Key& aim) {HashData* ret = find(aim);if (ret) {ret->state = DELETE;return true;}return false;}public:void print() {for (auto& x : tables)if (x.state == EXIST)cout << x.data << ',';cout << "\n";}void mapprint() {for (auto& x : tables)if (x.state == EXIST)cout << "[" << x.data.first << ':' << x.data.second << "] ";cout << "\n";}};//測試用的函數，一起打包在了命名空間中template<class Key, class Type>struct setKeyOfData {const Key& operator()(const Type& aim) {return aim;}};void fset() {srand(size_t(time(0)));HashTable<int, int, setKeyOfData<int, int> >ht;vector<int>a = {94,98,2,2,97,5,15,18,19,20,22,27,27,30,33,34,38,38,42,46,48,60,61,66,70,71,73,73,77,85,85,87,88,90,91,91,93,94,95,95 };for (auto& x : a)ht.insert(x);ht.print();cout << "\n";ht.erase(61);ht.print();cout << "\n";ht.insert(61);ht.print();}void fmap() {HashTable<string, pair<string, string> >ht;ht.insert(make_pair("insert", "插入"));ht.insert(make_pair("erase", "刪除"));ht.insert(make_pair("hash", "哈希"));ht.mapprint();}
}

開散列除留取余法（數組+鏈表）

開散列的哈希表實際上是一個支持下標索引的數組，每個元素存儲一個或一組容器。當發生哈希沖突時，將同一哈希函數得到的哈希地址相同的數據放在同一容器中。這個容器稱哈希桶。

哈系統可以是鏈表，也可以是紅黑樹，還可以是鏈表和紅黑樹的組合，反正就是哪個數據的查詢快就用哪個。

這里的開散列哈希表只用鏈表實現，這樣的哈希表相對容易實現。但當沖突的數據越來越多時，鏈表會變得很長，遍歷的效率會降低。因此不作為實際應用時的參考。

參考原型：

inline unsigned long __stl_next_prime(unsigned long n) {// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] = {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}template<class Key, class Type,class KeyOfType, class Hash = HashFunc<Key> >class HashTable {
private:vector<list<Type>>tables;size_t size;KeyOfType kot;Hash hashfunc;
public:HashTable(size_t capacity = __stl_next_prime(0)) {tables.resize(capacity);size = 0;}HashTable(const HashTable<Key, Type, KeyOfType, Hash>& aim):tables(aim.tables), size(aim.size), kot(aim.kot), hashfunc(aim.hashfunc){}};

__stl_next_prime函數是從c++98的stl_hashtable中獲得。因為庫中是使用素數作為哈希表的容量實現，所以這里選擇借鑒。

tables：哈希表本體，vector數組代替。

size：統計元素個數。

kot：用于從Type類型中獲取鍵值。

hashfunc：用于將Key型鍵值轉化為哈希地址。

迭代器

因為決定了使用list作為哈希桶的容器，所以迭代器最好使用list的迭代器。然后迭代器需要訪問哈希表以及指定位置的哈希桶。因此迭代器需要包含3個成員：list迭代器、哈希表和哈希桶。

因為哈希表直接拷貝的的話開銷可能很大，所以迭代器內包含哈希表的指針，通過指針訪問哈希表即可。

在實現過程中我遇到或一個問題：參考c++STL-list的模擬實現-CSDN博客，我將迭代器也設置成常量迭代器和非常量迭代器用同一個迭代器模板類推導得到，但遇到很多常屬性迭代器（特別是list的迭代器）和非常屬性的迭代器之間互相賦值等越權的情況。

針對這種情況，需要將迭代器類型和哈希表指針類型也作為模板參數，也可以使用條件編譯選擇類型（需要編譯器支持c++11，且操作繁瑣，不如給模板參數方便）。

因此迭代器原型參考：

template<class Key, class Type, class KeyOfType,class Ref, class Ptr, class Hash,class listiterator,class vectorptr>struct HashIterator {listiterator it;//list的迭代器vectorptr pt;//哈希表的指針size_t pb;//哈希桶typedef HashIterator<Key, Type, KeyOfType,Ref, Ptr, Hash,listiterator, vectorptr> self;HashIterator(listiterator it, vectorptr pt,size_t pb):it(it), pt(pt), pb(pb) {}HashIterator(const self& aim):it(aim.it), pt(aim.pt), pb(aim.pb) {}
};

由此也就衍生出了一個經驗（個人認為）：用其他容器的迭代器來實現本容器的迭代器，可以上傳迭代器和容器的數據類型作為模板參數。

之后若迭代器不帶常屬性，則在容器中這樣定義：

typedef HashIterator<Key, Type, KeyOfType, 
Type&, Type*, Hash,
typename list<Type>::iterator,
vector<list<Type>>*>iterator;

typename是讓編譯器將迭代器識別為類型。

若迭代器帶常屬性：

typedef HashIterator<Key, Type, KeyOfType,
const Type&, const Type*, Hash,
typename list<Type>::const_iterator, 
const vector<list<Type>>*>const_iterator;

回憶迭代器要求的幾個功能，根據哈希表來實現：

支持對迭代器解引用操作。在這里的實現中直接返回*it即可。
支持對迭代器的->操作。在這里的實現中直接返回&(*it)即可，即對迭代器解引用獲得數據后，再取地址返回。
支持++。先++it，若it為當前哈希桶的尾迭代器，則查找下一個非空哈希桶，找不到再重置為end()迭代器。
支持==。判斷哈希桶是否為同一個，以及迭代器it是否相同即可。

其他的根據需要自行補充。

最后：若迭代器無法訪問哈希表，則哈希表類可能需要將迭代器設置為友元以及前置聲明。聲明參考c語言的聲明，可以不實現，而是放一個模板參數和不帶類體的類聲明語句。

查找和刪除

通過哈希函數的到要查找的目標（aim）的哈希地址，然后遍歷哪個位置的哈希桶即可。找不到返回尾迭代器。

刪除需要先找到目標是否存在，不存在的話可以報錯，也可以返回尾迭代器；存在的話通過鏈表的erase方法刪除迭代器（可能要使用標準庫的std::find工具，需展開algorithm頭文件）。

成功刪除迭代器后，還需檢查當前哈希桶內是否還有元素，沒有元素的話需要向后查找第1個非空哈希桶，將非空哈希桶的首元素迭代器返回。

否則返回尾迭代器表示刪除失敗。

插入

首先查找要插入的元素是否在哈希表中。在的話就返回迭代器和false組成的鍵值對。這樣做是因為容器unordered_map需要借助insert方法來實現operator[]的操作。

然后檢查負載因子，為1時擴容。開散列不需要和閉散列一樣做的太過嚴格。

最后就是老流程：通過哈希函數獲取哈希地址，將數據插入指定地址的鏈表中。

開散列參考程序

這里只實現了迭代器、插入、查找和刪除的基本功能。其他的函數是為了哈希表能做unordered_map和unordered_set順手實現的。

#pragma once
#include<string>
#include<vector>
#include<algorithm>
#include<iostream>
#include<list>
#include<set>
#include<cassert>
using std::string;
using std::vector;
using std::lower_bound;
using std::cout;
using std::pair;
using std::make_pair;
using std::list;
using std::set;template<class Key>
struct HashFunc {size_t operator()(const Key& aim) {return size_t(aim);}
};template<>
struct HashFunc<string> {size_t operator()(const string& aim) {size_t val = 0;for (auto& x : aim)val = val * 131 + x;return val;}
};inline unsigned long __stl_next_prime(unsigned long n) {// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] = {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}//迭代器實現需要將其他容器的迭代器對象作為成員
template<class Key, class Type, class KeyOfType,class Ref, class Ptr, class Hash,class listiterator, class vectorptr>struct HashIterator {listiterator it;//list的迭代器vectorptr pt;//哈希表的指針size_t pb;//哈希桶typedef HashIterator<Key, Type, KeyOfType, Ref, Ptr, Hash,listiterator, vectorptr> self;HashIterator(listiterator it, vectorptr pt,size_t pb):it(it), pt(pt), pb(pb) {}HashIterator(const self& aim):it(aim.it), pt(aim.pt), pb(aim.pb) {}Ref operator*() {return *it;}Ptr operator->() {return &(*it);}self& operator++() {++it;if (it == (*pt)[pb].end()) {do++pb;while (pb < (*pt).size() && (*pt)[pb].empty());if (pb < (*pt).size()) {it = (*pt)[pb].begin();}else {--pb;it = (*pt)[pb].end();}}return *this;}self operator++(int) {self tmp(*this);++(*this);return tmp;}self& operator--() {//若最后一個哈希桶為空鏈表，則//鏈表的begin和end迭代器相等if (it == (*pt)[pb].begin()) {auto tmp = pb;//找到第1個非空的迭代器do--pb;while (pb > 0 && (*pt)[pb].empty());if ((*pt)[pb].empty()) {pb = tmp;return *this;}it = --(*pt)[pb].end();}else--it;return *this;}self operator--(int) {self tmp(*this);--(*this);return tmp;}bool operator==(const self& aim)const {return pb == aim.pb && (it == aim.it);}bool operator!=(const self& aim)const {return !(*this == aim);}};template<class Key, class Type,class KeyOfType, class Hash = HashFunc<Key> >class HashTable {private:vector<list<Type>>tables;size_t _size;KeyOfType kot;Hash hashfunc;public:HashTable(size_t capacity = __stl_next_prime(0)) {tables.resize(capacity);_size = 0;}HashTable(const HashTable<Key, Type, KeyOfType, Hash>& aim):tables(aim.tables), _size(aim._size), kot(aim.kot), hashfunc(aim.hashfunc) {}//迭代器模板類的友元聲明template<class Key, class Type, class KeyOfType,class Ref, class Ptr, class Hash,class listiterator,class vectorptr>friend struct HashIterator;//迭代器typedef HashIterator<Key, Type, KeyOfType,Type&, Type*, Hash,typename list<Type>::iterator,vector<list<Type>>*>iterator;typedef HashIterator<Key, Type, KeyOfType,const Type&, const Type*, Hash,typename list<Type>::const_iterator,const vector<list<Type>>*> const_iterator;iterator begin() {for (size_t i = 0; i < tables.size(); i++)if (!tables[i].empty())return iterator(tables[i].begin(),(&tables), i);return end();}iterator end() {return iterator(tables[tables.size() - 1].end(),(&tables),tables.size() - 1);}const_iterator begin() const {for (size_t i = 0; i < tables.size(); i++)if (!tables[i].empty())return const_iterator(tables[i].cbegin(),const_cast<const vector<list<Type>>*>(&tables),i);return end();}const_iterator end() const {return const_iterator(tables[tables.size() - 1].cend(),const_cast<const vector<list<Type>>*>(&tables),tables.size() - 1);}//插入pair<iterator, bool> insert(const Type& aim) {auto it = find(kot(aim));if (it != end())return make_pair(it, false);//負載因子等于1時擴容if (_size == tables.size()) {//生成新表vector<list<Type>>nt(__stl_next_prime(_size + 1));for (auto& tb : tables) {for (auto& lt : tb) {size_t hashi = hashfunc(kot(lt)) % nt.size();nt[hashi].push_front(lt);}}tables.swap(nt);}size_t hashi = hashfunc(kot(aim)) % tables.size();tables[hashi].push_front(aim);++_size;return make_pair(iterator(tables[hashi].begin(), &tables, hashi), true);}//查找iterator find(const Key& aim) {size_t hashi = hashfunc(aim) % tables.size();for (auto it = tables[hashi].begin(), ed = tables[hashi].end();it != ed; it++)if (kot(*it) == aim)return iterator(it, &tables, hashi);return end();}//刪除iterator erase(const Key& aim) {auto it = find(aim);if (it == end())return it;size_t hashi = hashfunc(aim) % tables.size();auto nit = tables[hashi].erase(std::find(tables[hashi].begin(), tables[hashi].end(), *it));--_size;if (nit != tables[hashi].end()) {return iterator(nit, &tables, hashi);}for (size_t i = hashi + 1; i < tables.size(); i++)if (!tables[i].empty())return iterator(tables[i].begin(), &tables, i);return end();}size_t size()const {return this->_size;}bool empty()const {return _size == 0;}void clear() {for (auto& x : tables)x.clear();_size = 0;}size_t count(const Key& val) {size_t cnt = 0, hashi = hashfunc(val) % tables.size();for (auto& x : tables[hashi])if (kot(x) == val)++cnt;return cnt;}
};//以下為測試用的函數
template<class Key, class Type>
struct setKeyOfType {const Key& operator()(const Type& aim) {return aim;}
};template<class Key, class Type>
struct mapKeyOfType {const Key& operator()(const Type& aim) {return aim.first;}
};//void f() {
//	std::vector<int>arr = { 1,3,4,5,6,7 };
//	auto it = arr.begin();
//	for (const auto ed = arr.end(); it != ed; ++it)
//		cout << *it << " ";
//}void testhash() {srand(size_t(time(0)));HashTable<int, int, setKeyOfType<int, int> >ht;vector<int>arr = { 1,2,55,92,2,3,5,6,7,8,34 };for (auto x : arr)ht.insert(x);//測試find和eraseauto it = ht.find(2);cout << *it << "\n";it = ht.erase(92);//cout << *it << endl;if (it == ht.end())cout << 92 << "\n";cout << "\n";//測試迭代器auto nit = (ht).begin();for (auto ned = ht.end(); nit != ned; nit++)cout << *nit << ' ';cout << "\n";for (const auto& x : ht)cout << x << ' ';cout << "\n";cout << "\n";//帶常屬性的迭代器實驗const HashTable<int, int, setKeyOfType<int, int> >ht2(ht);for (auto& x : ht2)cout << x << ' ';cout << "\n";auto ht2it = ht2.begin();for (auto ht2ed = ht2.end(); ht2it != ht2ed; ++ht2it)cout << *ht2it << ' ';cout << "\n";cout << "\n";//測試Key-Value模型的匹配度HashTable<int, pair<int, int>, mapKeyOfType<int, pair<int, int>> >ht3;ht3.insert(make_pair(1, 2));ht3.insert(make_pair(2, 2));ht3.insert(make_pair(3, 2));ht3.insert(make_pair(4, 2));for (auto& x : ht3)cout << "[" << x.first << ":" << x.second << "]" << " ";cout << "\n";cout << (*ht3.find(3)).second << "\n";ht3.erase(3);for (auto& x : ht3)cout << "[" << x.first << ":" << x.second << "]" << " ";cout << "\n";ht3.insert(make_pair(3, 2));ht3.insert(make_pair(56, 2));ht3.insert(make_pair(109, 2));auto mapit = --ht3.end();for (auto maped = ht3.begin(); (mapit) != maped; --mapit)cout << "[" << (*mapit).first << ":" << (*mapit).second << "]" << " ";cout << "\n";cout << "[" << (*mapit).first << ":" << (*mapit).second << "]" << "\n";--mapit;//這里設置了--begin()不起作用cout << "[" << mapit->first << ":" << mapit->second << "]" << "\n";
}

用紅黑樹和鏈表實現的哈希表，以后有機會會實現。

unordered_map和unordered_set的模擬實現

unordered_map和unordered_set完全可以將紅黑樹的map和set的模擬實現的原型搬過來，將底層容器更改為開散列哈希表，再修改一些細節即可。

unordered_map

#pragma once
#include"hash_table.h"
#include<functional>
using std::less;namespace mystd {template<class Key, class Type, class Compare = less<Type> >class unordered_map {public:typedef pair<const Key, Type> val_type;public://獲取鍵值的仿函數struct mapKeyOfType {const Key& operator()(const val_type& key) const {return key.first;}};private:HashTable<Key, pair<const Key, Type>, mapKeyOfType> ht;public://構造函數unordered_map() {}unordered_map(const unordered_map& st):ht(st.ht) {}template<class InputIterator>unordered_map(InputIterator first, InputIterator last) {for (auto it = first; it != last; ++it)insert(*it);}//迭代器typedef typenameHashTable<Key, pair<const Key, Type>,mapKeyOfType>::iteratoriterator;typedef typenameHashTable<Key, pair<const Key, Type>,mapKeyOfType>::const_iteratorconst_iterator;iterator begin() {return ht.begin();}iterator end() {return ht.end();}const_iterator begin() const {return ht.begin();}const_iterator end() const {return ht.end();}//插入pair<iterator, bool> insert(const val_type& val) {return pair<iterator, bool>(ht.insert(val));}//[]訪問Type& operator[](const Key& key) {//照搬庫里的寫法return (*(insert(make_pair(key, Type())).first)).second;}//刪除bool erase(const Key& val) {size_t tmp = ht.size();auto it = ht.erase(val);if (tmp == ht.size() + 1)return true;return false;}//返回存儲的元素個數size_t size()const {return ht.size();}//判空bool empty() const {return ht.empty();}//清空void clear() {ht.clear();}//查找iterator find(const Key& val) {return ht.find(val);}//計數size_t count(const Key& val) {return ht.count(val);}};void test_map() {mystd::unordered_map<string, int>mp;if (mp.empty())cout << "mp.empty()" << "\n";mp.insert(make_pair("insert", 1));if (!mp.empty())cout << mp.size() << "\n";mp["insert"] = 2;mp["erase"] = 3;mp["hash"] = 4;cout << mp.find("erase")->second << "\n";for (auto& x : mp)cout << "[" << x.first << ":" << x.second << "] ";cout << "\n";mp.erase("erase");for(auto&x:mp)cout << "[" << x.first << ":" << x.second << "] ";cout << "\n";}
}

unordered_set

#pragma once
#include"hash_table.h"
#include<functional>
using std::less;namespace mystd {template<class Type, class Compare = less<Type> >class unordered_set {public:typedef Type Key;//獲取鍵值的仿函數struct setKeyOfType {const Type& operator()(const Type& key) const {return key;}};//構造函數unordered_set() {}unordered_set(const unordered_set<Type, Compare>& st):ht(st.ht) {}template<class InputIterator>unordered_set(InputIterator first, InputIterator last) {for (auto it = first; it != last; ++it)insert(*it);}//迭代器typedef typenameHashTable<const Key, Key,setKeyOfType>::iteratoriterator;typedef typenameHashTable<const Key, Key,setKeyOfType>::const_iteratorconst_iterator;iterator begin() {return ht.begin();}iterator end() {return ht.end();}const_iterator begin() const {return ht.begin();}const_iterator end() const {return ht.end();}//插入pair<iterator, bool> insert(const Type& val) {return pair<iterator, bool>(ht.insert(val));}//刪除bool erase(const Type& val) {size_t tmp = ht.size();auto it = ht.erase(val);if (tmp == ht.size() + 1)return true;return false;}//返回存儲的元素個數size_t size()const {return ht.size();}//判空bool empty() const {return ht.empty();}//清空void clear() {ht.clear();}//查找iterator find(const Type& val) {return ht.find(val);}//計數size_t count(const Key& val) {return ht.count(val);}private://底層哈希表//STL容器禁止上傳帶const的數據類型作為容器存儲的數據HashTable<const Key, Key, setKeyOfType> ht;};void fset() {mystd::unordered_set<int>st;if (st.empty())cout << "st.empty()" << "\n";st.insert(1);if (!st.empty())cout << st.size() << "\n";st.insert(2);st.insert(3);st.insert(4);cout << *st.find(3) << "\n";for (auto& x : st)cout << x << " ";cout << "\n";st.erase(3);for (auto& x : st)cout << x << " ";cout << "\n";}
}