虚拟主机与网站建设,网络营销七个步骤,哪个网站找到做箱包厂外发的,在线购物网站每一个不曾起舞的日子都是对生命的辜负 哈希一.哈希概念及性质1.1 哈希概念1.2 哈希冲突1.3 哈希函数二.哈希冲突解决2.1 闭散列/开放定址法2.2 开散列/哈希桶三.开放定址法代码3.1 插入Insert3.2 查找Find3.3 删除Erase3.4 映射的改良完整代码四.开散列代码4.1 插入Inser… 每一个不曾起舞的日子都是对生命的辜负 哈希一.哈希概念及性质1.1 哈希概念1.2 哈希冲突1.3 哈希函数二.哈希冲突解决2.1 闭散列/开放定址法2.2 开散列/哈希桶三.开放定址法代码3.1 插入Insert3.2 查找Find3.3 删除Erase3.4 映射的改良完整代码四.开散列代码4.1 插入Insert4.2 查找Find4.3 删除Erase4.4 完整代码统计水果次数五.扩容机制一.哈希概念及性质
1.1 哈希概念
顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O(log2Nlog_2 Nlog2N)搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。
当向该结构中 插入元素 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放 搜索元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功
该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash Table)(或者称散列表) 例如数据集合{176459}
哈希函数设置为hash(key) key % capacity; capacity为存储元素底层空间总的大小。 用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快 问题按照上述哈希方式向集合中插入元素44会出现什么问题
1.2 哈希冲突
对于两个数据元素的关键字kik_iki和 kjk_jkj(i ! j)有kik_iki ! kjk_jkj但有Hash(kik_iki) Hash(kjk_jkj)即不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。 发生哈希冲突该如何处理呢 1.3 哈希函数
引起哈希冲突的一个原因可能是哈希函数设计不够合理。
哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单
常见哈希函数
1. 直接定址法–常用
取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况
一旦出现类似于这种数组[1,2,3,100,10000]此时就会浪费很多比毕业的空间因此一旦出现这种情况我们采用下面这种方法
2. 除留余数法–(常用)
设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址。
因此对于上面的数组来说我们就可以采用%10的方式将其固定在一定大小的范围之内从而降低空间上的浪费。但此时就会发生上面所说的哈希冲突即对于10010000这两个数字%10之后都是0因此一旦先将100放在了0的位置那么10000就会发生哈希冲突。
二.哈希冲突解决
解决哈希冲突两种常见的方法是闭散列和开散列
2.1 闭散列/开放定址法 闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢 1. 线性探测
比如1.1中的场景现在需要插入元素44先通过哈希函数计算哈希地址hashAddr为4因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。
线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。
插入 通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素 删除 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索。比如删除元素4如果直接删除掉44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。即我们可以采用标记的方式将没有插入过的地方标记为EMPTY存在数据的地方标记位EXIST。 查找 那如果想要具体查找某一个元素就可以从指定映射的地方直接找我们知道解决哈希冲突时会往后插入因此我们会继续往后找如果找了一圈没有找到那一定有一个位置代表终止位置即EMPTY的位置但是如果将之前的元素删除并标记EMPTY的话那这个位置之后实际上还有数据可以查找这样也就不能用这个表示终止位置了为了能够满足终止位置我们再设定一个状态将存在的数据并删除的位置标记位DELETE这样就可以通过EMPTY来终止查找了。 接下来直接看三.开放定址法代码中的代码实现- 线性探测优点实现非常简单。 线性探测缺点**一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降低。**如何缓解呢 2.二次探测
线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为HiH_iHi (H0H_0H0 i2i^2i2 )% m, 或者HiH_iHi (H0H_0H0 - i2i^2i2 )% m。其中i 1,2,3… H0H_0H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置m是表的大小。 对于1.1中如果要插入44产生冲突使用解决后的情况为 研究表明当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表装满的情况但在插入时必须确保表的装载因子a不超过0.5如果超出必须考虑增容。
因此闭散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷。
为了让映射的元素不互相影响开散列/哈希桶的方式也就与此诞生
2.2 开散列/哈希桶
1. 开散列概念
开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 数组为指针数组 从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素。C库中就是用的这种方式。 指针数组也需要一定的扩容不然空间为10而有1000个数据每个桶就需要挂100个数据事实上比单链表好不了多少。所以在扩容时同样需要负载因子不过对于演示来说负载因子控制在1就好了。相比开放地址法哈希桶的方式能让负载因子上升到很高的比例。 三.开放定址法代码
将除成员函数之外封装放在这里这样设计是为了更具观赏性。
HashTable.h
enum State
{EMPTY,EXIST,DELETE,
};templateclass K, class V
struct HashData
{pairK, V _kv;State _state EMPTY;//默认给一个缺省值
};templateclass K, class V
class HaskTable
{typedef HashDataK, V Data;
public://插入、查找、删除功能
private:vectorData _tables;size_t _n;//表中存储的有效数据的个数
};直接使用vector会更加便捷这也是一种很好的手段。
3.1 插入Insert
对于插入来说将采用线性探测法即如果发生冲突就往后遍历找到空的位置那此时同样会发生一个问题如果空间不够了需要扩容对于哈希来说并不能等到空间满了才扩容一旦到达某个程度就会因哈希冲突的不断发生造成效率的低下此时为了解决这种问题就有了负载因子/载荷因子即 负载因子 表中有效数据的个数/表的大小。
负载因子越小冲突概率越小消耗空间越多。负载因子越大冲突概率越大空间的利用率越高。
可以看出负载因子的出现正是以空间换时间的做法。一般将负载因子控制在0.7左右的样子超过了这个值就需要扩容了。 对于扩容的过程实际上随着空间大小的改变取模%的大小也发生变化这就造成数据原表的的位置可能与新表的位置寅映射关系的改变而变得不一样事实上这并非是坏事或许还会一定程度的减少哈希冲突。
因此一般的写法就是在写出一个 vectorData newTable然后重复下面的逻辑但是有一个更好的现代写法重新定义一个类的对象也就是新的哈希表将旧值通过类的方法重新Insert到新表中最后这两个表的值进行交换这样就不用重复写冲突的逻辑了。 注意是新对象调用的Insert和递归无关。 当然一开始会出现除0错误通过在内部重新写构造函数直接resize()一个非0的数就可以避免这个问题了。
那看看类中Insert的代码吧结点之类的代码没有写以免代码看起来太多在代码案例开始已经写过。
templateclass K, class V
class HashTable
{typedef HashDataK, V Data;
public:HashTable():_n(0){_tables.resize(10);}bool Insert(const pairK, V kv){//大于标定负载因子就需要扩容if (_n * 10 / _tables.size() 7)//这样处理了小数为0{旧表数据重新计算映射到新表//vectorData newTable;//newTable.resize(_tables.size() * 2);//for()//现代写法HashTableK, V newHT;newHT._tables.resize(_tables.size() * 2);for (auto e : _tables){newHT.Insert(e._kv);}_tables.swap(newHT._tables);}//因为需要满足vector的operator[]因此%size而不是capacitysize_t hashi kv.first % _tables.size();while (_tables[hashi]._state EXIST){//线性探测hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;//如果发现插入的值重复就应该返回false但由于这里还没有讲解find函数因此直接返回true也没什么问题后续将会有完整代码return true;}private:vectorData _tables;size_t _n 0;//表中存储的有效数据的个数
};测试一下
void TestHT1()
{HashTableint, int ht;int a[] { 18, 8, 7, 27, 57, 3, 38 };for (auto e : a){ht.Insert(make_pair(e, e));}
}3.2 查找Find
Data* Find(const K key)
{size_t hashi key % _tables.size();while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key){return _tables[hashi];}hashi;hashi % _tables.size();}return nullptr;
}返回类型为Data*可以更好的删除下面看看为什么
3.3 删除Erase
bool Erase(const K key)
{Data* ret Find(key);if (ret){ret-_state DELETE;--_n;return true;}return false;
}可以发现通过Find的返回值就可以将删除数据的_state变为DELETE事实上这是一种伪删除的方式不过用的恰到好处。
3.4 映射的改良完整代码
仍然拿出统计水果出现的次数为背景引出问题
void TestHT2()
{string arr[] { 苹果, 西瓜, 香蕉, 苹果, 西瓜 , 苹果, 苹果,西瓜,苹果,香蕉, 苹果,香蕉 };HashTablestring, int countHT;for (auto e : arr){HashDatastring, int* ret countHT.Find(e);if (ret){ret-_kv.second;}else{countHT.Insert(make_pair(e, 1));}}}对于这段代码来说看不出有什么问题那试着编译一下
可以发现我们之前解决哈希冲突的方式为线性探测中的除留余数法这种方式无法对字符串进行取模因此出现错误。那字符串转整形怎么转并且还是汉字汉字实际上就是由多个字母构成的。
解决方式-仿函数
通过仿函数的方式就可以将类型在映射时将string类型成功转换。在所有取模的地方都加上仿函数对象就可以通过我们自定义的映射方式解决即
enum State
{EMPTY,EXIST,DELETE,
};//仿函数解决s映射问题完全没有关联的类型不能随便转这个不能string转整形因此还需要写一个
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};//这个是针对string类型的仿函数
//特化
template
struct HashFuncstring
{size_t operator()(const string key){//BKDRsize_t hash 0;for (auto ch : key){hash * 131;hash ch;}return hash;//这样映射不易产生哈希冲突}
};templateclass K, class V
struct HashData
{pairK, V _kv;State _state EMPTY;//默认给一个缺省值
};templateclass K, class V, class Hash HashFuncK
class HashTable
{typedef HashDataK, V Data;
public:HashTable():_n(0){_tables.resize(10);}bool Insert(const pairK, V kv){if (Find(kv.first))//已经有了就不需要插入了{return false;}//大于标定负载因子就需要扩容if (_n * 10 / _tables.size() 7)//这样处理了小数为0{旧表数据重新计算映射到新表//vectorData newTable;//newTable.resize(_tables.size() * 2);//for()//现代写法HashTableK, V, Hash newHT;//定义对象多了一个仿函数参数newHT._tables.resize(_tables.size() * 2);for (auto e : _tables){newHT.Insert(e._kv);}_tables.swap(newHT._tables);}Hash hf;//取模的地方用定义的仿函数对象封装解决size_t hashi hf(kv.first) % _tables.size();//因为需要满足vector的operator[]因此%size而不是capacitywhile (_tables[hashi]._state EXIST){//线性探测hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}Data* Find(const K key){Hash hf;//仿函数把key转化成可以取模的整形size_t hashi hf(key) % _tables.size();while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key){return _tables[hashi];}hashi;hashi % _tables.size();}return nullptr;}bool Erase(const K key){Data* ret Find(key);if (ret){ret-_state DELETE;--_n;return true;}return false;}private:vectorData _tables;size_t _n 0;//表中存储的有效数据的个数
};void TestHT2()
{string arr[] { 苹果, 西瓜, 香蕉, 苹果, 西瓜 , 苹果, 苹果,西瓜,苹果,香蕉, 苹果,香蕉 };HashTablestring, int, HashFuncstring countHT;for (auto e : arr){HashDatastring, int* ret countHT.Find(e);if (ret){ret-_kv.second;}else{countHT.Insert(make_pair(e, 1));}}
}如果映射的是vectorstring甚至是vectorvectorstring或者是一个利他的类映射成整形同样需要配套一个仿函数这就体现了仿函数的灵活比较。 因此对于unordered_map通过观察同样发现其就利用了哈希的仿函数进行映射在使用unordered_map时我们一般传入两个参数第三个有缺省值对于string类型等还有模板的特化因此在调用库中的unordered_map也无需自己设计仿函数。 此外对于map和unordered_map除了底层的区别还有就是map是比较的方式找值而unordered_map是通过指定的算法将传入的数据转成整形再映射。 对于我们设计的Hash表实际上也不需要写默认的六大成员函数因为vector作为自定义类型会调用自己内置的析构对于size_t这种内置类型也不用处理。
四.开散列代码
将除成员函数之外封装放在这里这样设计同样是为了更具观赏性。
templateclass K, class V
struct HashNode
{pairK, V _kv;HashNodeK, V* _next;
};templateclass K, class V, class Hash HashFuncK
class HashTable
{typedef HashNodeK, V Node;
public://插入、查找、删除private:vectorNode* _tables;//指针数组size_t _n;
};4.1 插入Insert
插入时由于是链表所以头插无疑是最好的方式。此外对于指针数组来说如果达到一定的限度同样需要扩容负载因子可以根据所需的数量从而控制在一定范围内在这里负载因子以1为例。 与闭散列不同的是因为是链表结构默认生成的析构函数不能将空间全部释放所以我们需要自己写一个析构函数将链表节点的空间释放。 开散列扩容的问题
对于哈希桶这种结构扩容意味着重新开辟空间将旧表数据映射到新表需要注意的是不能直接一串一串的复制因为由于新表的空间变大因此取模时的映射关系也会变话直接成串复制会导致映射关系发生错误进而在Find时找不到对应位置。所以还是要像正常扩容一样把旧表的数据都遍历一遍映射拷贝到新表。与闭散列一样的扩容方式
// 负载因子控制在1超过就扩容
if (_tables.size() _n)
{HashTableK, V, Hash newHT;newHT._tables.resize(_tables.size() * 2);for (auto cur : _tables){while (cur){newHT.Insert(cur-_kv);cur cur-_next;}}_tables.swap(newHT._tables);
}对于这种扩容方式实际上很浪费空间因其在插入过程中都是在拷贝节点在一定程度上浪费了空间并且在析构时会析构两次又是一次性能的缺失。本着能优化尽量优化的思想事实上我们可以将旧表中的结点头插到新表指定的映射位置这样就不需要拷贝创建新节点但这样需要注意的是要将旧表的每一个元素_tables[i]清理掉或者都置nullptr防止同一块空间析构两次造成浅拷贝。因此改善之后的扩容及插入代码如下
bool Insert(const pairK, V kv)
{if (Find(kv.first))return false;// 负载因子控制在1超过就扩容if (_tables.size() _n){vectorNode* newTables;newTables.resize(2 * _tables.size(), nullptr);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t hashi Hash()(cur-_kv.first) % newTables.size();//头插到新表cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}}size_t hashi Hash()(kv.first) % _tables.size();// 头插Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;
}4.2 查找Find
和开放定址法一样
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;}else{cur cur-_next;}}return nullptr;
}4.3 删除Erase
bool Erase(const K key)
{size_t hashi Hash()(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (cur-_kv.first 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;
}4.4 完整代码统计水果次数
//仿函数解决s映射问题完全没有关联的类型不能随便转这个不能string转整形因此还需要写一个
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};//特化
template
struct HashFuncstring
{size_t operator()(const string key){//BKDR-Hashsize_t hash 0;for (auto ch : key){hash * 131;hash ch;}return hash;//这样映射不易产生哈希冲突}
};templateclass K, class V, class Hash HashFuncK
class HashTable
{typedef HashNodeK, V Node;
public:HashTable():_n(0){_tables.resize(10);}~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 pairK, V kv){if (Find(kv.first))return false;// 负载因子控制在1超过就扩容if (_tables.size() _n){vectorNode* newTables;newTables.resize(2 * _tables.size(), nullptr);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t hashi Hash()(cur-_kv.first) % newTables.size();//头插到新表cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}}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;}else{cur cur-_next;}}return nullptr;}bool Erase(const K key){size_t hashi Hash()(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (cur-_kv.first 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:vectorNode* _tables; //指针数组size_t _n 0;
};void TestHT2()
{string arr[] { 苹果, 西瓜, 香蕉, 苹果, 西瓜 , 苹果, 苹果,西瓜,苹果,香蕉, 苹果,香蕉 };//HashTablestring, int, HashFuncString countHT;HashTablestring, int, HashFuncstring countHT;for (auto e : arr){auto ret countHT.Find(e);if (ret){ret-_kv.second;}else{countHT.Insert(make_pair(e, 1));}}
} 五.扩容机制
对于哈希来说源码中采用了哈希容量为奇数这样或许可以在取模的时候更加的分散缓解冲突但并不能完全解决极端场景仍然没有办法。下面改善一下扩容机制当然这种方式也是可有可无的。
if (_tables.size() _n)//扩容
{vectorNode* newTables;//newTables.resize(2 * _tables.size(), nullptr);newTables.resize(__stl_next_prime(_tables.size()), nullptr);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)) % newTables.size();// 头插到新表cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}inline unsigned long __stl_next_prime(unsigned long n)
{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};for (int i 0; i __stl_num_primes; i){if (__stl_prime_list[i] n){return __stl_prime_list[i];}}return __stl_prime_list[__stl_num_primes - 1];
}当然一旦数据过于驳杂哈希桶挂的单链表改成红黑树是一个很好的解决方式。
