江苏建设集团有限公司网站,互联网门户网站,郑州有学网站制作,seo是什么意思的缩写哈希概念
顺序结构以及平衡树中#xff0c;元素关键码与其存储位置之间没有对应的关系#xff0c;因此在查找一个元素时#xff0c;必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)#xff0c;平衡树中为树的高度#xff0c;即O( Log2N)#xff0c;搜索的效率取决…哈希概念
顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O( Log2N)搜索的效率取决于搜索过程中元素的比较次数。 理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。
当向该结构中
插入元素 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放搜索元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功
该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash Table)(或者称散列表)
哈希冲突
不同元素通过相同哈希函数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。 所以我们需要进一步的改进哈希函数来解决冲突
哈希函数
引起哈希冲突的一个原因可能是哈希函数设计不够合理。 哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单
常用的哈希函数
直接定制法 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况除留余数法 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址平方取中法 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址 再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合不知道关键字的分布而位数又不是很大的情况折叠法 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)然后将这几部分叠加 求和并按散列表表长取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况随机数法 选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法数学分析法 假设要存储某家公司员工登记表如果用手机号作为关键字那么极有可能前7位都是 相同的那么我们可以选择后面的四位作为散列地址如果这样的抽取工作还容易出现 冲突还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成123446)等方法。数字分析法通常适合处理关键字位数比较大的情况如果事先知道关键字的分布且关键字的若干位分布较均匀的情况
不论函数设计的多好----都不可能完全的解决哈希冲突
哈希函数的冲突解决
闭散列
也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那 么可以把key存放到冲突位置中的“下一个” 空位置中去
1. 线性探测
插入 通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素 删除 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索。比如删除元素34如果直接删除掉104查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。 / 哈希表每个空间给个标记 // EMPTY此位置空 EXIST此位置已经有元素 DELETE元素已经删除 enum State{EMPTY, EXIST, DELETE}; 线性探测实现
规定:表格中元素唯一 线性探测:表格中的元素一定不会存满-----随着元素不断增多产生哈希冲突的概率就急剧增加
#includeiostream
using namespace std;
#includevector
enum State{ EMPTY, EXIST, DELETE };
templateclass T
class hashtable
{struct Elem //存储的元素类型{ Elem():_state(EMPTY){}T _data;State _state;};
public:hashtable(size_t capacity):_table(capacity), _size(0){}bool Insert(const Tdata){//检测哈希空间是否充足_CheckCapacity();//1.通过哈希函数计算哈希地址size_t hashAddr HashFunc(data);//2.检测位置是否可以存储while(_table[hashAddr]._state ! EMPTY){//检测该位置元素是否有效是否为待插入元素if (EXIST _table[hashAddr]._statedata _table[hashAddr]._data){return false;//元素已经存在不进行插入}//发生哈希冲突hashAddr;if (hashAddr _table.capacity())//如果地址越界了把地址放回0hashAddr 0;}//3.插入元素_table[hashAddr]._data data;_table[hashAddr]._state EXIST;_size;return true;}int Find(const Tdata){size_t hashAddr HashFunc(data);while (_table[hashAddr]._state ! EMPTY){if (EXIST _table[hashAddr]._statedata _table[hashAddr]._data){return hashAddr;}//发生哈希冲突hashAddr;if (hashAddr _table.capacity())hashAddr 0;}return -1;}bool Erase(const Tdata){int ret Find(data);if (-1 ! ret){_table[ret]._state DELETE;--_size;return true;}return false;}size_t Size()const{return _size;}
private:size_t HashFunc(const Tdata){return data%_table.capacity();}
private:vectorElem_table; //状态表格size_t _size;
};哈希算法
什么时候增容
哈希的负载因子 哈希负载因子 有效元素个数/哈希表的容量 哈希因子越小产生冲突的概率越低 负载因子控制在0.7左右性能就还可以 负载因子达到0.7就需要进行扩容 扩容
void Swap(hashtableT ht){_table.swap(ht._table);swap(_size, ht._size);swap(_total, ht._total);}
//扩容
void _CheckCapacity()
{if (_total * 10 / _table.capacity() 7){//新的哈希表hashtableTnewHT(_table.capacity() * 2);//奖旧哈希表中有效元素搬移到新的哈希表中//注意:已经删除的元素不用搬移for (size_t i 0; i _table.capacity(); i){if (_table[i]._data EXIST)newHT.Insert(_table[i]._data);}Swap(newHT);}
}线性探测缺陷
容易产生数据的堆积-----产生冲突的元素全部集中在一起一但产生冲突可能会引起一连串的冲突解决方法:二次探测
二次探测
线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为H(i) ( H(0)i2 )% m,或者H(i) (H(0) -i2 )% m。其中i 1,2,3… 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置m是表的大小。(i代表第几次探测)
代码实现
enum State{ EMPTY, EXIST, DELETE };
templateclass T, bool IsLine true
class hashtable
{struct Elem //存储的元素类型{ Elem():_state(EMPTY){}T _data;State _state;};
public:hashtable(size_t capacity):_table(capacity), _size(0),_total(0){}bool Insert(const Tdata){//检测哈希空间是否充足_CheckCapacity();//1.通过哈希函数计算哈希地址size_t hashAddr HashFunc(data);size_t i 0;//二次探测中的第几次探测//2.检测位置是否可以存储while(_table[hashAddr]._state ! EMPTY){//检测该位置元素是否有效是否为待插入元素if (EXIST _table[hashAddr]._statedata _table[hashAddr]._data){return false;//元素已经存在不进行插入}//发生哈希冲突if (IsLine){DetectiveLine(hashAddr);}else{i;DetectiveTwice(hashAddr,i);}}//3.插入元素_table[hashAddr]._data data;_table[hashAddr]._state EXIST;_size;_total;return true;}int Find(const Tdata){size_t hashAddr HashFunc(data);size_t i 0;while (_table[hashAddr]._state ! EMPTY){if (EXIST _table[hashAddr]._statedata _table[hashAddr]._data){return hashAddr;}//发生哈希冲突if (IsLine){DetectiveLine(hashAddr);}else{i;DetectiveTwice(hashAddr,i);}}return -1;}bool Erase(const Tdata){int ret Find(data);if (-1 ! ret){_table[ret]._state DELETE;--_size;return true;}return false;}size_t Size()const{return _size;}void Swap(hashtableT,IsLine ht){_table.swap(ht._table);swap(_size, ht._size);swap(_total, ht._total);}
private:size_t HashFunc(const Tdata){return data%_table.capacity();}//线性探测void DetectiveLine(size_thashAddr){hashAddr 1;if (hashAddr _table.capacity())hashAddr 0;}//二次探测void DetectiveTwice(size_t hashAddr, size_t i){hashAddr hashAddr 2 * i 1;if (hashAddr _table.capacity())hashAddr % _table.capacity();}//扩容void _CheckCapacity(){if (_total * 10 / _table.capacity() 7){//新的哈希表hashtableT,IsLinenewHT(_table.capacity() * 2);//奖旧哈希表中有效元素搬移到新的哈希表中//注意:已经删除的元素不用搬移for (size_t i 0; i _table.capacity(); i){if (_table[i]._data EXIST)newHT.Insert(_table[i]._data);}Swap(newHT);}}
private:vectorElem_table; //状态表格size_t _size; //哈希表中有效元素的个数size_t _total; //哈希表中元素的个数:存在和删除(为了保证哈希表中数据的唯一性删除位置不能插入元素)
};研究表明当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表装满的情况但在插入时必须确保表的装载因子a不超过0.5如果超出必须考虑增容
闭散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷。
开散列
开散列概念
开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码 归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。每个链表中保存发生哈希冲突的元素
代码实现
//开散列:一个链表的集合---产生相同哈希地址的元素放到同一个链表里
#includevector
//哈希表的结点
templateclass T
struct HashNode
{HashNode(const Tdata T()):_pNext(nullptr), _data(data){}HashNodeT* _pNext;T _data;
};templateclass T
class hashbucket
{typedef HashNodeT Node;
public:hashbucket(size_t capacity):_table(capacity), _size(0){}~hashbucket(){Clear();}bool Insert(const T data){//扩容_CheckCapacity();//通过哈希函数计算哈希的桶号size_t bucketNo HashFunc(data);Node* pCur _table[bucketNo];while (pCur){if (data pCur-_data)return false;pCur pCur-_pNext;}pCur new Node(data);pCur-_pNext _table[bucketNo];_table[bucketNo] pCur;_size;return true;}bool Erase(const Tdata){//先找在哪个链表size_t bucketNo HashFunc(data);//在链表中找元素Node* pCur _table[bucketNo];Node* pPrev nullptr;while (pCur){if (data pCur-_data){//可以删除if (pCur _table[bucketNo])_table[bucketNo] pCur-_pNext;elsepPrev-_pNext pCur-_pNext;delete pCur;--_size;return true;}else{pPrev pCur;pCur pCur-_pNext;}}return false;}Node* Find(const T data){size_t bucketNo HashFunc(data);Node* pCur _table[bucketNo];while (pCur){if (pCur-_data data)return pCur;pCur pCur-_pNext;}return nullptr;}size_t Size()const{return _size;}bool Empty()const{return 0 _size;}void Clear(){for (size_t bucketNo 0; bucketNo _table.capacity(); bucketNo){Node* pCur _table[bucketNo];while (pCur){_table[bucketNo] pCur-_pNext;delete pCur;pCur _table[bucketNo];}}}/*void _CheckCapacity(){if (_size _table.capacity())}*///打印函数void PrintHashBucket(){for (int i 0; i _table.capacity(); i){Node* pCur _table[i];cout table[ i ]:;while (pCur){cout pCur-_data --;pCur pCur-_pNext;}cout NULL endl;}}
private:size_t HashFunc(const Tdata){//T:可以是任意类型---可能不是整型return data % _table.capacity();}
private:vectorNode* _table;//每一个链表的首地址size_t _size; //当前哈希桶里放了多少个元素
};开散列的增容 桶的个数是一定的随着元素的不断插入每个桶中元素的个数不断增多极端情况下可能会导致一个桶中链表节点非常多会影响的哈希表的性能因此在一定条件下需要对哈希表进行增容那该条件怎么确认呢开散列最好的情况是每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可以给哈希表增容。 将旧哈希桶里的结点直接向新哈希桶里进行搬移在新哈希桶里不要创建新的结点
void Swap(hashbucketT ht)
{_table.swap(ht._table);swap(_size, ht._size);
}
void _CheckCapacity()
{if (_size _table.capacity()){//新的哈希桶hashbucketT newHT(_table.capacity() * 2);//将旧哈希桶中的结点往新哈希桶中进行搬移for (size_t i 0; i _table.capacity(); i){Node* pCur _table[i];//将i号桶中的所有结点搬移到新哈希桶中while (pCur){//将pCur结点从table的i号移除掉_table[i] pCur-_pNext;//将pCur插入到新哈希桶中size_t bucketNo newHT.HashFunc(pCur-_data);//采用头插法pCur-_pNext newHT._table[bucketNo];newHT._table[bucketNo] pCur;newHT._size;_size--;pCur _table[i];}}//新桶和旧桶进行交换this-Swap(newHT);}
}哈希表只能存储int类型的元素如何实现任意类型
templateclass T
struct HashNode
{HashNode(const Tdata T()):_pNext(nullptr), _data(data){}HashNodeT* _pNext;T _data;
};templateclass T
struct DefD2INIT
{const T operator()(const T data){return data;}
};struct Str2INT
{size_t operator()(const string s){stringstream ss;ss s;size_t ret;ss ret;return ret;}
};
templateclass T,class DTOINT DefD2INITT
class hashbucket
{typedef HashNodeT Node;typedef hashbucketT, DTOINT Self;
public:hashbucket(size_t capacity):_table(capacity), _size(0){}~hashbucket(){Clear();}bool Insert(const T data){//扩容_CheckCapacity();//通过哈希函数计算哈希的桶号size_t bucketNo HashFunc(data);Node* pCur _table[bucketNo];while (pCur){if (data pCur-_data)return false;pCur pCur-_pNext;}pCur new Node(data);pCur-_pNext _table[bucketNo];_table[bucketNo] pCur;_size;return true;}bool Erase(const Tdata){//先找在哪个链表size_t bucketNo HashFunc(data);//在链表中找元素Node* pCur _table[bucketNo];Node* pPrev nullptr;while (pCur){if (data pCur-_data){//可以删除if (pCur _table[bucketNo])_table[bucketNo] pCur-_pNext;elsepPrev-_pNext pCur-_pNext;delete pCur;--_size;return true;}else{pPrev pCur;pCur pCur-_pNext;}}return false;}Node* Find(const T data){size_t bucketNo HashFunc(data);Node* pCur _table[bucketNo];while (pCur){if (pCur-_data data)return pCur;pCur pCur-_pNext;}return nullptr;}size_t Size()const{return _size;}bool Empty()const{return 0 _size;}void Clear(){for (size_t bucketNo 0; bucketNo _table.capacity(); bucketNo){Node* pCur _table[bucketNo];while (pCur){_table[bucketNo] pCur-_pNext;delete pCur;pCur _table[bucketNo];}}}void Swap( Self ht){_table.swap(ht._table);swap(_size, ht._size);}void _CheckCapacity(){if (_size _table.capacity()){//新的哈希桶Self newHT(_table.capacity() * 2);//将旧哈希桶中的结点往新哈希桶中进行搬移for (size_t i 0; i _table.capacity(); i){Node* pCur _table[i];//将i号桶中的所有结点搬移到新哈希桶中while (pCur){//将pCur结点从table的i号移除掉_table[i] pCur-_pNext;//将pCur插入到新哈希桶中size_t bucketNo newHT.HashFunc(pCur-_data);//采用头插法pCur-_pNext newHT._table[bucketNo];newHT._table[bucketNo] pCur;newHT._size;_size--;pCur _table[i];}}//新桶和旧桶进行交换this-Swap(newHT);}}void PrintHashBucket(){for (int i 0; i _table.capacity(); i){Node* pCur _table[i];cout table[ i ]:;while (pCur){cout pCur-_data --;pCur pCur-_pNext;}cout NULL endl;}}
private:size_t HashFunc(const Tdata){//T:可以是任意类型---可能不是整型return DTOINT ()(data) % _table.capacity();}
private:vectorNode* _table;//每一个链表的首地址size_t _size; //当前哈希桶里放了多少个元素
};除留余数法最好模一个素数如何每次快速取一个类似两倍关系的素数
//素数表以递进两倍方式给出
const int PRIMECOUNT 28;
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 GetNextPrime(size_t prime)
{size_t i 0;for (; i PRIMECOUNT; i){//当前素数大于提供的素数if (primeList[i] prime)//返回return primeList[i];}//返回最后一个return primeList[PRIMECOUNT - 1];
}开散列与闭散列比较
应用链地址法处理溢出需要增设链接指针似乎增加了存储开销。事实上 由于开地址法必须保持大量的空闲空间以确保搜索效率如二次探查法要求装载因子a 0.7而表项所占空间又比指针大的多所以使用链地址法反而比开地址法节省存储空间。
