思路：创建一个数组，每个位置只能存储一个值，当插入一个值时，通过一个映射函数映射到该数组上，如果当前映射到的位置有值存在，就再以某种函数放到其余位置。每个位置的状态有三种，存在，删除和为空，以此方便我们查找和删除。
开放地址法实现的哈希表极容易出现哈希冲突的情况，因此我们可以通过闭散列实现哈希表来降低哈希冲突。
闭散列思路：仍是一个数组，但是该数组中存储的是一个指针，该指针指向一个链表或一棵树，链表或树中存储的是对应的数据，也就是将原本映射到同一位置的数据，以链表或树的方式组织起来，同时我们把这个指针指向的结构称为桶，也就是哈希桶。
下面我们以闭散列哈希表为底层封装容器unordered_map和unordered_set
数组中存储的是桶节点指针，节点的结构如下
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{
}
};
存储的数据分别是_data数据和指向下一个桶节点的_next指针
哈希表中有两个成员变量分别是存储每个哈希桶节点指针的数组和哈希表中一共存储的数据个数
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{
typedef HashNode<T> Node;
private:
vector<Node*> _table;//指针数组
size_t _n = 0; //存储了多少个数据
};
为什么还要保存哈希表中存储的数据个数？
如果存储的数据个数过多，而数组的长度较小就会导致哈希表负载因子过高，当负载因子大于某一个值时，就需要我们对这个数组进行扩容，因此_n的作用是方便我们计算负载因子，从而判断是否需要扩容。
通过该仿函数将不同类型的key值都转换成整型，方便我们通过映射函数映射到哈希表的某一个哈希桶
template<class K>
struct DefaultHashFunc//此函数作用是什么 通过仿函数将key变成整型，从而可以进行取余，建立映射关系
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct DefaultHashFunc<string>//特化，指定接受的参数类型为string
{
size_t operator()(const string& str)
{
return str[0];
}
};
对于string类型我们这里以取第一个字符转化为整型为例，你也可以取前n个字符并以某种的运算确定该类型的映射值
struct KeyOfMap
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
struct KeyOfSet
{
const K& operator()(const K& key)
{
return key;
}
};
通过key值来查找当前值是否存在，思路：先判断出当前key值可能位于哪一个桶，然后再在桶中逐个查找数据，如果找到了返回当前节点的迭代器，如果没找到则返回迭代器end(）
但是当前有两个问题：
1.传过来的key值类型我们是不确定的，他可能不是整型不能放到映射函数中进行运算，因此我们需要一个函数将这个key值转换成整型，然后再通过函数映射到哈希表的某一个桶，再在这个同种查找该数据是否存在
2.对于unordered_map和unordered_set分别存储的是键值对和键值，因此我们需要把他们中的key值取出来，然后才能与要查找的key值判断是否相等，因此可以选择在unordered_map和unordered_set第一层封装那里，分别设计对应的仿函数，用于取出这两个容器的key值。
iterator Find(const K& key)
{
HashFunc hf;
KeyOfT kot;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while(cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur, this);
}
cur = cur->_next;
}
return end();
}
数据的插入思路:
1.先判断当前值在哈希表中是否存在，如果存在就不用再插入了，并返回一个键值对，键值对中first存储指向该节点的迭代器，second为bool值false
2.其次判断该哈希表是否需要扩容，我们定义当负载因子值为1时就进行扩容，也就是_table.size() == _n就扩容
3.最后再插入
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot;
//如果已存在就返回false
iterator it = Find(kot(data));
if (it != end())
{
return make_pair(it, false);
}
HashFunc hf;
size_t hashi = hf(kot(data)) / _table.size();
//扩容
if (_table.size() == _n)
{
size_t newsize = _table.size() * 2;
vector<Node*> newtable;
newtable.resize(newsize);
//把原容器中的数据重新插入到新容器中
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
hashi = hf(kot(cur->_data)) % newtable.size();
cur->_next = newtable[hashi];
newtable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;//将原表置空
}
newtable.swap(_table);
}
//插入
hashi = hf(kot(data)) % _table.size();
Node* newnode = new Node(data);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
_n++;
return make_pair(iterator(newnode, this), true);
}
对于以往的容器，我们在实现迭代器时，它的构造函数只需要传过来一个节点指针过来即可，但是对于unordered_map和unordered_set，我们选择把哈希表指针也传过来，为什么？
因为我们在实现++操作时，不仅要去访问当前节点所在桶中的下一个节点，还可能要去访问下一个桶中的节点，因此我们把整个哈希表都传过来，以利于我们实现++操作。
两种情况
1.该节点的_next指针不为空
2.该节点的_next指针为空，就需要我们再去访问下一个桶了
为什么要在迭代器中实现一个构造函数只传Iterator的构造函数？
因为我们在第一层封装时Insert的返回值是一个普通迭代器，但是unordered_set中的迭代器都是const的，我们要返回的迭代器也需要是const的，因此我们设计出一个构造函数将普通迭代器构造**出一个const迭代器。不写这个构造函数不行吗？不是可以由普通迭代器通过权限缩小成const迭代器吗？**要注意一个误区这里的迭代器是类型定义为
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
HTIterator是一个整体，这是两个不同的类型，没有权限放大与缩小这一说，不要把概念混淆了
template <class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
typedef const HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;
Node* _node;
const HashTable<K, T, KeyOfT, HashFunc>* _pht;
//HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)//把哈希表指针也传过来，便于我们使用
// :_node(node)
// , _pht(pht)
//{
//}
HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht)
:_node(node)
, _pht(pht)
{
}
HTIterator(const Iterator& it)
:_node(it._node)
, _pht(it._pht)
{
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else//当前桶结束，找下一个节点不为空的桶
{
HashFunc hf;
KeyOfT kot;
size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
++hashi;
while (hashi < _pht->_table.size())
{
if (_pht->_table[hashi])
{
_node = _pht->_table[hashi];
return *this;
}
++hashi;
}
_node = nullptr;
}
return *this;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
因为我们不仅要在哈希表类中访问迭代器，还要在迭代器中访问哈希表类对象，这就会导致哪个类放在前面会报错，因为程序编译是自上而下进行查找的，因此我们要把放在后面的类在另一个类之前进行类声明，表明这个类是存在的
//前置声明
template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>> class HashTable;
因为迭代器要访问哈希表类private私密成员指针数组和_n，因此我们选择把迭代器类声明为哈希表类的友元类
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{
//友元声明,要加上模版
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc> friend struct HTIterator;
}
哈希表类中定义普通迭代器和const 迭代器
typedef HashNode<T> Node;
public:
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
HashTable()
{
_table.resize(10);
}
iterator begin()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
{
return iterator(cur, this);
}
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
const_iterator begin() const
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
{
return const_iterator(cur, this);
}
}
return const_iterator(nullptr, this);
}
const_iterator end() const
{
return const_iterator(nullptr, this);
}
#pragma once
#include "HashTable.h"
namespace sw
{
template <class K, class V>
class UnorderedMap
{
struct KeyOfMap
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
//为什么要加typename？
typedef typename sw::HashTable<K, pair<const K, V>, KeyOfMap>::iterator iterator;
typedef typename sw::HashTable<K, pair<const K, V>, KeyOfMap>::const_iterator const_iterator;
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return hash_bucket.Insert(kv);
}
bool erase(const K& key)
{
return hash_bucket.Erase(key);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = hash_bucket.Insert(make_pair(key, V()));
return ret.first->second;//等价于(*ret.first).second;
}
iterator begin()
{
return hash_bucket.begin();
}
iterator end()
{
return hash_bucket.end();
}
const_iterator begin() const
{
return hash_bucket.begin();
}
const_iterator end() const
{
return hash_bucket.end();
}
private:
HashTable<K, pair<const K, V>, KeyOfMap> hash_bucket;
};
}
#pragma once
#include "HashTable.h"
namespace sw
{
template <class K>
class UnorderedSet
{
struct KeyOfSet
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename sw::HashTable<K, K, KeyOfSet>::const_iterator iterator;
typedef typename sw::HashTable<K, K, KeyOfSet>::const_iterator const_iterator;
pair<iterator, bool> insert(const K& key)
{
return hash_bucket.Insert(key);
}
bool erase(const K& key)
{
return hash_bucket.Erase(key);
}
iterator begin()
{
return hash_bucket.begin();
}
iterator end()
{
return hash_bucket.end();
}
const_iterator begin()const
{
return hash_bucket.begin();
}
const_iterator end()const
{
return hash_bucket.end();
}
private:
HashTable<K, K, KeyOfSet> hash_bucket;
};
}
template <class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
typedef const HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;
Node* _node;
const HashTable<K, T, KeyOfT, HashFunc>* _pht;
//HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)//把哈希表指针也传过来，便于我们使用9.18 18:52
// :_node(node)
// , _pht(pht)
//{
//}
HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht)
:_node(node)
, _pht(pht)
{
}
HTIterator(const Iterator& it)
:_node(it._node)
, _pht(it._pht)
{
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else//当前桶结束，找下一个节点不为空的桶
{
HashFunc hf;
KeyOfT kot;
size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
++hashi;
while (hashi < _pht->_table.size())
{
if (_pht->_table[hashi])
{
_node = _pht->_table[hashi];
return *this;
}
++hashi;
}
_node = nullptr;
}
return *this;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
friend struct HTIterator;
typedef HashNode<T> Node;
//友元声明,要加上模版
public:
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
HashTable()
{
_table.resize(10);
}
iterator begin()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
{
return iterator(cur, this);
}
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
const_iterator begin() const
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
{
return const_iterator(cur, this);
}
}
return const_iterator(nullptr, this);
}
const_iterator end() const
{
return const_iterator(nullptr, this);
}
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot;
//如果已存在就返回false
iterator it = Find(kot(data));
if (it != end())
{
return make_pair(it, false);
}
HashFunc hf;
size_t hashi = hf(kot(data)) / _table.size();
//扩容
if (_table.size() == _n)
{
size_t newsize = _table.size() * 2;
vector<Node*> newtable;
newtable.resize(newsize);
//把原容器中的数据重新插入到新容器中
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
hashi = hf(kot(cur->_data)) % newtable.size();
cur->_next = newtable[hashi];
newtable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;//将原表置空
}
newtable.swap(_table);
}
//插入
hashi = hf(kot(data)) % _table.size();
Node* newnode = new Node(data);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
_n++;
return make_pair(iterator(newnode, this), true);
}
iterator Find(const K& key)
{
HashFunc hf;
KeyOfT kot;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while(cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur, this);
}
cur = cur->_next;
}
return end();
}
bool Erase(const K& key)
{
HashFunc hf;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
//当存在时，分两种情况
//1.key节点在当前桶的第一个位置，_table[hashi]就指向key节点2.key节点在当前桶的后面位置
KeyOfT kot;
if (kot(cur->_data) == key)
{
_table[hashi] = cur->_next;
delete cur;
--_n;
return true;
}
else
{
Node* prev = cur;
while (cur)
{
if (kot(cur->_data) == key)
{
prev->_next = cur->_next;
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
vector<Node*> _table;//指针数组
size_t _n = 0; //存储了多少个数据
};
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 HashFunc = DefaultHashFunc<K>> class HashTable;
template<class K>
struct DefaultHashFunc//此函数作用是什么9.16 11:26 通过仿函数将key变成整型，从而可以进行取余，建立映射关系
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct DefaultHashFunc<string>//特化，指定接受的参数类型为string
{
size_t operator()(const string& str)
{
return str[0];
}
};
哈希表封装unordered_map和unordered_set具体步骤
一、哈希表类
1.定义桶节点，桶节点中包含存储的值和指向下一个桶节点的指针
2.定义哈希表类，类中成员变量分别为一个数组，数组中的值指向一个桶的节点指针
3.各类成员函数实现，通过两个DefaultHashFunc函数来获取key值所对应的整型值
二、迭代器
1.迭代器类需要两个成员变量分别为哈希表指针和桶节点指针
2.实现迭代器的++，==和!=,指针,引用等操作
3.实现一个构造函数，把普通迭代器转换成const迭代器，如果传过来的是普通迭代器那么这个构造函数就为构造函数，如果传过来的是const迭代器那么这个函数就为拷贝构造
4.哈希表类中typedef迭代器，分别为const迭代器和普通迭代器
三、封装unordered_map和unordered_set
1.类中成员变量都为哈希表，当上层调用unordered_map和unordered_set类成员函数时，我们都通过该成员去调用底层哈希表类所对应的函数
2.unordered_set中的key不允许被修改，因此我们把它的迭代器都定义为const迭代器即可
3.对于unordered_map而言它的key也不允许被修改，但是value可以被修改，因此我们就不能让它像unordered_set一样将迭代器都定义为const的，而是它该封装类中的成员变量中的K声明为const的 HashTable<K, pair<const K, V>, KeyOfMap> hash_bucket;
4.在这两个类中分别实现仿函数，用于返回该类的key值
文章浏览阅读3.6k次，点赞2次，收藏2次。DELL7080台式机两块硬盘。_没有u盘怎么装ubuntu
文章浏览阅读32次。题面Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K asteroids (1 <= K <= 10,000), which are conv...
文章浏览阅读2.6w次，点赞21次，收藏112次。机器视觉则主要是指工业领域视觉的应用研究，例如自主机器人的视觉，用于检测和测量的视觉系统等。它通过在工业领域将图像感知、图像处理、控制理论与软件、硬件紧密结合，并研究解决图像处理和计算机视觉理论在实际应用过程中的问题，以实现高效的运动控制或各种实时操作。_工业机器视觉系统的构成与开发过程(理论篇—1
文章浏览阅读5.9w次，点赞32次，收藏58次。legend 传奇、图例。plt.legend()的作用：在plt.plot() 定义后plt.legend() 会显示该 label 的内容，否则会报error: No handles with labels found to put in legend.plt.plot(result_price, color = 'red', label = 'Training Loss') legend作用位置：下图红圈处。..._plt.legend
文章浏览阅读2.2k次，点赞3次，收藏11次。深入理解 C# .NET Core 中 async await 异步编程思想引言一、什么是异步？1.1 简单实例（WatchTV并行CookCoffee）二、深入理解（异步）2.1 当我需要异步返回值时，怎么处理？2.2 充分利用异步并行的高效性async await的秘密引言很久没来CSDN了，快小半年了一直在闲置，也写不出一些带有思想和深度的文章；之前就写过一篇关于async await 的异步理解 ，现在回顾，真的不要太浅和太陋，让人不忍直视！好了，废话不再啰嗦，直入主题：一、什么是异步？_netcore async await
文章浏览阅读6.5w次，点赞166次，收藏309次。当我看到别人的类上面的多行注释是是这样的：这样的：这样的：好装X啊！我也想要！怎么办呢？往下瞅：跟着我左手右手一个慢动作~~~File--->Settings---->Editor---->File and Code Templates --->Includes--->File Header:之后点applay--..._idea作者和日期等注释
文章浏览阅读175次。Netperf是一种网络性能的测量工具，主要针对基于TCP或UDP的传输。Netperf根据应用的不同，可以进行不同模式的网络性能测试，即批量数据传输（bulk data transfer）模式和请求/应答（request/reponse）模式。工作原理Netperf工具以client/server方式工作。server端是netserver,用来侦听来自client端的连接,c..._netperf 麒麟
文章浏览阅读1.1k次，点赞2次，收藏3次。作者| qcrao责编 | 屠敏出品 | 程序员宅基地刚开始写这篇文章的时候，目标非常大，想要探索 Go 程序的一生：编码、编译、汇编、链接、运行、退出。它的每一步具体如何进行，力图弄清 Go 程序的这一生。在这个过程中，我又复习了一遍《程序员的自我修养》。这是一本讲编译、链接的书，非常详细，值得一看！数年前，我第一次看到这本书的书名，就非常喜欢。因为它模仿了周星驰喜剧..._go run 每次都要编译吗
文章浏览阅读1.4k次，点赞4次，收藏2次。0、C++的输入输出分为三种：(1)基于控制台的I/O (2)基于文件的I/O (3)基于字符串的I/O 1、头文件[cpp] view plaincopyprint?#include 2、作用istringstream类用于执行C++风格的字符串流的输入操作。 ostringstream类用_c++ istringstream a >> string
文章浏览阅读2k次，点赞3次，收藏14次。我们在每个修改的地方都记录一条对应的 redo 日志显然是不现实的，因此实现方式是用时间换空间，我们在数据库崩了之后用日志还原数据时，在执行这条日志之前，数据库应该是一个一致性状态，我们用对应的参数，执行固定的步骤，修改对应的数据。1，MySQL 就是通过 undolog 回滚日志来保证事务原子性的，在异常发生时，对已经执行的操作进行回滚，回滚日志会先于数据持久化到磁盘上（因为它记录的数据比较少，所以持久化的速度快），当用户再次启动数据库的时候，数据库能够通过查询回滚日志来回滚将之前未完成的事务。_binglog
文章浏览阅读3k次。概述之前介绍过 移动Web开发基础-flex弹性布局（兼容写法） 里面有提到过想做一个Chrome插件，来生成flexbox布局的css代码直接拷贝出来用。最近把这个想法实现了，给大家分享下。play-flexbox插件介绍play-flexbox一秒搞定flexbox布局，可直接预览效果，拷贝CSS代码快速用于页面重构。 你也可以通过点击以下链接（codepen示例）查_chrome css布局插件
文章浏览阅读308次。我自己的配置是GeForce GTX 1660 +CUDA10.0+CUDNN7.6.0 + TensorFlow-GPU 1.14.0Win10系统安装tensorflow-gpu（按照步骤一次成功）https://blog.csdn.net/zqxdsy/article/details/103152190环境配置——win10下TensorFlow-GPU安装（GTX1660 SUPER+CUDA10+CUDNN7.4）https://blog.csdn.net/jiDxiaohuo/arti