手机算命网站建设,2个小时学会网站建设,织梦做的网站打不开网页,网站建站加盟数据结构之哈希表 文章目录 数据结构之哈希表一、哈希概念二、哈希冲突三、哈希函数常见哈希函数 四、哈希冲突解决闭散列闭散列的思考线性探测线性探测的实现 二次探测 开散列开散列概念开散列的思考开散列实现 五、开散列与闭散列比较 一、哈希概念
顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O( l o g 2 N log_2 N log2N)搜索的效率取决于搜索过程中元素的比较次数 理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素
当向该结构中 插入元素 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放 搜索元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功 该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash Table)(或者称散列表)
这种方法在理想状态下通俗来讲就是更具某种对应关系构造一个萝卜一个坑查找时只需要根据对应的坑找这个萝卜但这种方法必定会出现一个坑对应了多个萝卜的情况专业来讲这种情况叫做哈希冲突而如何解决哈希冲突则是哈希表的实现关键
二、哈希冲突
对于两个数据元素的关键字 k i k_i ki和 k j k_j kj(i ! j)有 k i k_i ki ! k j k_j kj但有Hash( k i k_i ki) Hash( k j k_j kj)即不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”
而发生哈希冲突该如何处理呢 三、哈希函数
引起哈希冲突的一个原因可能是哈希函数设计不够合理
哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单
常见哈希函数
直接定址法–(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况 面试题字符串中第一个只出现一次字符除留余数法–(常用) 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数 按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址平方取中法–(了解) 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址 再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合不知道关键字的分布而位数又不是很大的情况折叠法–(了解) 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)然后将这 几部分叠加求和并按散列表表长取后几位作为散列地址 折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况随机数法–(了解) 选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key),其中 random为随机数函数。 通常应用于关键字长度不等时采用此法数学分析法–(了解) 设有n个d位数每一位可能有r种不同的符号这r种不同的符号在各位上出现的频率不一定 相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只 有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散 列地址 通常适合处理关键字位数比较大的情况如果事先知道关键字的分布且关键字的若干位分布较均匀的情况
注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突
四、哈希冲突解决
解决哈希冲突两种常见的方法是闭散列和开散列
闭散列
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有 空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置 呢
闭散列的思考
思考:哈希表什么情况下进行扩容?如何扩容? 这里需要引入哈希表的负载因子的概念由于我们实现的是开放定址法一但发生冲突以后就需要逐个往后找空位而能否快速找到这个位置与当前未空的比例有关而负载因子的定义就与此有关
散列表的载荷因子定义为α 填入表中的元素个数 / 散列表的长度 α是散列表装满程度的标志因子由于表长是定值α与“填入表中的元素个数”成正比所以α越大表明填入表中的元素越多产生冲突的可能性就越大反之α越小标明填入表中的元素越少产生冲突的可能性就越小 实际上散列表的平均查找长度是载荷因子α的函数只是不同处理冲突的方法有不同的函数
对于开放定址法荷载因子是特别重要因素应严格限制在0.7-0.8以下。超过0.8查表时的CPU缓存不命中(cachemissing按照指数曲线上升。因此一些采用开放定址法的hash库如Java的系统库限制了荷载因子为0.75超过此值将resize散列表
线性探测
线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止
比如下图中的场景现在需要插入元素44先通过哈希函数计算哈希地址hashAddr为4因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。 插入 通过哈希函数获取待插入元素在哈希表中的位置 如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突 使用线性探测找到下一个空位置插入新元素 删除 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索 比如删除元素4如果直接删除掉44查找起来可能会受影响因此线性探测采用标记的伪删除法来删除一个元素 线性探测的实现
namespace Tlzns
{enum status{Empty,Exist,Delete};templateclass K,class Vstruct HashData{pairK, V _kv;status _s;};templateclass Kstruct HashFunc{size_t operator()(const K key){return (size_t)key;}};//针对string特化templatestruct HashFuncstring{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash * 13;hash e;}return hash;}};templateclass K, class V, class Hash HashFuncKclass HashTable{public:HashTable(size_t n 10){_t.resize(n);}bool Insert(const pairK, V kv){if (Find(kv.first)){return false;}Hash hf;//扩容if (_n * 10 / _t.size() 7){size_t newsize _t.size() * 2;HashTable newtable(newsize);for (int i 0; i _n; i){if (_t[i]._s Exist){newtable.Insert(_t[i]._kv);}}swap(_t, newtable._t);}size_t hashi hf(kv.first) % _t.size();while (_t[hashi]._s Exist){hashi;}_t[hashi]._kv kv;_t[hashi]._s Exist;_n;return true;}HashDataK, V* Find(const K key){Hash hf;size_t hashi hf(key) % _t.size();if (_t[hashi]._s Exist _t[hashi]._kv.first key){return _t[hashi];}else{return NULL;}}bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_s Delete;return true;}else{return false;}}void Print(){for (size_t i 0; i _t.size(); i){if (_t[i]._s Exist){//printf([%d]-%d\n, i, _tables[i]._kv.first);cout [ i ]- _t[i]._kv.first : _t[i]._kv.second endl;}else if (_t[i]._s Empty){printf([%d]-\n, i);}else{printf([%d]-D\n, i);}}cout endl;}private:vectorHashDataK, V _t;size_t _n 0;};void TestHT1(){HashTableint, int ht;int a[] { 4,14,24,34,5,7,1 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(-3, -3));ht.Print();ht.Erase(3);ht.Print();if (ht.Find(3)){cout 3存在 endl;}else{cout 3不存在 endl;}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(23, 3));ht.Print();}void TestHT2(){string arr[] { 香蕉, 甜瓜,苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };HashTablestring, int ht;for (auto e : arr){//auto ret ht.Find(e);HashDatastring, int* ret ht.Find(e);if (ret){ret-_kv.second;}else{ht.Insert(make_pair(e, 1));}}ht.Print();ht.Insert(make_pair(apple, 1));ht.Insert(make_pair(sort, 1));ht.Insert(make_pair(abc, 1));ht.Insert(make_pair(acb, 1));ht.Insert(make_pair(aad, 1));ht.Print();}}二次探测
线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为 H i H_i Hi ( H 0 H_0 H0 i 2 i^2 i2 )% m, 或者 H i H_i Hi ( H 0 H_0 H0 - i 2 i^2 i2 )% m其中i 1,2,3… H 0 H_0 H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置m是表的大小 对于下图中如果要插入44产生冲突使用解决后的情况为 研究表明当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表装满的情况但在插入时必须确保表的装载因子a不超过0.5如果超出必须考虑增容
因此闭散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷
开散列
开散列概念
开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中 从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素
开散列的思考
只能存储key为整形的元素其他类型怎么解决
// 哈希函数采用处理余数法被模的key必须要为整形才可以处理此处提供将key转化为整形的方法
// 整形数据不需要转化
templateclass T
class DefHashF
{
public:size_t operator()(const T val){return val;}
};
// key为字符串类型需要将其转化为整形
class Str2Int
{
public:size_t operator()(const string s){const char* str s.c_str();unsigned int seed 131; // 31 131 1313 13131 131313unsigned int hash 0;while (*str){hash hash * seed (*str);}return (hash 0x7FFFFFFF);}
};
// 为了实现简单此哈希表中我们将比较直接与元素绑定在一起
templateclass V, class HF
class HashBucket
{// ……
private:size_t HashFunc(const V data){return HF()(data.first) % _ht.capacity();}
};除留余数法最好模一个素数如何每次快速取一个类似两倍关系的素数
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];
}开散列实现
namespace Tlzns
{templateclass K,class Vstruct HashNode{HashNode(const pairK, V kv):_kv(kv),_next(nullptr){}pairK, V _kv;HashNode* _next;};templateclass Kstruct HashFunc{size_t operator()(const K key){return (size_t)key;}};templatestruct HashFuncstring{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash * 13;hash e;}return hash;}};templateclass K, class V, class Hash HashFuncKclass HashTable{typedef HashNodeK, V Node;public:HashTable(size_t n 10){_t.resize(n);}~HashTable(){for (auto e : _t){Node* cur e;while (cur){Node* next cur-_next;delete cur;cur next;}e nullptr;}}bool Insert(const pairK, V kv){if (Find(kv.first)){return false;}Hash hf;//扩容if (_n / _t.size() 1){size_t newsize _t.size() * 2;HashTable newtable(newsize);for (int i 0; i _n; i){Node* cur _t[i];while (cur){Node* next cur-_next;size_t hashi hf(cur-_kv.first) % newsize;cur-_next newtable._t[hashi];newtable._t[hashi] cur;cur next;}_t[i] nullptr;}swap(_t, newtable._t);}size_t hashi hf(kv.first) % _t.size();Node* newnode new Node(kv);newnode-_next _t[hashi];_t[hashi] newnode;_n;return true;}HashNodeK, V* Find(const K key){Hash hf;size_t hashi hf(key) % _t.size();Node* cur _t[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;}bool Erase(const K key){Hash hf;size_t hashi hf(key) % _t.size();Node* cur _t[hashi];Node* prev nullptr;if (cur-_kv.first key){_t[hashi] cur-_next;delete cur;return true;}while (cur){if (cur-_kv.first key){prev-_next cur-_next;delete cur;_n--;return true;}prev cur;cur cur-_next;}return false;}private:vectorHashNodeK, V* _t;size_t _n 0;};void TestHT1(){HashTableint, int ht;int a[] { 4,14,24,34,5,7,1,15,25,3 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(13, 13));cout ht.Find(4) endl;ht.Erase(4);cout ht.Find(4) endl;}void TestHT2(){string arr[] { 香蕉, 甜瓜,苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };HashTablestring, int ht;for (auto e : arr){//auto ret ht.Find(e);HashNodestring, int* ret ht.Find(e);if (ret){ret-_kv.second;}else{ht.Insert(make_pair(e, 1));}}int i 0;}
}五、开散列与闭散列比较
应用链地址法拉链法处理溢出需要增设链接指针似乎增加了存储开销 而事实上由于开地址法必须保持大量的空闲空间以确保搜索效率如二次探查法要求装载因子a 0.7而表项所占空间又比指针大的多所以使用链地址法反而比开地址法节省存储空间
并且哈希思想实现的unordered_map与unordered_set比红黑树实现的map与set在综合性上能更具优势 所以C11中unordered_map与unordered_set底层都是用开散列的拉链法实现的
