政务网站建设实施方案,七牛云图床,新网站怎样做好外链,nas访问不了wordpress文章目录 1. 哈希概念2. 哈希冲突3. 哈希函数4. 哈希冲突解决4.1 闭散列4.2 开散列 unordered 系列的关联式容器之所以效率比较高#xff0c;是因为其底层使用了哈希结构。
1. 哈希概念
顺序结构以及平衡树中#xff0c;元素关键码与其存储位置之间没有对应的关系#xff… 文章目录 1. 哈希概念2. 哈希冲突3. 哈希函数4. 哈希冲突解决4.1 闭散列4.2 开散列 unordered 系列的关联式容器之所以效率比较高是因为其底层使用了哈希结构。
1. 哈希概念
顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为 O(N)平衡树中为树的高度即 O( l o g 2 N log_2 N log2N)搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。
如果构造一种存储结构通过某种函数hashFunc使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。
当向该结构中 插入元素 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放 搜索元素 对元素的关键码进行同样的计算把求得的函数值当作元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功。
该方式即为哈希散列方法哈希方法中使用的转换函数称为哈希散列函数构造出来的结构称为哈希表Hash Table或者散列表。
例如数据集合 { 1, 7, 6, 4, 5, 9 }
哈希函数设置为hash(key) key % capacity; capacity 为存储元素底层空间总的大小。 用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快。
问题按照上述哈希方式向集合中插入元素 44会出现什么问题
2. 哈希冲突
对于两个数据元素的关键字 k i k_i ki 和 k j k_j kji ! j有 k i k_i ki ! k j k_j kj但有Hash( k i k_i ki) Hash( k j k_j kj)即不同关键字通过相同哈希函数计算出相同的哈希地址这种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
发生哈希冲突该如何处理呢
3. 哈希函数
引起哈希冲突的一个原因可能是哈希函数设计不够合理。
哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有 m 个地址时其值域必须在 0 到 m - 1 之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单。
常见哈希函数 直接定址法常用 取关键字的某个线性函数为散列地址Hash (Key) A * Key B 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况。 除留余数法常用 设散列表中允许的地址数为 m取一个不大于 m但最接近或者等于 m 的质数 p 作为除数按照哈希函数Hash (Key) Key % p (p m)将关键码转换成哈希地址。 平方取中法了解 假设关键字为 1234对它平方就是 1522756抽取中间的 3 位 227 作为哈希地址 再比如关键字为 4321对它平方就是 18671041抽取中间的 3 位 671或 710作为哈希地址 平方取中法比较适合不知道关键字的分布而位数又不是很大的情况。 折叠法了解 折叠法是将关键字从左到右分割成位数相等的几部分最后一部分位数可以短些然后将这几部分叠加求和并按照散列表表长取后几位作为散列地址 折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况。 随机数法了解 选择一个随机函数取关键字的随机函数值为它的哈希地址即 Hash (Key) random(Key)其中 random 为随机数函数 通常应用于关键字长度不等时采用此法。 数学分析法了解 设有 n 个 d 位数每一位可能有 r 种不同的符号这 r 种不同的符号在各位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。例如 假设要存储某家公司员工登记表如果用手机号作为关键字那么极有可能前 7 位都是相同的那么我们可以选择后面的四位作为散列地址如果这样的抽取工作还容易出现冲突还可以对抽取出来的数字进行反转如 1234 改成 4321、右环移位如 1234 改成 4123、左环移位、前两数与后两数叠加如 1234 改成 123446等方法 数字分析法通常适合处理关键字位数比较多的情况。
注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突。
4. 哈希冲突解决
解决哈希冲突两种常见的方法是闭散列和开散列。
4.1 闭散列
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明哈希表中必然还有空位置那么可以把 key 存放到冲突位置中的“下一个”空位置中去。那如何寻找下一个空位置呢 线性探测 比如上面的场景 现在需要插入元素 44先通过哈希函数计算哈希地址hashAddr 为 4因此 44 理论上应该插在该位置但是该位置已经放了值为 4 的元素即发生哈希冲突。 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 插入 通过哈希函数获取待插入元素在哈希表中的位置 如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素。 删除 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索。比如删除元素 4如果直接删除掉44 查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。 // 哈希表每个空间给个标记
// EMPTY此位置空 EXIST此位置已经有元素 DELETE元素已经删除
enum State
{EMPTY,EXIST,DELETE
};线性探测的实现 // 注意假如实现的哈希表中元素唯一即key相同的元素不再进行插入
// 为了实现简单此哈希表中我们将比较直接与元素绑定在一起
templateclass K, class V
class HashTable
{struct Elem{pairK, V _val;State _state;};public:HashTable(size_t capacity 3): _ht(capacity), _size(0){for (size_t i 0; i capacity; i)_ht[i]._state EMPTY;}bool Insert(const pairK, V val){// 检测哈希表底层空间是否充足// _CheckCapacity();size_t hashAddr HashFunc(key);// size_t startAddr hashAddr;while (_ht[hashAddr]._state ! EMPTY){if (_ht[hashAddr]._state EXIST _ht[hashAddr]._val.first key)return false;hashAddr;if (hashAddr _ht.capacity())hashAddr 0;/*转一圈也没有找到注意动态哈希表该种情况可以不用考虑哈希表中元素个数到达一定的数量哈希冲突概率会增大需要扩容来降低哈希冲突因此哈希表中元素是不会存满的if(hashAddr startAddr)return false;*/}// 插入元素_ht[hashAddr]._state EXIST;_ht[hashAddr]._val val;_size;return true;}int Find(const K key){size_t hashAddr HashFunc(key);while (_ht[hashAddr]._state ! EMPTY){if (_ht[hashAddr]._state EXIST _ht[hashAddr]._val.first key)return hashAddr;hashAddr;}return hashAddr;}bool Erase(const K key){int index Find(key);if (-1 ! index){_ht[index]._state DELETE;_size;return true;}return false;}size_t Size()const;bool Empty() const;void Swap(HashTableK, V, HF ht);private:size_t HashFunc(const K key){return key % _ht.capacity();}private:vectorElem _ht;size_t _size;
};思考哈希表什么情况下进行扩容如何扩容 void CheckCapacity()
{if (_size * 10 / _ht.capacity() 7){HashTableK, V, HF newHt(GetNextPrime(ht.capacity));for (size_t i 0; i _ht.capacity(); i){if (_ht[i]._state EXIST)newHt.Insert(_ht[i]._val);}Swap(newHt);}
}线性探测优点实现非常简单 线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要多次比较导致搜索效率降低如何缓解 二次探测 线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为 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如果超出必须考虑增容。
因此闭散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷。
4.2 开散列 开散列的概念 开散列法又叫链地址法开链法首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头节点存储在哈希表中。 个人理解哈希桶 顺序表 链表 哈希算法 从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素。 开散列实现 templateclass V
struct HashBucketNode
{HashBucketNode(const V data): _pNext(nullptr), _data(data){}HashBucketNodeV* _pNext;V _data;
};// 本文所实现的哈希桶中key是唯一的
templateclass V
class HashBucket
{typedef HashBucketNodeV Node;typedef Node* PNode;
public:HashBucket(size_t capacity 3) : _size(0){_ht.resize(GetNextPrime(capacity), nullptr);}// 哈希桶中的元素不能重复PNode* Insert(const V data){// 确认是否需要扩容。。。// _CheckCapacity();// 1. 计算元素所在的桶号size_t bucketNo HashFunc(data);// 2. 检测该元素是否在桶中PNode pCur _ht[bucketNo];while (pCur){if (pCur-_data data)return pCur;pCur pCur-_pNext;}// 3. 插入新元素pCur new Node(data);pCur-_pNext _ht[bucketNo];_ht[bucketNo] pCur;_size;return pCur;}// 删除哈希桶中为data的元素(data不会重复)返回删除元素的下一个节点PNode* Erase(const V data){size_t bucketNo HashFunc(data);PNode pCur _ht[bucketNo];PNode pPrev nullptr, pRet nullptr;while (pCur){if (pCur-_data data){if (pCur _ht[bucketNo])_ht[bucketNo] pCur-_pNext;elsepPrev-_pNext pCur-_pNext;pRet pCur-_pNext;delete pCur;_size--;return pRet;}}return nullptr;}PNode* Find(const V data);size_t Size()const;bool Empty()const;void Clear();bool BucketCount()const;void Swap(HashBucketV, HF ht;~HashBucket();private:size_t HashFunc(const V data){return data % _ht.capacity();}private:vectorPNode* _ht;size_t _size; // 哈希表中有效元素的个数
};开散列增容 桶的个数是一定的随着元素的不断插入。每个桶中元素的个数不断增多极端情况下可能会导致一个桶中链表节点非常多会影响哈希表的性能因此在一定条件下需要对哈希表进行增容那该条件怎么确认呢开散列最好的情况是每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可以给哈希表增容。 void _CheckCapacity(){size_t bucketCount BucketCount();if (_size bucketCount){HashBucketV, HF newHt(bucketCount);for (size_t bucketIdx 0; bucketIdx bucketCount; bucketIdx){PNode pCur _ht[bucketIdx];while (pCur){// 将该节点从原哈希表中拆出来_ht[bucketIdx] pCur-_pNext;// 将该节点插入到新哈希表中size_t bucketNo newHt.HashFunc(pCur-_data);pCur-_pNext newHt._ht[bucketNo];newHt._ht[bucketNo] pCur;pCur _ht[bucketIdx];}}newHt._size _size;this-Swap(newHt);}}开散列的思考 只能存储 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];
}开散列与闭散列比较 应用链地址法处理溢出需要增设链接指针似乎增加了存储开销。事实上由于开地址法必须保持大量的空闲空间以确保搜索效率如二次探测法要求装载因子 a 0.7而表项所占空间又比指针大得多所以使用链地址法反而比开地址法节省存储空间。 END
