坪山公司网站建设,版面设计网站有哪些,天津企业网站专业订制,郑州网站优化外包目录
前言
一、哈希
1、哈希的概念
2、哈希函数
#xff08;1#xff09;直接定址法
#xff08;2#xff09;除留余数法
#xff08;3#xff09;平方取中法#xff08;了解#xff09;
#xff08;4#xff09;随机数法#xff08;了解#xff09;
3、哈…目录
前言
一、哈希
1、哈希的概念
2、哈希函数
1直接定址法
2除留余数法
3平方取中法了解
4随机数法了解
3、哈希冲突
4、闭散列及其实现
1闭散列的查找
2闭散列的插入
3闭散列的删除
5、开散列及其实现
1开散列的查找
2开散列的插入
3开散列的删除
4其他函数
6、开散列与闭散列的一些其他问题
1对于自定义类型成员无法确定位置
2模素数优化
二、unordered_set与unordered_map的封装 前言 前面我们学习了unordered_set、unordered_map的使用这里我们从底层来看看这两个容器并对其封装再封装之前我们需要清楚者两个容器的底层是哈希结构我们首先自己实现一个哈希表再拿这个哈希表对容器进行封装 一、哈希
1、哈希的概念 前面的二叉搜索树我们想找到一个值就必须对这个值从根节点开始依次比较知道找到这个数或者找到空姐点指针但是我们想通过一种一 一映射的思想以最快的速度找到我们想要的值这种将我们的关键码与位置建立关系的思想我们称之为哈希举个例子 题目链接 如上述这道题目我们想要找出只出现一个只出现一次的字符我们怎么处理呢我们之前可通过类似计数排序的思想将每个字母映射一个数字下标的位置题目有说只会出现小写字母如我们创建一个大小为26的数组并都初始化为0a映射到数组0下标的位置b映射到数组1下标的位置这样依次映射我们可以映射到下标25z的位置然后遍历字符串每遇到一个字符就将该字符对应的下标的数组值1如遇到a我们将0下标对应的数组值1这样的思想也就是我们哈希的思想 2、哈希函数 哈希函数就是将我们关键码转化成对应的哈希值上述题目中将小写字母转换成0到26这一过程我们就可以理解成我们用哈希函数将小写字母转换成特定的哈希值接下来我们来看看了解一下常见的哈希函数 1直接定址法 所谓直接定址法就是去关键码作为哈希地址如来了一个3我们就将3放进数组下标为3的位置来了一个13就将13放进数组13的位置 但是这种方法有一个明显的缺陷我们要是我们的数据并不是集中分布的呢假如有三个数据分别为3510007那么我们是不是要开辟10007这么大的空间存放数据呢因此我们不使用这种方法 2除留余数法 我们在得到一个关键码时我们将它余上某个数字得到储存位置这种方法就是我们的除留余数法我们后面实现哈希表就是采用这种方法例如还是上述三个数据3510007 我们将上述的值依次余上一个10得到的余数就是对应的位置后面还有一个写方法我们了解即可 3平方取中法了解 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址 再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址 4随机数法了解 选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key),其中random为随机数函数。 当然还有很多很多的方法大家感兴趣可以自行搜索 3、哈希冲突 在上述不同方法中仍然会出现一些特殊状况其中有一种被称为哈希冲突如下图所示 上图采取的是除留取余法目前数据存储并没有什么问题但是接下来当我们想存入一个13这是我们对其取10的余数即为3但是此时我们3的位置已经存储了一个数据了那这时我们应该怎么存储这个数据呢这种存储数据位置冲突的现象就是我们的哈希冲突那么如何解决这种哈希冲突呢没错就是我们接下来的闭散列和开散列两种方法 4、闭散列及其实现 闭散列也叫开放定址法当发生哈希冲突的时候我们将当前数据存储到“下一个”位置存储关于这下一个位置我们有几种不同的定义可以是1的位置也可以每次都加不同的数主要看实现者想如何实现以下我们依次分析 首先我们分析一下我们想实现我们的闭散列有哪些困难 1、我们开辟一块空间后当来了一个关键码以后我们通过特定的算法函数将这个关键码转换成我们的位置然后我们需要查看数组的这个位置是否存储了数据那我们如何确定这个位置是否存储了数据呢 2、当我们删除一个元素后我们应该如何表明该数据被删除了呢 我们可以将数组中存储一个结构化数据而不是单个数据结构化数据包括我们存储的数据以及数据的状态这里我设置了三种状态分别是EMPT此位置为空EXIST此位置有数据DELETE此位置目前没数据了被删除了 注意这里可能有很多同学看不懂这里为什么要设置DELETE这种状态删除一个数据直接设置成EMPTY不可以吗这里我们需要考虑删除的情况假设如下 此时插入了数据如上图所示我们使用的下一个位置是1我们查找数据的逻辑是先算出位置值我们算出存入hashi中然后我们从hashi位置开始查找如果不是我们要查找的数值我们就找下一个位置知道我们加到的那个位置的值为EMPTY状态为止这时如果我们删除数据的逻辑是将数据对应位置设置为EMPTY就有坑了假设我们删除15此时下标5这个位置被设置成EMPTY然后我们接着想查找12我们从算出hashi值2从2开始查找发现不等于12接着探测下一个位置下标3的值对比还是不相等一直到下标5的位置时我们发现下标5为EMPTY状态停止查找可是我们数据明明存储在这个哈希表中所以两个状态是不够的 根据如上分析我们写出闭散列的大体框架如下所示 namespace ClosedHash
{// 状态表示enum State{EMPTY,EXIST,DELETE};// 哈希表中数据存储类型templateclass K, class Vstruct HashDate{std::pairK, V _kv;State _state EMPTY;};// 哈希表templateclass K, class Vclass HashTable{public:private:std::vectorHashDateK, V _hash_table;size_t _n 0; // 哈希表中元素个数};
}
1闭散列的查找 闭散列的查找需要先算出hashi这里是余上这个vector的size这里采用的是一次探测即不断1 HashDateK, V* find(const K key){if (_n 0){return nullptr;}size_t hashi key % _hash_table.size();size_t i 1;size_t index hashi;// 若查找位置不为空继续往后找while (_hash_table[index]._state ! EMPTY){if (_hash_table[index]._state EXIST _hash_table[index]._kv.first key){return _hash_table[index];}else{// 下一个探测index hashi i;index % _hash_table.size();i;}// 防止都是DELETE状态造成死循环if (index hashi)break;}return nullptr;}
2闭散列的插入 插入的代码中关于哈希碰撞时我们可以选择一次探测也可以选择二次探测这里插入时需要考虑扩容问题这里涉及到什么时候扩容关于什么时候扩容我们这里引入了负载因子这一概念 负载因子 元素个数 / size 所以这里需要控制除零错误第一次进去必须扩容还有我们这的负载因子一般控制在0.7到0.8左右大了就哈希碰撞的几率大空间利用率高搜索效率低小了就哈希碰撞几率低空降利用率低搜索效率高 bool insert(const std::pairK, V kv){if (find(kv.first))return false;// 是否需要扩容if (_hash_table.size() 0 || _n * 10 / _hash_table.size() 7){int newsize _hash_table.size() 0 ? 10 : _hash_table.size() * 2;HashTableK, V tmp;tmp._hash_table.resize(newsize);for (auto e : _hash_table){tmp.insert(e._kv);}_hash_table.swap(tmp._hash_table);}size_t hashi kv.first % _hash_table.size();size_t i 1;size_t index hashi;// 若插入位置发生冲突则继续探测while (_hash_table[index]._state EXIST){// 一次探测index hashi i;// 二次探测//index hashi i * i;i;index % _hash_table.size();}_hash_table[index]._kv kv;_hash_table[index]._state EXIST;_n;return true;}
3闭散列的删除 bool erase(const K key){auto pos find(key);if (pos nullptr)return false;pos-_state DELETE;_n--;return false;}
5、开散列及其实现 开散列又叫链地址法开链法当我们得到一个关键码时我们将这个关键码求出对应的地址我们称对应地址所在位置为一个哈希桶我们将这个数据以链表的形式挂在对应的哈希桶下面如下图所示 不难看出每个哈希桶下面挂着发生哈希冲突的值实际上我们的unordered_set与unordered_map同样也是使用开散列的哈希桶进行封装我们根据上述同样也可以实现出开散列类的基本结构如下所示 namespace OpenHash
{templateclass K, class Vstruct HashNode{typedef HashNodeK, V Node;HashNode(const std::pairK, V kv):_kv(kv),_next(nullptr){}std::pairK, V _kv;Node* _next nullptr;};templateclass K, class Vclass HashBucket{public:typedef HashNodeK, V Node;private:std::vectorNode* _hash_table;size_t _n 0; // 存储的元素个数};
}
1开散列的查找 查找并无难度我们仅仅只需要算出对应的hashi然后在对应桶下面的单链表中查找即可 Node* find(const K key){if (_hash_table.size() 0)return nullptr;size_t hashi key % _hash_table.size();Node* cur _hash_table[hashi];while (cur){if (cur-_kv.first key)return cur;cur cur-_next;}return nullptr;}
2开散列的插入 开散列同样也要考虑扩容问题开散列的负载因子我们可以略微增加因为开散列的哈希碰撞几率明显降低了这里我们把负载因子设置为了1 bool insert(const std::pairK, V kv){// 扩容if (_hash_table.size() 0 || _n * 10 / _hash_table.size() 10){int newsize _hash_table.size() 0 ? 10 : _hash_table.size() * 2;HashBucketK, V tmp;tmp._hash_table.resize(newsize, nullptr);for (auto cur : _hash_table){// 将该链表下所有结点放入新表中while (cur){Node* next cur-_next;size_t hashi cur-_kv.first % tmp._hash_table.size();// 头插入新表中cur-_next tmp._hash_table[hashi];tmp._hash_table[hashi] cur;cur next;}}_hash_table.swap(tmp._hash_table);}// 插入size_t hashi kv.first % _hash_table.size();Node* newnode new Node(kv);if (_hash_table[hashi] nullptr){_hash_table[hashi] newnode;}else{// 头插newnode-_next _hash_table[hashi];_hash_table[hashi] newnode;}_n;return true;}
3开散列的删除 这里需要注意头删的特殊处理 bool erase(const K key){Node* pos find(key);if (pos nullptr)return false;size_t hashi key % _hash_table.size();Node* prev nullptr;Node* cur _hash_table[hashi];while (cur){if (cur-_kv.first key){// 头删if (prev nullptr){_hash_table[hashi] cur-_next;}else // 中间尾部删除{prev-_next cur-_next;}delete cur;return true;}else{prev cur;cur cur-_next;}}return false;}
4其他函数 这里需要实现拷贝构造因为vector里存的成员是链表对于链表我们要进行深拷贝不然会内存泄露 // 默认构造HashBucket():_n(0){}// 拷贝构造HashBucket(const HashBucketK, V hb){// 深拷贝if (this ! hb){_hash_table.resize(hb._hash_table.size(), nullptr);for (size_t i 0; i hb._hash_table.size(); i){Node* cur hb._hash_table[i];Node* copytail nullptr;while (cur){Node* newnode new Node(cur-_kv);if (_hash_table[i] nullptr){_hash_table[i] newnode;copytail newnode;}else{copytail-_next newnode;copytail copytail-_next;}cur cur-_next;}}}}// 赋值重载(现代写法)HashBucketK, V operator(HashBucketK, V hb){_hash_table.swap(hb._hash_table);std::swap(_n, hb._n);return *this;}// 析构函数~HashBucket(){clear();}size_t size(){return _n;}void clear(){for (size_t i 0; i _hash_table.size(); i){Node* cur _hash_table[i];while (cur){Node* del cur;cur cur-_next;delete del;}_hash_table[i] nullptr;}}
6、开散列与闭散列的一些其他问题
1对于自定义类型成员无法确定位置 前面不管是开散列还是闭散列我们在求取hashi的时候我们都是直接求余数的假如我们的key是string类型呢那不就都会报错吗所以此时我们必须多提供一个模板参数也就是我们unordered_set/unordered_map第三个模板参数Hash这个参数就是我们可以传入一个仿函数控制如何将key转换成size_t类型 // 增加后的模板列表templateclass K, class V, class HashFunc HashKclass HashBucket//增加的默认Hash函数templateclass Kstruct Hash{size_t operator()(const K key){return key;}};// 特化templatestruct Hashstd::string{// BKDRHashsize_t operator()(const std::string s1){size_t hash 0;for (auto ch : s1){hash hash * 31 ch;}return hash;}}; 关于字符串哈希算法下面有一篇博客进行了详细介绍上述代码就是采用其中之一的BKDRHash 字符串哈希函数 2模素数优化 经过研究发现除留余数法最好模上一个素数这样哈希冲突的概率比较低因此我们可以在每次扩容时我们取比当前容量大两倍的一个素数因此有了以下代码 size_t GetNextPrime(size_t prime){const int PRIMECOUNT 28;static const size_t primeList[PRIMECOUNT] {53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul,25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul,805306457ul,1610612741ul, 3221225473ul, 4294967291ul};size_t i 0;for (; i PRIMECOUNT; i){if (primeList[i] prime)return primeList[i];}return primeList[i];} 我们每次扩容直接调用这个函数即可拿到扩容的大小 二、unordered_set与unordered_map的封装 这两个容器的封装与我们map、set封装差不多我们修改一下我们之前写的哈希表然后进行封装即可代码提交至gitee中有兴趣的可以查看 容器封装代码
