ps网站导航制作,旅游网站开发的意义,淘宝内部优惠券网站怎么做,怎么购买域名自己做网站目录 一、哈希的引入
二、概念
三、哈希冲突
四、哈希函数
常见的哈希函数
1、直接定址法
2、除留余数法
五、哈希冲突的解决
1、闭散列
2、开散列 一、哈希的引入 顺序结构以及平衡树中#xff0c;元素关键码与其存储位置之间没有对应的关系#xff0c;因此在查找…目录 一、哈希的引入
二、概念
三、哈希冲突
四、哈希函数
常见的哈希函数
1、直接定址法
2、除留余数法
五、哈希冲突的解决
1、闭散列
2、开散列 一、哈希的引入 顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O(log_2 N)搜索的效率取决于搜索过程中元素的比较次数。 理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。 这种思想就是我们接下来要讲的哈希了。 二、概念
如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系那么在查找时通过该函数可以很快找到该元素。 当向该结构中 插入元素根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放。 搜索元素对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功。 该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash Table)(或者称散列表)。
当有这些数据时145679。我们可以通过下图的方式去插入数据。 用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快。 三、哈希冲突
按照上面的方式如果我们插入的是 123222279这几个数呢
我们发现如果按照哈希的思想去插入的话23222将会被放在同一个位置这样就会引起一些麻烦。如果我去访问下标为2位置的数据到底访问的哪一个呢我们将这种现象称为哈希冲突。
不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。 四、哈希函数
引起哈希冲突的一个原因可能是哈希函数设计不够合理。
常见的哈希函数
1、直接定址法
取关键字的某个线性函数为散列地址HashKey A*Key B。 优点简单、均匀。 缺点需要事先知道关键字的分布情况。 使用场景适合查找比较小且连续的情况。
2、除留余数法
设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p (pm)将关键码转换成哈希地址。 五、哈希冲突的解决
1、闭散列 闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。 那么这个下一个位置怎么确定呢我们有两种方法来帮助我们寻找“下一个”位置。
~ 线性探测
比如三中的情况插入2之后现在需要插入元素32先通过哈希函数计算哈希地址为2因此32理论上应该插在该位置但是该位置已经放了值为2的元素即发生哈希冲突。这时我们就需要去寻找该位置后面的空位置了。 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 如下图32只能插入在3的位置了。 注采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素 会影响其他元素的搜索。比如删除元素2如果直接删除掉32查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。 在有限的空间内随着我们插入的数据越来越多冲突的概率也越来越大查找效率越来越低所以闭散列的冲突表不可能让它满了所以我们就引入了负载因子
负载因子(载荷因子)等于表中的有效数据个数/表的大小衡量表的满程度在闭散列中负载因子不可能超过11代表满了。一般情况下负载因子一般在0.7左右。负载因子越小冲突概率也越小但是消耗的空间越大负载因子越大冲突概率越大空间的利用率越高。
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};//特化
template
struct HashFuncstring
{size_t operator()(const string key){size_t val 0;for (auto ch : key){val * 131;val ch;}return val;}
};namespace closehash
{
enum State
{EMPTY,DELETE,EXIST
};templateclass K,class V
struct HashData
{pairK, V _kv;State _state EMPTY;
};templateclass K, class V, class Hash HashFuncK
class HashTable
{
public:bool insert(const pairK, V kv){if (Find(kv.first)){return false;}if (_tables.size() 0 || 10 * _size / _tables.size() 7){size_t newsize _tables.size() 0 ? 10 : _tables.size() * 2;HashTableK, V, Hash newHT;newHT._tables.resize(newsize);for (auto e : _tables){if (e._state EXIST){newHT.insert(e._kv);}}_tables.swap(newHT._tables);}Hash hash;size_t index hash(kv.first) % _tables.size();//如果kv.first是string类型那么就无法取模因此我们要使用仿函数将其转换成整型//线性探测while (_tables[index]._state EXIST){index;index % _tables.size();}_tables[index]._kv kv;_tables[index]._state EXIST;_size;return true;}HashDataK, V* Find(const K key){if (_tables.size() 0){return nullptr;}Hash hash;size_t hashi hash(key) % _tables.size();size_t start hashi;while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._state ! DELETE _tables[hashi]._kv.first key){return _tables[hashi];}hashi;hashi % _tables.size();if (hashi start){break;}}return nullptr;}bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_state DELETE;_size--;return true;}elsereturn false;}private:vectorHashDataK, V _tables;size_t _size 0; //存储了多少个有效数据};
2、开散列 概念开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素。
那么是不是我们只需要开固定的空间然后其他的数据就一直连接到对应的桶的后面那样桶是不是太长了呢
桶的个数是一定的随着元素的不断插入每个桶中元素的个数不断增多极端情况下可能会导致一个桶中链表节点非常多会影响的哈希表的性能因此在一定条件下需要对哈希表进行增容。 增容条件每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可以给哈希表增容。 templateclass K,class Vstruct HashNode{pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK, V kv):_kv(kv), _next(nullptr){}};templateclass K, class V, class Hash HashFuncKclass HashTable{typedef HashNodeK, V Node;public:~HashTable(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;free(cur);cur next;}_tables[i] nullptr;}}bool insert(const pairK, V kv){//去重if (Find(kv.first)){return false;}Hash hash;//扩容if (_size _tables.size()){size_t newsize _tables.size() 0 ? 10 : _tables.size() * 10;vectorNode* newTables;newTables.resize(newsize, 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;}_tables.swap(newTables);}size_t hashi hash(kv.first) % _tables.size();Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_size;return true;}Node* Find(const K key){if (_tables.size() 0)return nullptr;Hash hash;size_t hashi hash(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key)return cur;elsecur cur-_next;}return nullptr;}bool erase(const K key){if (_tables.size() 0){return nullptr;}Hash hash;size_t hashi hash(key) % _tables.size();Node* cur _tables[hashi];Node* prev nullptr;while (cur){if (cur-_kv.first key){// 1、头删// 2、中间删if (prev nullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;_size--;return true;}prev cur;cur cur-_next;}return false;}private:vectorNode* _tables;size_t _size 0;};
