寫在前面

???????順序結構以及平衡樹中，元素關鍵碼與其存儲位置之間沒有對應的關系，因此在查找一個元素時，必須要經過關鍵碼的多次比較。順序查找時間復雜度為O(N)，平衡樹中為樹的高度，即O( )，搜索的效率取決于搜索過程中元素的比較次數。
???????理想的搜索方法：可以不經過任何比較，一次直接從表中得到要搜索的元素。 如果構造一種存儲結構，通過某種函數(hashFunc)使元素的存儲位置與它的關鍵碼之間能夠建立一一映射的關系，那么在查找時通過該函數可以很快找到該元素。

當向該結構中：
插入元素

根據待插入元素的關鍵碼，以此函數計算出該元素的存儲位置并按此位置進行存放

搜索元素

對元素的關鍵碼進行同樣的計算，把求得的函數值當做元素的存儲位置，在結構中按此位置取元素比較，若關鍵碼相等，則搜索成功

該方式即為哈希(散列)方法，哈希方法中使用的轉換函數稱為哈希(散列)函數，構造出來的結構稱為哈希表(Hash Table)(或者稱散列表)

哈希沖突

對于兩個數據元素的關鍵字 和 (i != j)，有 != ，但有：Hash(i ) == Hash(j )， 即：不同關鍵字通過相同哈希哈數計算出相同的哈希地址，該種現象稱為哈希沖突或哈希碰撞.

把具有不同關鍵碼而具有相同哈希地址的數據元素稱為“同義詞”。

發生哈希沖突該如何處理呢？

哈希沖突解決

解決哈希沖突兩種常見的方法是：閉散列和開散列

1.閉散列的實現

閉散列：也叫開放定址法，當發生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置， 那么可以把key存放到沖突位置中的“下一個” 空位置中去。那如何尋找下一個空位置呢？

類的成員變量：

private:vector<elem> _ht;int _size; /enum state{empty,exist,deleted};typedef struct elem{pair<K, V> val;state sta;}elem; //1.閉散列 #include<map> #include<vector> #include<utility> #include<iostream> using namespace std;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 };enum state{empty,exist,deleted};template<class K,class V>class hash_1{typedef struct elem{pair<K, V> val;state sta;}elem;public:hash_1(int n = 3):_size(0), _ht(n){for (int i = 0; i < _ht.capacity(); ++i){_ht[i].sta = empty;}}bool insert(const K& key){check_capacity();size_t _hashaddr = hash_func(key);pair<K, V>_val = { key, _hashaddr }; //pair類型的變量初始化size_t _start = _hashaddr;while (_ht[_hashaddr].sta == exist){if (_ht[_hashaddr].sta == exist && _ht[_hashaddr].val.first == key)return false;_hashaddr++;if (_hashaddr == _ht.capacity())_hashaddr == 0;if (_hashaddr == _start)return false;}//如果為空，可以直接插入_ht[_hashaddr].val = _val;_ht[_hashaddr].sta = exist;++_size;return true;}void check_capacity(){//增容的條件是： α>=0.7if (_size*10/_ht.capacity()>=7){hash_1<K, V>newht(getnextprime(_ht.capacity()));for (int i = 0; i < _ht.capacity(); ++i){if (_ht[i].sta == exist){newht.insert(_ht[i].val.first);}}Swap(newht);}}int getnextprime(size_t n){for (int i = 0; i < PRIMECOUNT; ++i){if (primeList[i]>n)return primeList[i];}return 0;}int find(const K& key){//如果找到了，返回下標；沒有找到就打印“不存在”;int _hashaddr = hash_func(key);size_t start = _hashaddr;while ( _ht[_hashaddr].sta != empty ){if (_ht[_hashaddr].sta == exist && _ht[_hashaddr].val.first == key)return _hashaddr;++_hashaddr;if (_hashaddr == _ht.capacity()){_hashaddr = 0;}if (_hashaddr == start){cout << "不存在" << endl;return -1;}}cout << "不存在" << endl;return -1;}void erase(const K& key){int index = find(key);if (index != -1){_ht[index].sta = deleted;++_size;}return;}void Swap(hash_1<K, V>& ht){swap(_ht, ht._ht);swap(_size, ht._size);}private: size_t hash_func(const K& key){return key % _ht.capacity();}private:vector<elem> _ht;int _size;};

2.開散列的實現

開散列法又叫鏈地址法(開鏈法)，首先對關鍵碼集合用散列函數計算散列地址， 具有相同地址的關鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈表鏈接起來， 各鏈表的頭結點存儲在哈希表中。

類的成員變量：

private:vector<Node *> _ht; size_t _size; ///template<class v>struct node{node(const v& data):_val(data),_pnext(nullptr){}int _val;node<v>* _pnext;};typedef node<V> Node;typedef node* PNode; //哈希---開散列--哈希桶//開散列的實現template<class v>struct node{node(const v& data):_val(data),_pnext(nullptr){}int _val;node<v>* _pnext;};template<class V, class HF = DefHashF<T> > class HashBucket {typedef node<V> 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;//PNode pRet = nullptr;while (pCur!=nullptr && pCur->_val!=data){pPrev = pCur;pCur = pCur->_pnext;}//要刪除的節點不存在if (pCur == nullptr)return nullptr;//如果是頭刪if (pPrev == nullptr){ _ht[bucketNo] = pCur->_pnext;return _ht[bucketNo];}//數據存在，并且非首元素 pPrev->_pnext = pCur->_pnext;return pPrev->_pnext;}// 查找data是否在哈希桶中PNode Find(const V& data){size_t bucketNo = HashFunc(data);PNode pCur = _ht[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 < _ht.capacity(); ++bucketNo){PNode pCur = _ht[bucketNo];while (pCur){PNode pNext = pCur->_pNext;delete pCur;pCur = pNext;}}_size = 0;}bool BucketCount()const{return _ht.capacity();}void Swap(HashBucket<V, HF>& ht){swap(_ht, ht._ht);swap(_size, ht._size);}~HashBucket(){Clear();}/*桶的個數是一定的，隨著元素的不斷插入，每個桶中元素的個數不斷增多，極端情況下，可能會導致一個桶中鏈表節點非常多，會影響的哈希表的性能，因此在一定條件下需要對哈希表進行增容，那該條件怎么確認呢？開散列最好的情況是：每個哈希桶中剛好掛一個節點，再繼續插入元素時，每一次都會發生哈希沖突，因此，在元素個數剛好等于桶的個數時，可以給哈希表增容。*/void _CheckCapacity(){size_t bucketCount = BucketCount();if (_size == bucketCount){//增容HashBucket<V, HF> newHt(getnextprime(_ht.capacity()));for (int i = 0; i < newHt._ht.capacity; ++i)newHt._ht[i] = nullptr;for (int j = 0; j < _ht.capacity(); ++j){PNode cur = _ht[j];int hashNo = -1;while (cur){//取舊哈希桶i號桶的第一個節點_ht[j] = cur->_pnext; //頭刪//計算當前節點在新空間的桶號hashNo = newHt.HashFunc(cur->_val); //計算在那個哈希桶中//頭插法將該節點插入新空間cur->_pnext = newHt[hashNo];//連接新桶中的內容newHt[hashNo] = cur;//將給定的第一個節點放入新空間//取舊哈希桶i號桶的第next個節點cur = ht[j]//cur取原鏈表中的下一個節點}}}newHt._size = _size;this->Swap(newHt);}private:size_t HashFunc(const V& data){return HF()(data) % _ht.BucketCount();}private:vector<Node *> _ht; size_t _size; // 哈希表中有效元素的個數};

開散列與比散列比較：
應用鏈地址法處理溢出，需要增設鏈接指針，似乎增加了存儲開銷。事實上： 由于開地址法必須保持大量的空閑空間以確保搜索效率，如二次探查法要求裝載因子a <= 0.7，而表項所占空間又比指針大的多，所以使用鏈地址法反而比開地址法節省存儲空間。

總結

以上是生活随笔為你收集整理的数据结构学习——浅谈哈希表开散列和闭散列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。