科讯网站首页公告模板,免费友情链接网站,网站项目建设的组织机构,dw登录页面怎么制作文章目录 1. 哈希的概念2. 哈希表与哈希函数2.1 哈希冲突2.2 哈希函数2.3 哈希冲突的解决2.3.1 闭散列#xff08;线性探测#xff09;2.3.2 闭散列的实现2.3.3 开散列(哈希桶)2.3.4 开散列的实现 2.4 开散列与闭散列比较 1. 哈希的概念
在我们之前所接触到的所有的数据结构… 文章目录 1. 哈希的概念2. 哈希表与哈希函数2.1 哈希冲突2.2 哈希函数2.3 哈希冲突的解决2.3.1 闭散列线性探测2.3.2 闭散列的实现2.3.3 开散列(哈希桶)2.3.4 开散列的实现 2.4 开散列与闭散列比较 1. 哈希的概念
在我们之前所接触到的所有的数据结构中元素关键码与其存储位置之间没有对应的关系因此我们要想查找一个元素必须要经过关键码的多次比较。
顺序查找时间复杂度为O(N)平衡树中为树的高度即O(log2N)搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一 一映射的关系那么在查找时通过该函数可以很快找到该元素。
向该结构中搜索与查找一个元素时可以直接通过关键码的值然后通过某种函数直接找到该元素所在的位置。
该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表或者称散列表
2. 哈希表与哈希函数 其中size为表中元素的大小最初是默认是10
2.1 哈希冲突
按照上述哈希方式向集合中插入元素14、24、34会出现什么问题
不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
发生哈希冲突该如何处理呢
2.2 哈希函数
引起哈希冲突的一个原因可能是哈希函数设计不够合理。 哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在[0,m-1]中哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单
常见哈希函数 直接定址法- -(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B。例如一个字符串其在哈希比表中的位置就可以使字符串中所有字符的和为了避免key不同而地址相同可以在乘以一个A 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况 除留余数法- -(常用) 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p将关键码转换成哈希表中的3地址 随机数法- -(了解) 选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key),其中random为随机数函数。 通常应用于关键字长度不等时采用此法
由于哈希函数比较多这里就不一一列举了。
2.3 哈希冲突的解决
2.3.1 闭散列线性探测
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢
线性探测
比如上述中的场景现在需要插入元素14先通过哈希函数计算哈希地址hashi为4因此14理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。
线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。
插入 通过哈希函数获取待插入元素在哈希表中的位置 如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突则使用线性探测找到下一个空位置插入新元素 查找
例如要找key为14的元素首先使用哈希函数计算出元素在哈希表中的地址从该地址处依次向后比较直到遇到空位置。 删除
对于删除而言要先查找到元素然后再将元素删除掉。那怎么删呢将该位置的状态置为吗 删除数据时只需将该位置设置为删除不能将该位置的状态设置为空否则将影响查找功能如果将14位置的状态置为空在查找44时将找不到走到空就停下了
2.3.2 闭散列的实现
为了标明每个位置的状态我们可以使用枚举常量来表示 //元素的状态enum State{EXIST 0, //已有元素DELETE, //该位置元素已删除EMPTY //该位置为空};哈希表的初步框架
namespace open_addr
{//为了后期适配map与set这里先给两个模板参数templateclass K,class Tclass HashTable{//元素的状态enum State{EXIST 0, //已有元素DELETE, //该位置元素已删除EMPTY //该位置为空};//元素的结构struct Element{T _data;State _state;};public:HashTable(size_t N 10){_table.resize(N);for (size_t i 0; i N; i){_table[i]._state EMPTY;}}bool insert(const T data){}size_t find(const K key){}bool erase(const K key){}private:vectorElement _table;//哈希表size_t _n; //记录当前元素个数};
}下面我们就来具体实现各项功能
插入 //哈希函数templateclass Kstruct HashFunc{size_t operator()(const K key){return key;}};bool insert(const T data){//根据哈希函数计算位置Hash hs;size_t hashi hs(data) % _table.size();//检查是否有哈希冲突问题while (_table[hashi]._state EXIST){hashi;hashi % _table.size();//实现下标的环绕}//插入元素修改状态_table[hashi]._data data;_table[hashi]._state EXIST;_n;return true;}当我们的元素是int时代码可以跑通但当元素是string时代码就过不了了。 所以我们需要对哈希函数进行特化处理。 此时不管你是什么类型只要提供对应的哈希函数我们的代码就可以跑 哈希表扩容问题
如果我们的哈希表满了那么数据进来后就会一直死循环而且哈希表中元素越多哈希冲突越高效率越低。
因此就引入了载荷因子来判断是否需要扩容来提高效率问题 散列表的载荷因子定义为: a 填入表中的元素个数 / 散列表的长度 a是散列表装满程度的标志因子。由于表长是定值a与“填入表中的元素个数”成正比所以a越大表明填入表中的元素越多产生冲突的可能性就越大反之a越小标明填入表中的元素越少产生冲突的可能性就越小。实际上散列表的平均查找长度是载荷因子a的函数只是不同处理冲突的方法有不同的函数。对于开放定址法荷载因子是特别重要因素应严格限制在0.7-0. 8以下。超过0. 8查表时的CPU缓存不命中(cache missing)按照指数曲线上升。因此一些采用开放定址法的hash库如Java的 系统库限制了荷载因子为0.75超过此值将resize散列表。 扩容时先开一个是原来旧表二倍大小的新表然后根据旧表中的元素寻找元素在新表中的位置寻找位置插入。 由于再次计算位置插入元素和不扩容时的代码一样为了减少代码的冗余这里我们直接开一个新的哈希表最后交换两哈希表的表即可。 bool insert(const T data){size_t n _table.size();//检查是否扩容if (10 * _n / n 7){//直接建立一个新表HashTableK, T, Hash newtable;newtable._table.resize(n * 2);//复用插入的逻辑for (size_t i 0; i n; i){if (_table[i]._state EXIST)//该位置有元素才转移{newtable.insert(_table[i]._data);}}//交换新旧表swap(_table, newtable._table);}//根据哈希函数计算位置Hash hs;size_t hashi hs(data) % n;//检查是否有哈希冲突问题while (_table[hashi]._state EXIST){hashi;hashi % n;//实现下标的环绕}//插入元素修改状态_table[hashi]._data data;_table[hashi]._state EXIST;_n;return true;}查找
对于查找而言使用哈希函数计算好位置后从该位置向后找直到位置的状态为空 int find(const K key){//根据key获取表中的位置Hash hs;size_t hashi hs(key) % _table.size();while (_table[hashi]._state ! EMPTY){if (_table[hashi]._state EXIST _table[hashi]._data key){return hashi;}hashi;hashi % _table.size();}return -1;}删除 bool erase(const K key){int hashi find(key);if (hashi ! -1){_table[hashi]._state DELETE;//状态设置为删除--_n;//个数减少return true;}return false;}线性探测优点实现非常简单 线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降低。如何缓解呢
线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为 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是表的大小。
二次探测其实也只是缓解了该问题因此我们就不实现二次探测了。 闭散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷。
//原模板
templateclass K
struct HashFunc
{size_t operator()(const K key){return key;}
};//特化
template
struct HashFuncstring
{size_t operator()(const string key){size_t sum 0;for (auto e : key){sum * 31;//这里使用了直接地址法避免字符串的key计算后相同sum e;}return sum;}
};
namespace open_addr
{//为了后期适配map与set这里先给两个模板参数templateclass K,class T,class Hash HashFuncKclass HashTable{//元素的状态enum State{EXIST 0, //已有元素DELETE, //该位置元素已删除EMPTY //该位置为空};//元素的结构struct Element{T _data;State _state;};public:HashTable(size_t N 10){_table.resize(N);for (size_t i 0; i N; i){_table[i]._state EMPTY;}}bool insert(const T data){size_t n _table.size();//检查是否扩容if (10 * _n / n 7){//直接建立一个新表HashTableK, T, Hash newtable;newtable._table.resize(n * 2);//复用插入的逻辑for (size_t i 0; i n; i){if (_table[i]._state EXIST)//该位置有元素才转移{newtable.insert(_table[i]._data);}}//交换新旧表swap(_table, newtable._table);}//根据哈希函数计算位置Hash hs;size_t hashi hs(data) % n;//检查是否有哈希冲突问题while (_table[hashi]._state EXIST){hashi;hashi % n;//实现下标的环绕}//插入元素修改状态_table[hashi]._data data;_table[hashi]._state EXIST;_n;return true;}int find(const K key){//根据key获取表中的位置Hash hs;size_t hashi hs(key) % _table.size();while (_table[hashi]._state ! EMPTY){if (_table[hashi]._state EXIST _table[hashi]._data key){return hashi;}hashi;hashi % _table.size();}return -1;}bool erase(const K key){int hashi find(key);if (hashi ! -1){_table[hashi]._state DELETE;//状态设置为删除--_n;//个数减少return true;}return false;}size_t size(){return _n;}private:vectorElement _table;//哈希表size_t _n; //记录当前元素个数};
}2.3.3 开散列(哈希桶)
开散列法又叫链地址法(开链法)首先对关键码集合用哈希函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素。
2.3.4 开散列的实现
开散列与闭散列唯一的不同就是开散列使用了链表解决哈希冲突占据其它位置的问题。 所以此时的插入和删除就要按照链表的逻辑去走。
插入 桶的个数是一定的随着元素的不断插入每个桶中元素的个数不断增多极端情况下可能会导致一个桶中链表节点非常多会影响的哈希表的性能因此在一定条件下需要对哈希表进行增容那该条件怎么确认呢开散列最好的情况是每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可以给哈希表增容。 由于开辟节点的消耗比较大因此就不能使用闭散列那种方法复用插入我们可以按照元素的值计算新的位置对其进行重新连接省下来开辟节点的消耗。 bool insert(const T data){Hash hs;size_t size _table.size();//检查扩容if (_n size)//节点个数等于桶的数量时进行扩容{//为了节省开销不再重新开辟新节点直接映射原来的节点将原来的映射取消vectorNode* newtable(size * 2, nullptr);size_t newsize newtable.size();for (size_t i 0; i size; i){Node* cur _table[i];while (cur){size_t hashi hs(cur-_data) % newsize;//元素对应的新表中的位置Node* next cur-_next;//记录当前桶的下一个元素//头插连接到新桶cur-_next newtable[hashi];newtable[hashi] cur;cur next;}_table[i] nullptr;}swap(_table, newtable);}size_t hashi hs(data) % _table.size();//头插连接Node* newnode new Node(data);newnode-_next _table[hashi];_table[hashi] newnode;_n;return true;}查找
查找时按照哈希函数确定位置后遍历链表比较即可 Node* find(const K key){Hash hs;size_t hashi hs(key) % _table.size();Node* cur _table[hashi];while (cur){if (cur-_data key)return cur;cur cur-_next;}return nullptr;}删除
对于删除而言就不能直接利用find函数了。对于链表的删除要分几种情况讨论
当前桶是否只有这一个元素多个元素时删除链表中的节点要连接删除节点前后的节点要记录前驱节点 bool erase(const K key){Hash hs;size_t hashi hs(key) % _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (cur-_data key){if (prev nullptr)//桶中只有一个元素{_table[hashi] nullptr;}else{prev-_next cur-_next;//连接前驱和后继节点}delete cur;_n--;return true;}else{prev cur;cur cur-_next;}}return false;}析构
由于此处使用的是我们自己的链表所以最后别忘记释放节点 ~HashTable(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;delete cur;cur next;}_table[i] nullptr;}}//原模板
templateclass K
struct HashFunc
{size_t operator()(const K key){return key;}
};//特化
template
struct HashFuncstring
{size_t operator()(const string key){size_t sum 0;for (auto e : key){sum * 31;//这里使用了直接地址法避免字符串的key计算后相同sum e;}return sum;}
};namespace hash_bucket
{templateclass Tstruct HashNode{T _data;//数据域HashNodeT* _next;//指针域HashNode(const T data):_data(data), _next(nullptr){}};//为了后期适配map与set这里先给两个模板参数templateclass K, class T,class Hash HashFuncKclass HashTable{typedef HashNodeT Node;public:HashTable(size_t N 10){_table.resize(N,nullptr);}~HashTable(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;delete cur;cur next;}_table[i] nullptr;}}bool insert(const T data){Hash hs;size_t size _table.size();//检查扩容if (_n size)//节点个数等于桶的数量时进行扩容{//为了节省开销不再重新开辟新节点直接映射原来的节点将原来的映射取消vectorNode* newtable(size * 2, nullptr);size_t newsize newtable.size();for (size_t i 0; i size; i){Node* cur _table[i];while (cur){size_t hashi hs(cur-_data) % newsize;//元素对应的新表中的位置Node* next cur-_next;//记录当前桶的下一个元素//头插连接到新桶cur-_next newtable[hashi];newtable[hashi] cur;cur next;}_table[i] nullptr;}swap(_table, newtable);}size_t hashi hs(data) % _table.size();//头插连接Node* newnode new Node(data);newnode-_next _table[hashi];_table[hashi] newnode;_n;return true;}Node* find(const K key){Hash hs;size_t hashi hs(key) % _table.size();Node* cur _table[hashi];while (cur){if (cur-_data key)return cur;cur cur-_next;}return nullptr;}bool erase(const K key){Hash hs;size_t hashi hs(key) % _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (cur-_data key){if (prev nullptr)//桶中只有一个元素{_table[hashi] nullptr;}else{prev-_next cur-_next;}delete cur;_n--;return true;}else{prev cur;cur cur-_next;}}return false;}private:vectorNode* _table;size_t _n;};
}2.4 开散列与闭散列比较
用链地址法处理溢出需要增设链接指针似乎增加了存储开销。事实上由于开地址法必须保持大量的空闲空间以确保搜索效率如二次探查法要求装载因子a 0.7而表项所占空间又比指针大的多所以使用链地址法反而比开地址法节省存储空间。
