哈希封装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# 中的策略模式：从基础到高级

MYSQL常用基本操作总结
SQL查询中各个关键字的执行先后顺序： from > on> join > where > group by > with > having >select
阅读更多2024-09-19
JAVA并发编程系列之Semaphore信号量剖析
候选人，心中万马奔腾！！！吐了一口82年老血，当场砸电脑回家！原因是：腾讯T2面试，现场限时3分钟+限最多20行代码，模拟地铁口安检进站。其中安检入口10个，当前排队人数是100个，每个人安检进站耗时
阅读更多2024-09-19
24年蓝桥杯及攻防世界赛题-MISC-2
24年蓝桥杯及攻防世界赛题-MISC-2
阅读更多2024-09-19
干货-并发编程提高——重谈 RUNNABLE-上篇（十四）
直接看它的 Javadoc 中的说明：一个在 JVM 中执行的线程处于这一状态中。（A threadexecuting而传统的进（线）程状态一般划分如下：注：这里的进程指早期的单线程进程，这里所谓进程
阅读更多2024-09-19
phpstudy 建站使用 php8版本打开 phpMyAdmin后台出现网页提示致命错误：（phpMyAdmin这是版本问题导致的）
将网站根目录phpMyAdmin4.8.5里面的文件换成官网下载的5.2.1版本即可。重启网站，打开phpMyAdmin后台即可（若打不开更改 mysql密码即可）解决方法：官网下载phpmyadm
阅读更多2024-09-19
零工市场小程序：保障灵活就业
截止2024年高校毕业生达到1179万，在今年的经济情况下，就业市场就面临着比较大的压力，许多毕业生面临一时之间难以找到合适的工作的问题，那么求职者就会需要一份临时的工作来得到报酬，面对传统的找零工方
阅读更多2024-09-19
Linux中权限和指令
mv指令是move的缩写，用来，经常用来备份文件或目录。
阅读更多2024-09-19
Redis 底层揭秘：事务与 Lua 脚本的工作原理
定义Lua 是一种轻量级的脚本语言，它可以在 Redis 中被执行，用于实现复杂的逻辑操作。优势与事务相比，Lua 脚本具有更高的性能和更好的灵活性。Lua 脚本可以在 Redis 服务器端一次性执行
阅读更多2024-09-19
Vue3使用shapefile读取矢量数据，以数组形式返回坐标点
【代码】Vue3使用shapefile读取矢量数据，以数组形式返回坐标点。
阅读更多2024-09-19
WEB 编程：使用富文本编辑器 Quill 配合 WebBroker 后端
评估了好几个，最后选择这个开源的。把前端代码，存储为一个单独的文本文件，方便随便哪个页面需要的时候可以使用。相当于封装为一个独立的对象，方便代码重用。
阅读更多2024-09-19