洛阳做网站公司在哪,wordpress4.9.4 使用教程,基于asp的网络课程网站开发,网上ui设计培训文章目录 哈希哈希冲突哈希函数 解决哈希冲突闭散列#xff1a;开散列 哈希
在顺序结构和平衡树中#xff0c;元素的Key和存储位置之间没有必然的联系#xff0c;在进行查找的时候#xff0c;要不断的进行比较#xff0c;时间复杂度是O(N)或O(logN)
而有没有这样一种方案… 文章目录 哈希哈希冲突哈希函数 解决哈希冲突闭散列开散列 哈希
在顺序结构和平衡树中元素的Key和存储位置之间没有必然的联系在进行查找的时候要不断的进行比较时间复杂度是O(N)或O(logN)
而有没有这样一种方案可以直接不经过比较从表中得到所需要的元素呢直接进行获取就可以如果存在这样的结构那么对它而言的查找效率是很高的
插入元素
根据上面的原理在插入元素的时候根据插入元素的Key找到一个可以映射到一个表中的具体位置并进行存放
搜索元素
在对元素的Key进行计算后就可以直接找到它被映射到了表中的哪一个位置从而可以直接找到它在表中的位置如果找到了就返回true
上面的这个原理就叫做哈希也叫做散列而在哈希中使用的这个转换函数就叫做哈希函数也叫做散列函数构造出来的结构就叫做哈希表也叫做散列表
下面用一个例子来举例
例如数据集合有{1, 7, 6, 4, 5, 9}
那么就可以把根据一个哈希转换函数hash(key) key % capacity得到一个专属于它的下标把这个值存到下标的位置 通过这样的方法就可以对元素和下标建立一种关系在寻找的时候可以直接寻找到在进行数据的存储和查找的过程拥有相当高的效率
但依旧有问题如果存储的元素正好已经被存储过了呢
哈希冲突
所谓哈希冲突简单来说就是不同的Key值经过计算得到了一个相同的hash值此时再向表中填写数据就会有问题这个过程就叫哈希冲突也叫做哈希碰撞那为什么会引起哈希碰撞如何解决
哈希函数
通常来说引起哈希碰撞的一个原因是哈希函数有问题
常见的哈希函数定义
直接定址法取Key值的某个线性函数作为散列地址例如HashKey A*Key B除留余数法设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址平方取中法折叠法数学分析法
哈希函数设计的越好出现哈希冲突的可能性就越低但无法避免哈希冲突也就是说哈希冲突是一定会发生的
解决哈希冲突
解决的方法通常有两种闭散列和开散列
闭散列
当发生哈希冲突的时候如果哈希表没有被装满那么就说明哈希表中肯定还有空余位置那么就放到冲突位置的下一个位置当中去
线性探测
从发生哈希冲突的位置开始依次向后进行探测直到探测到了一个空位置为止
那么下面模拟实现一下线性探测的实现过程 bool insert(const pairK, V kv){// 考虑扩容问题if (_n * 10 / _t.size() 7){size_t newsize _t.size() * 2;vectorHashDataK, V newV;newV.resize(newsize);size_t _newn 0;// 把原来的数据放到新表中 遍历一次旧表for (int i 0; i _t.size(); i){// 如果旧表中这个位置的值存在 就准备放到新表中if (_t[i]._s EXIST){size_t newhashi _t[i]._kv.first % newsize;while (newV[newhashi]._s EXIST){newhashi;newhashi % newsize;}newV[newhashi]._kv _t[i]._kv;newV[newhashi]._s EXIST;_newn;}}_t.swap(newV);_n newsize;}// 正常插入逻辑size_t hashi kv.first % _t.size();while (_t[hashi]._s EXIST){// 如果插入元素的位置有内容就插入到下一个位置hashi;hashi % _t.size();}_t[hashi]._kv kv;_t[hashi]._s EXIST;_n;return true;}但是闭散列的缺陷是很明显的比如当插入数据是12,22,32,42…这样的数据的时候就会导致不停地触发哈希冲突这样会产生堆积的效应为了避免出现这样的问题又提出了开散列的方案
开散列
开散列也叫做哈希桶也叫做拉链法原理就是把具有相同地址的Key值放到一起每一个子集就叫做一个桶每个桶的元素通过单链表来进行链接每个链表的头结点在哈希表中 开散列中每个桶中放的都是哈希冲突的元素
namespace opened_hashing
{// 定义节点信息templateclass K, class Vstruct Node{Node(const pairK, V kv):_next(nullptr), _kv(kv){}Node* _next;pairK, V _kv;};templateclass K, class Vclass HashTable{typedef NodeK, V Node;public:// 构造函数HashTable():_n(0){_table.resize(10);}// 析构函数~HashTable(){//cout endl ******************* endl;//cout destructor endl;for (int i 0; i _table.size(); i){//cout [ i ]-;Node* cur _table[i];while (cur){Node* next cur-_next;//cout cur-_kv.first ;delete cur;cur next;}//cout endl;_table[i] nullptr;}}// 插入元素bool insert(const pairK, V kv){// 如果哈希表中有这个元素就不插入了if (find(kv.first)){return false;}// 扩容问题if (_n _table.size()){HashTable newtable;int newsize _table.size() * 2;newtable._table.resize(newsize, nullptr);for (int i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;// 把哈希桶中的元素插入到新表中int newhashi cur-_kv.first % newsize;// 头插cur-_next newtable._table[newhashi];newtable._table[newhashi] cur;cur next;}_table[i] nullptr;}_table.swap(newtable._table);}// 先找到在哈希表中的位置size_t hashi kv.first % _table.size();// 把节点插进去Node* newnode new Node(kv);newnode-_next _table[hashi];_table[hashi] newnode;_n;return true;}Node* find(const K Key){// 先找到它所在的桶int hashi Key % _table.size();// 在它所在桶里面找数据Node* cur _table[hashi];while (cur){if (cur-_kv.first Key){return cur;}cur cur-_next;}return nullptr;}void print(){for (int i 0; i _table.size(); i){cout i -;Node* cur _table[i];while (cur){cout cur-_kv.first ;cur cur-_next;}cout endl;}cout endl;}private:vectorNode* _table;size_t _n;};
}上面的实现看似没有问题实际上依旧有问题如果要传入的数据是string类那么在比较的过程中会出现错误因此要写一个仿函数用以处理这些情况 这里利用版本模板中的特化进行处理即可处理细节比较巧妙 templateclass Tstruct _Convert{T operator()(const T key){return key;}};templatestruct _Convertstring{size_t operator()(const string key){size_t sum 0;for (auto e : key){sum e * 31;}return sum;}};那么下一步就要进行对于哈希表的封装了详情见模拟实现篇章
