Hash hs

前言：本篇文章继续分享新的容器unordered_map和set。前边我们分享过map和set，其底层为红黑树，而unordered_map和set的底层则为哈希表，因此在unordered_map和set的实现中，我们可以效仿许多在map和set的中就分享过的一些知识，所以在本篇文章中，就不对分享过的知识进行重复讲解。 而unordered_map和set与map和set的区别，即为红黑树和哈希表的区别。 目录 1.unordered_map 2.unordered_set 一.修改hash 我们所实现的普通哈希表肯定是无法直接拿来作为unordered_map和set的底层代码的，所以我们需要对其进行优化修改，完整代码如下： template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; struct HashStringFunc { size_t operator()(const string& s) { size_t hash = 0; for...

C++ STL 库中，unordered_map 和 unordered_set 容器的底层为哈希表，本文将简单模拟哈希表（哈希桶），unordered_map 和 unordered_set 只需封装哈希表的接口即可实现。 1.

unordered —— 无序的，从表面上来看，与 map 和 set 不同之处就在于，unordered_map 和 unordered_set 无法保证插入数据是有序的； 尽管如此，由于这两种容器内部封装了“哈希桶”，可以实现快速查找数据 —— 这一优点与 map 和 set 相同。 其实，除了内部结构的不同外，其余与 map 和 set 没什么不同，一样的 insert、find、erase … … 在我们模拟过 map set 的基础上，再学习封装 无序map 和 无序set 实在简单。 因此，本文的重点在于迭代器的运行逻辑 —— operator++() ，和理解模板、仿函数等。 最后，补充一个概念： 哈希 是一种思想，将传入的数据映射成一个或多个整型；哈希表 / 哈希桶 则是一种实现哈希思想的结构。 一、改造哈希桶 1.1 初步搭建 HashTable template<class T> struct HashNode { HashNode<T>* _next; T _data; HashNode(const T& data) :_next(nullptr)...