【C++】——用哈希封装unordered_set和unordered_map

🕗 发布于 2024-11-10 09:50 c++ 哈希算法 开发语言 c语言 算法

文章目录

unordered_set和unordered_map的结构
改造哈希表
迭代器
完整代码

unordered_set和unordered_map的结构

unordered_set和unordered_map的底层就是开散列的哈希表。

template<class K, class Hash = HashFunc<K>> // 在我上一篇博客哈希中介绍了对string类型的特化
class unordered_set
{
public:
    //成员函数
private:
    hash_bucket::HashTable<K,const K,Hash> _ht; // 加const是为了防止K被修改
};

template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
public:
    //成员函数
private:
    hash_bucket::HashTable<K, pair<const K,V,Hash>> _ht;// 加const是为了防止K被修改
};

改造哈希表

改造哈希表节点模版参数

为了更加灵活，我们把哈希表的模版参数定义为T

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

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

增加仿函数

搞个仿函数帮助我们提取键值

struct SetKeyOfT
{
const K& operator() (const K& key)
{
return key;
}
};

struct MapKeyOfT
{
const K& operator()(const pair<K,V>& kv)
{
return kv.first;
}
};

改造插入

我们的比较除了用仿函数替换以外，以及需要将key通过对应的转换函数转换以外，还需要将返回值改造了，返回值是pair类型，第一个参数是迭代器，第二个是bool值

在我的set和map那篇博客中提到过：
insert不仅仅可以插入，还有查找功能。
所以
若待插入元素的键值key在容器当中不存在，则insert函数插入成功，并返回插入后元素的迭代器和true。
若待插入元素的键值key在容器当中已经存在，则insert函数插入失败，并返回容器当中键值为key的元素的迭代器和false。

pair<Iterator, bool> Insert(const T& data)
{
KeyOfT kot;
Iterator it = Find(kot(data));
if (it != End())
return { it, false};

Hash hash;

// 负载因子 == 1时扩容
if (_n == _tables.size())
{
/*HashTable<K, V> newht;
newht._tables.resize(__stl_next_prime(_tables.size() + 1));
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);*/
vector<Node*> newTable(__stl_next_prime(_tables.size()+1));
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = hash(kot(cur->_data)) % newTable.size();
cur->_next = newTable[hashi];
newTable[hashi] = cur;

cur = next;
}

_tables[i] = nullptr;// 将原哈希桶置空

}
// 通过交换让原本哈希表自动回收，同时新哈希表成为当前使用的哈希表
_tables.swap(newTable);
}
// 计算插入位置
size_t hashi = hash(kot(data)) % _tables.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;

return { Iterator(newnode, this), false };
}

改造删除和查找

删除和查找函数中除了比较需要用仿函数替换，以及需要将key通过对应的转换函数转换以外没什么需要注意的地方。

bool Erase(const K& key)
{
KeyOfT kot;
size_t hashi = key % _tables.size();
// 记录前一个节点，等会好链接
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
// 头结点
_tables[hashi] = cur->_next;
}
else
{
// 中间节点
prev->_next = cur->_next;
}

delete cur;
--_n;

return true;
}
else
{// 没找到就遍历下一个
prev = cur;
cur = cur->_next;
}
}

return false;
}
Iterator Find(const K& key)
{
KeyOfT kot;
Hash hash;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return Iterator(cur, this);
}

cur = cur->_next;
}

return End();
}

迭代器

正因为unordered_set和unordered_map底层是开散列的哈希表，有些节点与节点之间并不连续，所以迭代器也肯定需要进行封装。
为了同时支持const迭代器与普通迭代器，我们需要三个模版参数，第一个模版参数T代表数据存储类型，第二个模版参数Ref代表存储类型的引用，第三个模版参数Ptr代表存储类型的指针。
在迭代器中应该有两个参数，一个就是节点指针，另一个就是我们的哈希表的指针，因为我们可能需要遍历哈希表的下一个桶的位置。其中为了方便访问哈希表的私有成员我们可以将迭代器设为友元类，并且在最开始要给出哈希表的声明。然后我们重载如*，->等常见操作符。

template<class K, class T, class KeyOfT, class Hash>
class HashTable;

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

Node* _node;
const HT* _ht;

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

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

Ptr operator->()
{
return &_node->_data;
}
bool operator == (const Self& s)
{
return _node == s._node;
}

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

begin()就是哈希表中第一个有数据的节点，end()可以先设置为nullptr

Iterator Begin()
{
if (_n == 0)
return End();

for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return Iterator(cur, this);
}
}

return End();
}

Iterator End()
{
return Iterator(nullptr, this);
}


ConstIterator Begin() const
{
if (_n == 0)
return End();

for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return ConstIterator(cur, this);
}
}

return End();
}

ConstIterator End() const
{
return ConstIterator(nullptr, this);
}

因为哈希表迭代器通常是单向迭代器，所以只支持++操作，如果想实现–也可以搞一个双链表的哈希桶

Self& operator++()
{
if (_node->_next)
{
// 当前桶还有数据，走到当前桶下一个节点
_node = _node->_next;
}
else
{
// 当前桶走完了，找下一个不为空的桶
KeyOfT kot;
Hash hash;
size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
++hashi;
while (hashi < _ht->_tables.size())
{
_node = _ht->_tables[hashi];

if (_node)
break;
else
++hashi;
}

// 所有桶都走完了，end()给的空标识的_node
if (hashi == _ht->_tables.size())
{
_node = nullptr;
}
}

return *this;
}

因为unordered_set键和值相同，所以它的迭代器一般是const迭代器，就是为了防止K被修改。所以我们也重载一个构造函数，将普通迭代器初始化为一个const迭代器。

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

最后直接复用改造好的哈希表接口就行

template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K,V>& kv)
{
return kv.first;
}
};
public:
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_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();
}

V& operator[](const K& key)
{
pair<iterator, bool> ret = Insert({ key, V() });
return ret.first->second;
}
pair<iterator, bool> Insert(const pair<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);
}
private:
hash_bucket::HashTable<K, pair<const K,V>, MapKeyOfT, Hash> _ht;
};

template<class K, class Hash = HashFunc<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator() (const K& key)
{
return key;
}
};

public:
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;

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

iterator begin()
{
return _ht.Begin();
}

iterator end()
{
return _ht.End();
}

const_iterator begin() const
{
return _ht.Begin();
}

const_iterator end() const
{
return _ht.End();
}

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

bool Erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};

完整代码

HashTable.h

#pragma once  
#include <vector>  
#include <iostream>
using namespace std;

enum State 
{
    EMPTY,
    EXIST,
    DELETE 
};

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

template<> // 在key为string时，编译器会优先选择全特化
struct HashFunc<string>
{
    size_t operator()(const string& s)
    {
        size_t ret = 0;
        for (auto a : s)
        {
            ret += a;
            ret *= 131;
        }
        return ret;
    }
};

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;
}

namespace open_address
{
    // 为了方便进行比较所写的仿函数
    template<class K>
    struct HashFunc
    {
        size_t operator()(const K& key)
        {
            return (size_t)key;
        }
    };

    

    template<class K, class V>
    struct HashData
    {
        pair<K, V> _kv;
        State _state = EMPTY;
    };

  

    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable
    {
    public:
        HashTable()
            : _tables(11)
            , _n(0)
        {}

        bool Insert(const std::pair<K, V>& kv)
        {
            if (Find(kv.first))
                return false;

            if (_n * 10 / _tables.size() >= 7)
            {
                HashTable<K, V> newht;
                newht._tables.reserve(_tables.size() * 2);
                for (auto& data : _tables)
                {
                    if (data._state == EXIST)
                    {
                        newht.Insert(data._kv);
                    }
                }
                _tables.swap(newht._tables);
            }
            Hash hash;
            size_t hash0 = hash(kv.first) % _tables.size();
            size_t hashi = hash0;
            size_t i = 1;
            while (_tables[hashi]._state == EXIST)
            {
                hashi = (hash0 + i) & _tables.size();
                ++i;
            }

            _tables[hashi]._kv = kv;
            _tables[hashi]._state = EXIST;
            ++_n;
            return true;
        }

        HashData<K, V>* Find(const K& key)
        {
            Hash hash;
            size_t hash0 = hash(key) % _tables.size();
            size_t hashi = hash0;
            size_t i = 1;
            while (_tables[hashi]._state != EMPTY)
            {
                if (_tables[hashi]._kv.first == key)
                {
                    return &_tables[hashi];
                }
                hashi = (hash0 + i) & _tables.size();
                ++i;
            }
            return nullptr;
        }

        bool Erase(const K& key)
        {
            HashData<K, V>* ret = Find(key);
            if (ret)
            {
                ret->_state = DELETE;
                return true;
            }
            else
            {
                return false;
            }
        }

    private:
        vector<HashData<K, V>> _tables;
        size_t _n; // 记录数据个数 
    };
}




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

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

// 前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

Node* _node;
const HT* _ht;

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

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

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

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

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

Self& operator++()
{
if (_node->_next)
{
// 当前桶还有数据，走到当前桶下一个节点
_node = _node->_next;
}
else
{
// 当前桶走完了，找下一个不为空的桶
KeyOfT kot;
Hash hash;
size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
++hashi;
while (hashi < _ht->_tables.size())
{
_node = _ht->_tables[hashi];

if (_node)
break;
else
++hashi;
}

// 所有桶都走完了，end()给的空标识的_node
if (hashi == _ht->_tables.size())
{
_node = nullptr;
}
}

return *this;
}

};

template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
// 友元声明
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
friend struct HTIterator;

typedef HashNode<T> Node;
public:
typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;

Iterator Begin()
{
if (_n == 0)
return End();

for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return Iterator(cur, this);
}
}

return End();
}

Iterator End()
{
return Iterator(nullptr, this);
}


ConstIterator Begin() const
{
if (_n == 0)
return End();

for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return ConstIterator(cur, this);
}
}

return End();
}

ConstIterator End() const
{
return ConstIterator(nullptr, this);
}

HashTable()
:_tables(__stl_next_prime(0))
, _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;
}
}

pair<Iterator, bool> Insert(const T& data)
{
KeyOfT kot;
Iterator it = Find(kot(data));
if (it != End())
return { it, false};

Hash hash;

// 负载因子 == 1时扩容
if (_n == _tables.size())
{
/*HashTable<K, V> newht;
newht._tables.resize(__stl_next_prime(_tables.size() + 1));
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);*/
vector<Node*> newTable(__stl_next_prime(_tables.size()+1));
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = hash(kot(cur->_data)) % newTable.size();
cur->_next = newTable[hashi];
newTable[hashi] = cur;

cur = next;
}

_tables[i] = nullptr;// 将原哈希桶置空

}
// 通过交换让原本哈希表自动回收，同时新哈希表成为当前使用的哈希表
_tables.swap(newTable);
}
// 计算插入位置
size_t hashi = hash(kot(data)) % _tables.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;

return { Iterator(newnode, this), false };
}

Iterator Find(const K& key)
{
KeyOfT kot;
Hash hash;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return Iterator(cur, this);
}

cur = cur->_next;
}

return End();
}

bool Erase(const K& key)
{

KeyOfT kot;
size_t hashi = key % _tables.size();
// 记录前一个节点，等会好链接
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
// 头结点
_tables[hashi] = cur->_next;
}
else
{
// 中间节点
prev->_next = cur->_next;
}

delete cur;
--_n;

return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}

return false;
}
private:
vector<Node*> _tables; // 指针数组
size_t _n = 0;   // 表中存储数据个数
}

原文地址：https://blog.csdn.net/super_coders/article/details/143635723

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

上一篇：Go语言的并发安全与互斥锁
下一篇：python 输入输出ACM

Linux系统下svn新建目录
Linux安装svn自行查找。
阅读更多2024-11-14
Scala的不可变Map常用操作
/3.1 get方法：输入key，如果找到，就返回包装数据，如果没有找到，就返回None。val map1 = Map("鄂"->"湖北省","
阅读更多2024-11-14
mqtt学习笔记（一）
mqtt相关笔记（一）之mqtt初探，以提出、解决问题的方式来逐步学习
阅读更多2024-11-14
Ken和Bwk趣说UNIX
[肯汤普森和布莱恩(AWK作者之一)趣说UNIX](https://www.bilibili.com/video/BV1nP411t7gt/ “肯汤普森和布莱恩(AWK作者之一 “肯汤普森和布莱恩(A
阅读更多2024-11-14
【CentOS】中的Firewalld：全面介绍与实战应用（上）
本文深入探讨了CentOS操作系统中Firewalld防火墙的全面功能与实战应用。首先，文章概述了Firewalld的基本概念，强调了它在现代Linux系统中作为动态管理防火墙规则的重要工具的地位。与
阅读更多2024-11-14
新手小白学习docker第七弹------安装redis集群大厂面试
新手小白学习docker第七弹----安装redis集群大厂面试
阅读更多2024-11-14
/// ts中的三斜线指令 | 前端
包），你需要在你的项目中以某种方式告诉TypeScript编译器这些类型定义的存在。三斜线指令是一种在单个文件中这样做的方式，虽然在实际项目中，更常见的是通过。1. 这行代码是TypeScript中
阅读更多2024-11-14
快速掌握——python类封装[私有属性方法]、继承【python进阶】(内附代码)
python类的封装【私有属性、私有方法、属性装饰器】类的继承
阅读更多2024-11-14
2024年5款大屏可视化工具多维分析对比
经过对市场上多款大屏可视化工具的深入研究和对比，强烈推荐FineVis作为您的首选。无论您是希望快速搭建大屏项目、展示复杂3D模型还是实现多屏适应和实时数据分析，FineVis都能满足您的需求。文章中
阅读更多2024-11-14
计算机网络-mac地址与ip地址的区别总结
mac地址在OSI模型中的第二层数据链路层工作，数据链路层基于mac地址进行转发数据帧【交换机基于mac地址表转发数据】ip地址在OSI模型中的第三层网络层工作，网络层基于ip地址转发报文【路由器
阅读更多2024-11-14