企业网站做优化,广告网站做动图怎么做,网站改版方案怎么写,东莞免费的制作网页哈希相关的模拟实现哈希表的模拟实现闭散列除留取余法查找、插入和删除闭散列参考程序开散列除留取余法#xff08;数组链表#xff09;迭代器查找和删除插入开散列参考程序unordered_map和unordered_set的模拟实现unordered_mapunordered_set建议先看
哈希的概念及其应用-CS…
哈希相关的模拟实现哈希表的模拟实现闭散列除留取余法查找、插入和删除闭散列参考程序开散列除留取余法数组链表迭代器查找和删除插入开散列参考程序unordered_map和unordered_set的模拟实现unordered_mapunordered_set建议先看
哈希的概念及其应用-CSDN博客哈希表的模拟实现 学习c最大的乐趣个人认为是搓天搓地搓空气包括底层的操作系统也是由和c很接近的c语言和汇编语言等搓出来的不排除后期可能有别的。 闭散列除留取余法
这里选用开放定址法和闭散列的线性探测。但需要用枚举或其他变量来表示状态标识因为线性探测在原来的位置满了的时候会向后探测找空位需要根据状态来进行判断空位是否真的是否为空。
根据红黑树的模拟实现的经验这里将通过模板参数来推演 Key 模型和 Key-Value 模型。
templateclass Key,class Type,
class KeyOfType mapKeyOfTypeKey, Type,
class Hash HashFuncKey
class HashTable {
private:vectorHashDataType tables;size_t size;KeyOfType kot;Hash hashfunc;typedef HashDataType HashData;
};其中的模板参数
Key查找哈希地址的键的类型。
Type存储的数据的类型。
KeyOfType从Type类型数据中获得Key型键值的仿函数。
Hash通过Key型键值查找哈希地址的哈希函数。
查找、插入和删除
查找
查找时根据Key型键值来查找。获取哈希地址后要查找的数据可能通过开放寻址法放到其他空位所以需要从获取的哈希地址向后查找。
插入
首先查找要插入的数据是否存在不存在就不插入。
然后检测负载因子。若负载因子大于 0.7 推荐设置为0.7则扩容。扩容时推荐创建新表将旧表的数据重新插入新表再删除旧表。
最后就是通过哈希函数找到哈希地址从哈希地址开始通过线性探测寻找空位找到后进行插入。
删除
首先查找要删除的数据是否存在不存在直接返回。
找到要删除的数据后将状态设置为EMPTY即可。
闭散列参考程序
因为闭散列造成数据堆积的情况相对严重因此只适合数据量小的情况闭散列也不是重点这里给 Key 模型实现参考用于复习即可。
#pragma once
#includestring
#includevector
#includealgorithm
#includeiostream
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};templateclass Key, class Typestruct mapKeyOfType {const Key operator()(const Type aim) {return aim.first;}};templateclass Keystruct HashFunc {size_t operator()(const Key aim) {return size_t(aim);}};templatestruct HashFuncstring {size_t operator()(const string aim) {size_t val 0;for (auto x : aim)val val * 131 x;return val;}};templateclass Typestruct 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;}templateclass Key,class Type,class KeyOfType mapKeyOfTypeKey, Type,class Hash HashFuncKey class HashTable {private:vectorHashDataType tables;size_t size;KeyOfType kot;Hash hashfunc;typedef HashDataType 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) {HashTableKey, Type, KeyOfTypenewht(__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;}};//测试用的函数一起打包在了命名空间中templateclass Key, class Typestruct setKeyOfData {const Key operator()(const Type aim) {return aim;}};void fset() {srand(size_t(time(0)));HashTableint, int, setKeyOfDataint, int ht;vectorinta {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() {HashTablestring, pairstring, 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;
}templateclass Key, class Type,class KeyOfType, class Hash HashFuncKey class HashTable {
private:vectorlistTypetables;size_t size;KeyOfType kot;Hash hashfunc;
public:HashTable(size_t capacity __stl_next_prime(0)) {tables.resize(capacity);size 0;}HashTable(const HashTableKey, Type, KeyOfType, Hash aim):tables(aim.tables), size(aim.size), kot(aim.kot), hashfunc(aim.hashfunc){}};__stl_next_prime函数是从c98的stl_hashtable中获得。因为库中是使用素数作为哈希表的容量实现所以这里选择借鉴。
tables哈希表本体vector数组代替。
size统计元素个数。
kot用于从Type类型中获取键值。
hashfunc用于将Key型键值转化为哈希地址。
迭代器
因为决定了使用list作为哈希桶的容器所以迭代器最好使用list的迭代器。然后迭代器需要访问哈希表以及指定位置的哈希桶。因此迭代器需要包含3个成员list迭代器、哈希表和哈希桶。
因为哈希表直接拷贝的的话开销可能很大所以迭代器内包含哈希表的指针通过指针访问哈希表即可。
在实现过程中我遇到或一个问题参考cSTL-list的模拟实现-CSDN博客我将迭代器也设置成常量迭代器和非常量迭代器用同一个迭代器模板类推导得到但遇到很多常属性迭代器特别是list的迭代器和非常属性的迭代器之间互相赋值等越权的情况。
针对这种情况需要将迭代器类型和哈希表指针类型也作为模板参数也可以使用条件编译选择类型需要编译器支持c11且操作繁琐不如给模板参数方便。
因此迭代器原型参考
templateclass Key, class Type, class KeyOfType,class Ref, class Ptr, class Hash,class listiterator,class vectorptrstruct HashIterator {listiterator it;//list的迭代器vectorptr pt;//哈希表的指针size_t pb;//哈希桶typedef HashIteratorKey, 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 HashIteratorKey, Type, KeyOfType,
Type, Type*, Hash,
typename listType::iterator,
vectorlistType*iterator;typename是让编译器将迭代器识别为类型。
若迭代器带常属性
typedef HashIteratorKey, Type, KeyOfType,
const Type, const Type*, Hash,
typename listType::const_iterator,
const vectorlistType*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
#includestring
#includevector
#includealgorithm
#includeiostream
#includelist
#includeset
#includecassert
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;templateclass Key
struct HashFunc {size_t operator()(const Key aim) {return size_t(aim);}
};template
struct HashFuncstring {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;
}//迭代器实现需要将其他容器的迭代器对象作为成员
templateclass Key, class Type, class KeyOfType,class Ref, class Ptr, class Hash,class listiterator, class vectorptrstruct HashIterator {listiterator it;//list的迭代器vectorptr pt;//哈希表的指针size_t pb;//哈希桶typedef HashIteratorKey, 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()) {dopb;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);}};templateclass Key, class Type,class KeyOfType, class Hash HashFuncKey class HashTable {private:vectorlistTypetables;size_t _size;KeyOfType kot;Hash hashfunc;public:HashTable(size_t capacity __stl_next_prime(0)) {tables.resize(capacity);_size 0;}HashTable(const HashTableKey, Type, KeyOfType, Hash aim):tables(aim.tables), _size(aim._size), kot(aim.kot), hashfunc(aim.hashfunc) {}//迭代器模板类的友元声明templateclass Key, class Type, class KeyOfType,class Ref, class Ptr, class Hash,class listiterator,class vectorptrfriend struct HashIterator;//迭代器typedef HashIteratorKey, Type, KeyOfType,Type, Type*, Hash,typename listType::iterator,vectorlistType*iterator;typedef HashIteratorKey, Type, KeyOfType,const Type, const Type*, Hash,typename listType::const_iterator,const vectorlistType* 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_castconst vectorlistType*(tables),i);return end();}const_iterator end() const {return const_iterator(tables[tables.size() - 1].cend(),const_castconst vectorlistType*(tables),tables.size() - 1);}//插入pairiterator, bool insert(const Type aim) {auto it find(kot(aim));if (it ! end())return make_pair(it, false);//负载因子等于1时扩容if (_size tables.size()) {//生成新表vectorlistTypent(__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;}
};//以下为测试用的函数
templateclass Key, class Type
struct setKeyOfType {const Key operator()(const Type aim) {return aim;}
};templateclass Key, class Type
struct mapKeyOfType {const Key operator()(const Type aim) {return aim.first;}
};//void f() {
// std::vectorintarr { 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)));HashTableint, int, setKeyOfTypeint, int ht;vectorintarr { 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 HashTableint, int, setKeyOfTypeint, 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模型的匹配度HashTableint, pairint, int, mapKeyOfTypeint, pairint, 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
#includehash_table.h
#includefunctional
using std::less;namespace mystd {templateclass Key, class Type, class Compare lessType class unordered_map {public:typedef pairconst Key, Type val_type;public://获取键值的仿函数struct mapKeyOfType {const Key operator()(const val_type key) const {return key.first;}};private:HashTableKey, pairconst Key, Type, mapKeyOfType ht;public://构造函数unordered_map() {}unordered_map(const unordered_map st):ht(st.ht) {}templateclass InputIteratorunordered_map(InputIterator first, InputIterator last) {for (auto it first; it ! last; it)insert(*it);}//迭代器typedef typenameHashTableKey, pairconst Key, Type,mapKeyOfType::iteratoriterator;typedef typenameHashTableKey, pairconst 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();}//插入pairiterator, bool insert(const val_type val) {return pairiterator, 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_mapstring, intmp;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(autox:mp)cout [ x.first : x.second ] ;cout \n;}
}unordered_set
#pragma once
#includehash_table.h
#includefunctional
using std::less;namespace mystd {templateclass Type, class Compare lessType class unordered_set {public:typedef Type Key;//获取键值的仿函数struct setKeyOfType {const Type operator()(const Type key) const {return key;}};//构造函数unordered_set() {}unordered_set(const unordered_setType, Compare st):ht(st.ht) {}templateclass InputIteratorunordered_set(InputIterator first, InputIterator last) {for (auto it first; it ! last; it)insert(*it);}//迭代器typedef typenameHashTableconst Key, Key,setKeyOfType::iteratoriterator;typedef typenameHashTableconst 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();}//插入pairiterator, bool insert(const Type val) {return pairiterator, 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的数据类型作为容器存储的数据HashTableconst Key, Key, setKeyOfType ht;};void fset() {mystd::unordered_setintst;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;}
}
