哈希封装unordered_map和unordered_set

🕗 发布于 2024-04-20 10:58 哈希算法算法后端

一. 哈希表的改造

咱们这里还是跟Map和Set的封装一样的道理，没有必要为了unordered_map和unordered_set传的参数不同就实例化两份代码，可以直接通过模板参数来解决。那么unordered_map传的是pair<key,value>，unordered_set传的是key。对于哈希表还有不懂的可以去看上一篇博客(http://t.csdnimg.cn/O5Vg5)，对Map和Set封装还有不懂的可以去看博客(http://t.csdnimg.cn/dOSOt)。

所以咱们的代码改造成：

namespace hash_bucket
{
template<class T>
struct HashNode
{
HashNode<T>* _next;
T _data;

HashNode(const T& data)
:_next(nullptr)
, _data(data)
{}
};

    template<class K, class T,class KeyOfT,class Hash>
    //为了获得传参中的key，用KeyOfT仿函数
    //考虑unordered_map和unordered_set里面的元素不只是整型，所以用仿函数Hash对元素进行处理
class HashTable
{
typedef HashNode<T> Node;

public:

int GetNextPrimer(int val)
{
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53,97,193,389,
1543,3079,6151,12289,
49157,98317,196613,393241,
1572869,3145739,6291469,12582917,
50331653,100663319,201326611,402653189,
1610612741, 3221225473, 4294967291
};
for (size_t i = 0; i < __stl_num_primes; i++)
{
if (__stl_prime_list[i] > val)
{
return __stl_prime_list[i];
}
}
}
HashTable()
{
_tables.resize(GetNextPrimer(1), nullptr);
_n = 0;
}
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
        
        //插入
bool insert(const pair<K, V>& kv) {
if (find(kv.first))
return false;

//调用仿函数的匿名对象来将key转换为整数
size_t hashi = Hash()(kv.first) % _tables.size();
//哈希桶头插
Node* newNode = new Node(kv);
newNode->next = _tables[hashi];
_tables[hashi] = newNode;
++_n;

return true;
}

//查找
Node* find(const K& key) {
size_t hashi = Hash()(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) {
//由于单链表中删除节点需要改变上一个节点的指向，所以这里不能find后直接erase
size_t hashi = Hash()(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
//删除还要分是否为头结点
if (cur->_kv.first == key) {
if (cur == _tables[hashi])
_tables[hashi] = cur->next;
else
prev->next = cur->next;

delete cur;
--_n;
return true;
}

//迭代
prev = cur;
cur = cur->next;
}

return false;
}
        private:
    vector<Node*> _tables;//指针数组
    size_t _n;
    };
}

到此时我们还没有出现新的东西，一切都是在《Map和Set的封装》和《哈希开散列的实现》两个基础上结合起来的。而对迭代器的封装也是如此。

二. 迭代器的封装

我们还是采用之前的模板参数来实现，需要注意的是，由于迭代器里面要用到自定义类HashTable，而由于HashTable 我把他排版在了迭代器的下面，所以我们要先在迭代器的前面申明这个类存在，因为编译器只会向上兼容，这也是一个可以借鉴的点。而我们自定义类HashTable里面也要用到迭代器，那么反过来迭代器在类的上方，可以向上兼容，所以不用在类的前面申明了。

特别注意的是：

如果你把迭代器定义在了类HashTable的下面，就无需在迭代器的上面进行声明，而要在类HashTable的上面声明迭代器的存在。
此处迭代器要对类HashTable里面的私有成员进行访问，所以要在类HashTable里面对迭代器设置友元，使迭代器能访问私有成员。

那么类HashTable中设置友元具体是：

template<class K, class T,class KeyOfT,class Hash>
class HashTable
{
typedef HashNode<T> Node;
//友元让迭代器能访问私有成员
template<class K, class T, class KeyOfT, class Hash>
friend struct __HTIterator;

    //...
private:
vector<Node*> _tables;//指针数组
size_t _n;
};

此处迭代器里面值得一讲的是++操作(因为哈希表开散列的结构是单链表，所以没有必要实现--操作)，我们得分情况来看，如果这个元素之后在用一个桶中还有元素，那么直接++就行；如果没有，则要依次向后找，找到下一个不为空的桶开始遍历。

//声明有HashTable这个类
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
template<class K,class T,class KeyOfT,class Hash>
struct __HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef __HTIterator<K, T, KeyOfT, Hash> Self;
Node* _node;
HT* _ht;

__HTIterator(Node* node,HT* ht)
:_node(node)
,_ht(ht)
{}

T& operator*()
{
return _node->_data;
}

T* operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next)
{
_node=_node->_next;
}
else
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();
//下一个桶
hashi++;
while (hashi < _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
++hashi;
}
if (hashi == _ht->_tables.size())
{
_node=nullptr;
}
}
return *this;
}

bool operator!=(const Self& s)
{
return _node != s._node;
}
};

三. 哈希表整体代码

那么我们哈希表的整体代码就是：

namespace hash_bucket
{
template<class T>
struct HashNode
{
HashNode<T>* _next;
T _data;

HashNode(const T& data)
:_next(nullptr)
, _data(data)
{}
};

//声明有HashTable这个类
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
template<class K,class T,class KeyOfT,class Hash>
struct __HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef __HTIterator<K, T, KeyOfT, Hash> Self;
Node* _node;
HT* _ht;

__HTIterator(Node* node,HT* ht)
:_node(node)
,_ht(ht)
{}

T& operator*()
{
return _node->_data;
}

T* operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next)
{
_node=_node->_next;
}
else
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();
//下一个桶
hashi++;
while (hashi < _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
++hashi;
}
if (hashi == _ht->_tables.size())
{
_node=nullptr;
}
}
return *this;
}

bool operator!=(const Self& s)
{
return _node != s._node;
}
};
template<class K, class T,class KeyOfT,class Hash>
class HashTable
{
typedef HashNode<T> Node;
//友元让迭代器能访问私有成员
template<class K, class T, class KeyOfT, class Hash>
friend struct __HTIterator;

public:
typedef __HTIterator<K, T, KeyOfT, Hash> iterator;

int GetNextPrimer(int val)
{
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53,97,193,389,
1543,3079,6151,12289,
49157,98317,196613,393241,
1572869,3145739,6291469,12582917,
50331653,100663319,201326611,402653189,
1610612741, 3221225473, 4294967291
};
for (size_t i = 0; i < __stl_num_primes; i++)
{
if (__stl_prime_list[i] > val)
{
return __stl_prime_list[i];
}
}
}
HashTable()
{
_tables.resize(GetNextPrimer(1), nullptr);
_n = 0;
}
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}

iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
//用this将HashTable传过去
return iterator(_tables[i],this);
}
}
return end();
}

iterator end()
{
return iterator(nullptr, this);
}

pair<iterator,bool> Insert(const T& data)
{
KeyOfT kot;
iterator it = Find(data);
if (it!=end())
{
return make_pair(it, false);
}
Hash hs;
//负载因子到1就扩容
if (_n == _tables.size())
{
//法一：采用闭散列的扩容方法--复用insert接口
//优点：实现简单；
//缺点：先开辟节点再释放节点代价大
//HashTable<K, V, Hash> newHT;
//newHT._tables.resize(_tables.size() * 2, nullptr);
//for (size_t i = 0; i < _tables.size(); ++i) {
//Node* cur = _tables[i];
//while (cur) {
//newHT.insert(cur->_kv);
//cur = cur->next;
//}
//}
//_tables.swap(newHT._tables);

//法二：取原表中的节点链接到当前表中
//缺点：实现比较复杂
//优点：不用再去开辟新节点，也不用释放旧节点，消耗小
//不用跟开放地址法一样重新创一个HashTable对象，因为会造成指针
//节点创建又删除
vector<Node*> newvector(_tables.size()*2,nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur1 = _tables[i];
while (cur1)
{
Node* cur2 = cur1->_next;
size_t hashi = hs(kot(cur1->_data)) % newvector.size();
cur1->_next = newvector[i];
newvector[i] = cur1;
cur1 = cur2;
}

//把原来的指针置空
_tables[i] = nullptr;
}
_tables.swap(newvector);
}

size_t hashi = hs(kot(data)) % _tables.size();
//头插不用看该位置是否为空
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
_n++;
return make_pair(iterator(newnode,this), true);
}

iterator Find(const T& data)
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(data)) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (hs(kot(cur->_data)) == hs(kot(data)))
{
return iterator(cur,this);
}
cur = cur->_next;
}
return iterator(nullptr,this);
}
bool Erase(const T& data)
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(data)) % _tables.size();
Node* cur = _tables[hashi];
Node* prev = nullptr;
while (cur)
{
if (cur->_data == kot(data))
{
if (prev)
{
prev->_next = cur->_next;
}
else
{
_tables[hashi] = cur->_next;
}
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;//指针数组
size_t _n;
};
}

注意：由于迭代器的构造要用到HashTable，所以在HashTable类中插入操作的时候，用this返回哈希表。

四. unordered_set和unordered_map具体实现

3.1 unordered_set具体实现

那么到此时，unordered_set的具体实现已经很清楚了。这里我们要知道unordered_set里面的元素key是不能被改变的，所以为其附上const的枷锁。

//int类型
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};

namespace yjy
{
template<class K,class Hash=HashFunc<K>>
class unordered_set
{
struct KeyOfTSet
{
const K& operator()(const K& key)
{
return key;
}
};
public:
    typedef typename hash_bucket::HashTable<K,const K, KeyOfTSet, Hash>::iterator iterator;

iterator begin()
{
return us.begin();
}

iterator end()
{
return us.end();
}

pair<iterator,bool> Insert(const K& key)
{
return us.Insert(key);
}

iterator Find(const K& key)
{
return us.Find(key);
}

bool Erase(const K& key)
{
us.Erase(key);
}
typedef hash_bucket::HashTable<K,const K, KeyOfTSet,Hash> _set;
private:
_set us;
};
}

3.2 unordered_map具体实现

同样，unordered_map的具体实现已经很清楚了。这里我们要知道unordered_map的pair<key,value>里的key是不能被改变的，所以也要为其附上const的枷锁。

//int类型
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};

namespace yjy
{
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct KeyOfTMap
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename hash_bucket::HashTable<K, pair<const K, V>, KeyOfTMap, Hash>::iterator iterator;

iterator begin()
{
return um.begin();
}

iterator end()
{
return um.end();
}

pair<iterator, bool> Insert(const pair<K, V>& kv)
{
return um.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = Insert(make_pair(key,V()));
return ret.first->second;
}

iterator Find(const K& key)
{
return um.Find(key);
}

bool Erase(const K& key)
{
um.Erase(key);
}
typedef hash_bucket::HashTable<K, pair<const K, V>, KeyOfTMap, Hash> _map;
private:
_map um;
};
}

总结

好了，到这里今天的知识就讲完了，大家有错误一点要在评论指出，我怕我一人搁这瞎bb，没人告诉我错误就寄了。

祝大家越来越好，不用关注我（疯狂暗示）

原文地址：https://blog.csdn.net/weixin_75172965/article/details/137939429

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：DRF 请求与响应
下一篇：C# 中的策略模式：从基础到高级

百度搜索AI探索版多线程批量生成TXT原创文章软件-可生成3种类型文章
8、有8种标题模式可自由设置：1、关键词 2、百度搜索AI原创标题(以原创标题写文章) 3、关键词 + 百度搜索AI原创标题 4、关键词 + 下拉副标题 5、关键词 + 下拉副标题
阅读更多2024-11-16
批量更改表格数据不更新、不实时渲染、或则watch监听不到表格修改数据
第一种方法是监听的watch中添加deep:true，但是这种方法对我来说不管用，我需要监听某一列的数据，在批量更改后，统计数量，这时候，手动更改数据，他的监听并不能实时抓捕到。我这里的功能是，批量更
阅读更多2024-11-16
【大语言模型】ACL2024论文-10 CSCD-IME: 纠正拼音输入法产生的拼写错误
本文研究了中文拼写校正（CSC）任务，特别是针对拼音输入法（IME）产生的错误。作者首先介绍了一个包含40,000个标注句子的中文拼写校正数据集（CSCD-IME），这些句子来自新浪微博上的官方媒体帖
阅读更多2024-11-16
react 中 memo 模块作用
memo`是一个用于优化组件性能的高阶组件。
阅读更多2024-11-16
随笔content1
如果组件的具体类型无法获得，或者你并不关心组件的具体类型，那么可以使用 ComponentPublicInstance。当你将一个响应式对象的属性赋值或解构到一个本地变量时，访问或赋值该变量是非响应式
阅读更多2024-11-16
Java多线程底层设计思路
Java 的多线程设计比较全面和灵活，提供了多种方式来定义任务和管理线程，特别是通过Runnable和Callable接口，可以实现任务和线程的解耦，适应不同的应用场景。与 Python 和 C# 相
阅读更多2024-11-16
第七章利用CSS和多媒体美化页面
当设置为show时，就意味着当表格中某个单元格没有内容时，依然会显示该单元格的边框，这样可以保持表格的完整性和视觉上的连贯性，让用户在浏览表格时，能清晰地看到每个单元格的范围。而当参数为hide时，则
阅读更多2024-11-16
Cyberchef配合Wireshark提取并解析TCP/FTP流量数据包中的文件
通过cyberchef还原pcap数据包中TCP上层的文件内容，提升wireshark分析数据包的效率
阅读更多2024-11-16
redis
Redis 本质上是一个 Key-Value 类型的内存数据库，整个数据库加载在内存当中进行操作，定期通过异步操作把数据库数据 flush 到硬盘上进行保存。因为是纯内存操作， Redis 的性能
阅读更多2024-11-16
C++学习笔记之string容器、vector容器
vector可以动态扩展，动态扩展并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间。我们读过的书，说过的话，见过的山水，见到的人和事，最终都会变成我们脚下的的路。
阅读更多2024-11-16