网站公示如何做链接,中太建设集团官方网站,网站运营管理的内容有哪些,网站建设价格怎么算个人主页#xff1a;仍有未知等待探索-CSDN博客 专题分栏#xff1a;C 本文着重于模拟实现哈希表#xff0c;并非是哈希表的使用。
实现的哈希表的底层用的是线性探测法#xff0c;并非是哈希桶。
目录 一、标准库中的哈希表
1、unordered_map
2、unordered_set
二、模… 个人主页仍有未知等待探索-CSDN博客 专题分栏C 本文着重于模拟实现哈希表并非是哈希表的使用。
实现的哈希表的底层用的是线性探测法并非是哈希桶。
目录 一、标准库中的哈希表
1、unordered_map
2、unordered_set
二、模拟实现哈希表
1、结构
2、注解hashtable的模板参数
3、重难点
1、二元“!” 没有找到接收类型的右操作数的运算符编辑
2、迭代器的本质、const和非const的区别
3、类A在类B的上面想要在类A中使用以类B为类型的变量怎么办
4、类A在类B的上面想要在类A中使用类B的私有成员怎么办
三、代码 一、标准库中的哈希表 这两个是两种不同映射关系的哈希表。 unordered_map是 Key - Value 的映射关系 也就是 关键字和键值 之间的映射 unordered_set是 Value 的映射关系也就是只有 键值 的映射 这两种不同的映射关系从各自的模板参数就能看出来。 1、unordered_map
unordered_map又分为两种一种是unordered_map另一种是unordered_multimap。 这两种有什么区别呢 以unordered_map为例 这里面的模板参数 Key - T 就是这个容器存储的键值关系。 2、unordered_set
同样unordered_set又分为两种一种是unordered_set另一种是unordered_multiset。 这两个的区别和unordered_map中两个的区别一样。
二、模拟实现哈希表
1、结构
在模拟实现哈希表前我们要知道整个实现的结构要有完整性的认识。 这个就是哈希表的大致底层结构。 2、注解hashtable的模板参数 Key是上层结构也就是unordered_set、unordered_map的关键字。T是存的关键字和键值的映射。 也就是unordered_setpairKey, Keyunordered_map:pairKey, Vaule Ptr是T*。Ref是T。KeyofT是一个仿函数用来取T的Key。因为在这一层也不知道上一层是unordered_set、unordered_map所以还需要传一个仿函数来进行取值。hashfunc是一个仿函数用来计算hash映射值。 对于一个整数怎么存储到哈希表里需要对其进行hash计算将这个整数取模于表的大小得到。 对于一个字符串怎么存储到哈希表里需要对其进行hash计算将这个字符串转换成整数然后将这个整数取模于表的大小得到下标。 如果得到的下标冲突了就用哈希线性探测法解决冲突。 3、重难点
写完不算难难的是找bug。
1、二元“!” 没有找到接收类型的右操作数的运算符 类型不匹配你可以去你出错的位置看看该类型的模板参数的类型匹不匹配。 2、迭代器的本质、const和非const的区别 迭代器就是模拟的指针的行为。 const迭代器和非const迭代器的区别就是限制其*和-运算符的返回值。 3、类A在类B的上面想要在类A中使用以类B为类型的变量怎么办 在类A的前面加上类B的前置声明即可。 4、类A在类B的上面想要在类A中使用类B的私有成员怎么办 在类B中加上类A的友元。 三、代码
hash.h
#pragma once#include iostream
#include vector
#include string
using namespace std;
enum State
{Empty,Exist,Delete
};
// hash_func --- 用来对任意类型进行编码
templateclass T
struct hash_func
{size_t operator()(const T _val){return (size_t)_val;}
};
// 对string类型进行特化
template
struct hash_funcstring
{size_t operator()(const string val){size_t hash 0;for (auto e : val){hash * 131;hash e;}return hash;}
};// 闭散列 --- 线性探测
// 这里的 T 是 K or pairK, V
template class T
struct HashNode
{HashNode() {}HashNode(const HashNode) default;HashNode(const T data, const State state):_data(data),_state(state){}T _data;State _state Empty;};template class K, class V, class Ptr, class Ref, class KeyofT, class HashFunc
class HashTable;templateclass K, class T, class Ptr, class Ref, class KeyofT
struct HashTable_iterator
{typedef HashNodeT HashNode;typedef HashTable_iteratorK, T, Ptr, Ref, KeyofT iterator;typedef HashTableK, T, Ptr, Ref, KeyofT, hash_funcK hashtable;HashNode* _node;hashtable* _pht;KeyofT kot;hash_funcK hs;HashTable_iterator(HashNode* node, hashtable* pht):_node(node), _pht(pht){}bool operator!(const iterator s){return _node ! s._node;}Ref operator*(){return _node-_data;}Ptr operator-(){return (_node-_data);}iterator operator(){int hashindex 0;for (int i 0; i _pht-_tables.size(); i){// 找到当前节点的位置寻找下一个节点的位置if (_pht-_tables[i] _node){hashindex i;break;}}for (int i hashindex 1; i _pht-_tables.size(); i){if (_pht-_tables[i] _pht-_tables[i]-_state Exist){_node _pht-_tables[i];return *this;}}_node nullptr;return *this;}
};template class K, class V, class Ptr, class Ref, class KeyofT, class HashFunc hash_funcK
class HashTable
{typedef HashNodeV hashnode;typedef HashTableK, V, Ptr, Ref, KeyofT, hash_funcK hashtable;templateclass K, class T, class Ptr, class Ref, class KeyofTfriend struct HashTable_iterator;typedef HashTable_iteratorK, V, Ptr, Ref, KeyofT iterator;public:hash_funcK hf;KeyofT kot;HashTable(size_t n 10):_size(0){_tables.resize(n);}iterator begin(){for (int i 0; i _tables.size(); i){hashnode* cur _tables[i];if (cur cur-_state Exist){// this - HashTable*return iterator(cur, this);}}return end();}iterator end(){return iterator(nullptr, this);}// V : V or pairK, Vpairiterator, bool insert(const V e){iterator it find(kot(e));if (it ! end()){return make_pair(it, false);}if (_size * 10 / _tables.size() 7){hashtable newt(_tables.size() * 2);for (int i 0; i _tables.size(); i ){if (_tables[i]-_state Exist){newt.insert(_tables[i]-_data);}}_tables.swap(newt._tables);}size_t hashindex hf(kot(e)) % _tables.size();while (_tables[hashindex] _tables[hashindex]-_state Exist){hashindex;hashindex % _tables.size();}hashnode* newnode new hashnode(e, Exist);swap(_tables[hashindex], newnode);delete newnode;_size;return make_pair(iterator(_tables[hashindex], this), true);}iterator find(const K key){size_t hashindex hf(key)% _tables.size();while (_tables[hashindex] _tables[hashindex]-_state ! Empty){if (_tables[hashindex]-_state Exist kot(_tables[hashindex]-_data) key){return iterator(_tables[hashindex], this);}hashindex;hashindex % _tables.size();}return iterator(nullptr, this);}bool erase(const K key){iterator t find(key);if (t._node nullptr) return false;else{t._node-_state Delete;--_size;}return true;}
private:vectorhashnode* _tables;size_t _size;
};unordered_map.h
#pragma once#include hash.htemplateclass K, class V
class unordered_map
{struct MapKeyofT{const K operator()(const pairconst K, V key){return key.first;}};
public:typedef HashTableK, pairconst K, V, pairconst K, V*, pairconst K, V, MapKeyofT, hash_funcK HashTable;typedef HashNodepairconst K, V HashNode;typedef HashTable_iteratorK, pairconst K, V, pairconst K, V*, pairconst K, V, MapKeyofT iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool insert(const pairconst K, V kv){return _ht.insert(kv);}iterator find(const K key){return _ht.find(key);}bool erase(const K key){return _ht.erase(key);}V operator[](const K key){pairK, V pkv make_pair(key, V());pairiterator, bool ret insert(pkv);return ret.first-second;}
private:HashTable _ht;
};//void map01()
//{
// unordered_mapint, int s1;
// vectorint v { 1, 8, 34, 5, 3, 4, 8, 1111, 111, 11 };
//
// for (auto e : v)
// {
// s1.insert({e, e});
// }
//
// s1.erase(1111);
// s1.erase(8);
//}
//
//void map02()
//{
// unordered_mapstring, int s1;
// vectorstring v { 1234, 233, a, b, 1234, 233, a, b };
//
// for (auto e : v)
// {
// s1.insert({e, 1});
// }
//
// s1.erase(1234);
// s1.erase(8);
//}
unordered_set.h
#pragma once#include hash.htemplateclass K
class unordered_set
{struct SetKeyofT{const K operator()(const K key){return key;}};
public:typedef HashTableK, K, const K*, const K, SetKeyofT, hash_funcK HashTable;typedef HashNodeK HashNode;typedef HashTable_iteratorK, K, const K*, const K, SetKeyofT iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool insert(const K val){return _ht.insert(val);}iterator find(const K key){return _ht.find(key);}bool erase(const K key){return _ht.erase(key);}
private:HashTable _ht;
};//void set01()
//{
// unordered_setint s1;
// vectorint v { 1, 8, 34, 5, 3, 4, 8, 1111, 11, 11};
//
// for (auto e : v)
// {
// s1.insert(e);
// }
//
// s1.erase(1111);
//}
//void set02()
//{
// unordered_setstring s;
// vectorstring v { 1234, 233, a, b };
//
// for (auto e : v)
// {
// s.insert(e);
// }
//
// s.erase(1111);
// s.erase(1234);
//}
谢谢大家
