网站同时使用asp php,微信企业公众号开发,wordpress 进销存插件,erp系统下载手机版文章目录 哈希概念哈希冲突哈希函数哈希表闭散列开散列 开散列与闭散列比较 正文开始前给大家推荐个网站#xff0c;前些天发现了一个巨牛的
人工智能学习网站#xff0c;
通俗易懂#xff0c;风趣幽默#xff0c;忍不住分享一下给大家。
点击跳转到网站。 哈希概念
顺… 文章目录 哈希概念哈希冲突哈希函数哈希表闭散列开散列 开散列与闭散列比较 正文开始前给大家推荐个网站前些天发现了一个巨牛的
人工智能学习网站
通俗易懂风趣幽默忍不住分享一下给大家。
点击跳转到网站。 哈希概念
顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为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),将关键码转换成哈希地址
哈希表
解决哈希冲突两种常见的方法是闭散列和开散列
闭散列
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。
怎么找下个空位置呢
线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。二次探测线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位 置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为 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是表的大小。
线性探测和二次探测实现方法类似只有找空位置的地方有点区别我们以实现线性探测为例。我们使用的是除留余数法。每个Key对表的大小取余确定对应的哈希地址。
一个位置的状态可能有三种空、存在、删除有很多人有一个误区觉得空状态和删除状态是一样的其实他们差别挺大的为什么这么说呢我们看下面场景 我们把6删除了。
此时如果找44遇到空就会停止那44我们就无法找到所以删除状态是必须的我们找查找时是遇到空就停止并且删除44也是无法成功的与查找同理。
结构 我们需要枚举来表示三个状态哈希表本质就是用数组实现的我们这里可以直接使用vector我们把状态和需要存储的值用一个结构体封起来存到vector中就可以了。
enum Status
{EMP,//空DEL,//删除EXI//存在
};template class K, class V
struct HashNode
{//表示状态Status _s;pairK, V _kv;
};template class K, class V, class Hash HashFuncK
class HashTable
{
private:vectorHashNodeK, V _v;//表示存储了多少个数据size_t _n 0;//为了解决不能被取余的值Hash hs;
};插入
首先需要通过哈希映射所以要对表的大小取余然后在这个对应的位置去把值放进去并且把状态改为存在。但是有一个问题这个位置有可能已经被有的值映射过了这是就需要使用线性探测我们要从这个位置开始找到一个状态为空或者删除的位置然后才能把值放进去。还有一个问题就是我们什么时候扩容呢
有一个东西叫做负载因子负载因子 数据的个数 / 表的大小我们通过控制负载因子来控制扩容的时机如果负载因子控制的太大那么出现哈希冲突的概率就太大了但是如果负载因子太小了那么对于空间的浪费太多了所以负载因子的选择对哈希表的影响还是挺大的。闭散列我们一般把负载因子控制在0.7.
那么怎么扩容呢 我们不能再原表直接扩容因为扩容会打乱映射关系所以我们需要建立一个新表然后把新表的大小初始化成旧表的二倍然后遍历旧表把旧表的数据重新插入映射到新表新表的内容就是我们需要的所以我们此时可以考虑直接swap两个新旧表中的vector这样就可以完美的符合我们的需求。
bool Insert(const pairK, V kv)
{if (Find(kv.first)){return false;}if (_n * 10 / _v.size() 7){int newsize _v.size() * 2;HashTableK, V newTable;newTable._v.resize(newsize);for (size_t i 0; i _v.size(); i){if (_v[i]._s EXI){newTable.Insert(_v[i]._kv);}}_v.swap(newTable._v);}size_t hashi hs(kv.first) % _v.size();//寻找下个是删除或者空的位置while (_v[hashi]._s EXI){hashi;//防止越界hashi % _v.size();}_v[hashi]._kv kv;_v[hashi]._s EXI;_n;return true;
}删除和查找
查找同样需要映射然后从当前位置开始查找只要不为空就一直找如果找到了Key并且状态为存在我们就可以直接返回当且的节点如果到空都没找到就返回nullptr。 删除需要先查找查找到直接改状态就可以不然就返回false。
HashNodeK,V* Find(const K k)
{size_t hashi hs(k) % _v.size();while (_v[hashi]._s ! EMP){if (_v[hashi]._s EXI _v[hashi]._kv.first k){return _v[hashi];}hashi;hashi % _v.size();}return nullptr;
}bool Erase(const K k)
{HashNodeK, V* f Find(k);if (f){f-_s DEL;_n--;return true;}else{return false;}
}以上情况如果我们存储整型的话当然是没问题的但是如果我们存储的是string等不能直接被取余的类型怎么办
这是我们就可以传一个仿函数来把不能不能直接被取余的类型转化为整型。
templateclass K
struct HashFunc
{size_t operator()(const K k){return (size_t)k;}
};template
struct HashFuncstring
{size_t operator()(const string s){size_t sum 0;for (auto e : s){sum sum * 31 e;}return sum;}
};
一般我们会特化一个string的因为字符串是最常见的。我们这里字符串转化为整型时BKDR法。
开散列
开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。开散列中每个桶中放的都是发生哈希冲突的元素。 这里实现我们直接使用vector就可以因为每个桶都是哈希冲突的元素所以结构需要一个链接下一个节点的指针。
结构
template class K, class V
struct HashNode
{pairK, V _kv;HashNode* _next;HashNode(const pairK,V kv): _kv(kv), _next(nullptr){}
};template class K, class V, class Hash HashFuncK
class HashTable
{typedef HashNodeK, V Node;
private:vectorNode* _tables;size_t _n;Hash hs;
};这里的插入删除查找都是直接映射然后都是单链表的操作插入因为哈希本来就是无序的所以我们直接头插就行了只有扩容时需要我们重点说一下我们可以跟上面闭散列一样建立一个新表然后把节点重新插入一下但是这里会产生很多的浪费因为原来表的节点重现插入以后就会被释放了有没有一种办法把原来的节点直接拿到新表呢 我们遍历原表时再拿到一个节点后直接通过映射把他的链接关系连接到新表中去就可以实现这样的效果只不过需要我们提前记录一下下一个节点不然会找不到下一个节点。
桶的个数是一定的随着元素的不断插入每个桶中元素的个数不断增多极端情况下可能会导致一个桶中链表节点非常多会影响的哈希表的性能因此在一定条件下需要对哈希表进行增容那该条件怎么确认呢 开散列最好的情况是每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可以给哈希表增容。
开散列
templateclass K
struct HashFunc
{size_t operator()(const K k){return (size_t)k;}
};template
struct HashFuncstring
{size_t operator()(const string s){size_t sum 0;for (auto e : s){sum sum * 31 e;}return sum;}
};
template class K, class V
struct HashNode
{pairK, V _kv;HashNode* _next;HashNode(const pairK,V kv): _kv(kv), _next(nullptr){}
};template class K, class V, class Hash HashFuncK
class HashTable
{typedef HashNodeK, V Node;
public:HashTable(){_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;}if (_n _tables.size()){//需要扩容vectorNode* newtables;newtables.resize(2 * _tables.size());for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t hashi cur-_kv.first % newtables.size();cur-_next newtables[hashi];newtables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newtables);}size_t hashi hs(kv.first) % _tables.size();Node* cur new Node(kv);cur-_next _tables[hashi];_tables[hashi] cur;_n;return true;}Node* Find(const K k){size_t hashi hs(k) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first k){return cur;}cur cur-_next;}return nullptr;}bool Erase(const K k){size_t hashi hs(k) % _tables.size();Node* cur _tables[hashi];Node* prev nullptr;while (cur){if (cur-_kv.first k){if (prevnullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;return true;}cur cur-_next;}return false;}
private:vectorNode* _tables;size_t _n;Hash hs;};开散列与闭散列比较
应用链地址法处理溢出需要增设链接指针似乎增加了存储开销。事实上由于开地址法必须保持大量的空闲空间以确保搜索效率如二次探查法要求装载因子a 0.7而表项所占空间又比指针大的多所以使用链地址法反而比开地址法节省存储空间。
