做網(wǎng)站能設(shè)置關(guān)鍵詞在百度中搜索到百度站長收錄入口
哈希學(xué)習(xí)
- unordered系列關(guān)聯(lián)式容器
- 哈希結(jié)構(gòu)
- 除留余數(shù)法
- 哈希沖突
- 閉散列
- 線性探測
- 二次探測
- 負(fù)載因子
- 開散列
- 開散列增容
- 閉散列 VS 開散列
- 字符串哈希算法
- 線性探測 & 二次探測實(shí)現(xiàn)
- 拉鏈法實(shí)現(xiàn)
unordered系列關(guān)聯(lián)式容器
unordered系列關(guān)聯(lián)式容器是從C++11開始,STL提供的。它的查詢效率要更優(yōu)于set/map類型關(guān)聯(lián)式容器。
unordered系列容器的名字是從功能角度來取定的。set/map這類容器,其遍歷是有序的,而unordered系列容器的遍歷則是無序的。
從底層角度來看,set/map類容器底層采用紅黑樹實(shí)現(xiàn),而unordered系列容器則是采用的哈希結(jié)構(gòu)。同時(shí),map/set的迭代器是雙向的,而unordered系列容器是單向的。
unordered系列容器的使用可以參考set/map的使用【C++】set & map的使用,它們的使用方式大多是類似的。
哈希結(jié)構(gòu)
哈希,也叫散列,是一種值與存儲位置之間建立映射關(guān)聯(lián)的結(jié)構(gòu)。
哈希結(jié)構(gòu)通過哈希函數(shù)(Hash)使元素的關(guān)鍵碼與存儲位置之間建立一一映射的關(guān)系。當(dāng)插入元素時(shí),由元素的關(guān)鍵碼,根據(jù)哈希函數(shù)計(jì)算出元素的存儲位置進(jìn)行存放;當(dāng)查找刪除元素時(shí),也是同樣的計(jì)算過程。
除留余數(shù)法
哈希函數(shù)有很多種,本文中使用的哈希函數(shù)為除留余數(shù)法。
設(shè)哈希表中允許存放的位置個(gè)數(shù)為n,取一個(gè)小于等于n的最大質(zhì)數(shù)p作為除數(shù),按照哈希函數(shù):Hash(key) = key % p
,通過計(jì)算將關(guān)鍵碼轉(zhuǎn)換成哈希表中對應(yīng)的地址。
哈希沖突
當(dāng)哈希表中存放的數(shù)據(jù)越來越多,必然會出現(xiàn)不同的key通過相同哈希函數(shù)的計(jì)算,出現(xiàn)相同地址的情況,即哈希沖突,或哈希碰撞。
哈希沖突的解決有兩種常見方式:閉散列和開散列。
閉散列
閉散列,也叫開放定址法。當(dāng)發(fā)生哈希沖突時(shí),如果哈希表未被填滿,也就是還存在空位置,那么可以把關(guān)鍵碼key的元素存放到?jīng)_突位置的“下一個(gè)”空位置去。
線性探測
線性探測:從發(fā)生沖突的位置開始,依次向后探測,直到找到一個(gè)空位置為止。
線性探測的插入分兩種情況:
- 通過哈希函數(shù)計(jì)算待插入元素的位置,如果該位置沒有元素,即直接插入新元素;
- 如果該位置有元素,發(fā)生哈希沖突,使用線性探測找到空位置,再插入新元素。
線性探測的查找和刪除的處理需要額外引入對元素delete
的狀態(tài)標(biāo)記。
enum State{EMPTY, EXIST, DELETE};
假如哈希表中存在發(fā)生哈希沖突的兩個(gè)元素,這兩個(gè)元素位置一前一后,狀態(tài)都為EXIST
。如果在前面的元素被刪除了,該位置狀態(tài)直接被置為EMPTY
,此時(shí)再去找位于后面的元素,就會發(fā)生找不到的情況。因?yàn)閷ふ业慕K止條件就是遇到空EMPTY
結(jié)束。所以,通過DELETE
標(biāo)記的引入,使得前面元素的刪除不會影響到后面的元素。
線性探測實(shí)現(xiàn)起來會比較簡單。但是一旦發(fā)生哈希沖突,可能會相互作用,不斷擴(kuò)大沖突的范圍,使得找一個(gè)關(guān)鍵碼的位置需要比較很多次,從而導(dǎo)致效率的下降。
二次探測
二次探測是對線性探測缺陷的一種改進(jìn),但本質(zhì)上還是沒有完全解決哈希沖突問題。
如果說線性探測的“下一個(gè)”位置可以用 H a s h ( k e y ) + i ( i > = 0 ) Hash(key) +i(i>=0) Hash(key)+i(i>=0)表示,那么在二次探測中,“下一個(gè)”位置的表示就是 H a s h ( k e y ) + i 2 Hash(key) + i^2 Hash(key)+i2 或者 H a s h ( k e y ) ? i 2 Hash(key) - i^2 Hash(key)?i2。
負(fù)載因子
其實(shí)還可以通過擴(kuò)容來降低哈希沖突發(fā)生的概率。
哈希表的負(fù)載因子 α = 填入表中的元素個(gè)數(shù) 哈希表的長度 ( 地址個(gè)數(shù) ) \alpha = \dfrac{填入表中的元素個(gè)數(shù)}{哈希表的長度(地址個(gè)數(shù))} α=哈希表的長度(地址個(gè)數(shù))填入表中的元素個(gè)數(shù)?。
α \alpha α是哈希表填充程度的衡量因子。因?yàn)楸黹L是定值,所以 α \alpha α與“填入表中的元素個(gè)數(shù)”成正比。所以, α \alpha α越大,表明填入表中的元素越多,沖突概率也越大;反之, α \alpha α越小,表明填入表中的元素越少,沖突概率也越小。對于閉散列(開放定址法),應(yīng)嚴(yán)格限制 α \alpha α在0.7 - 0.8
。
閉散列最大的缺陷就是空間利用率比較低了,這同時(shí)也是哈希的缺陷。
開散列
開散列,也叫拉鏈法。首先同樣是通過哈希函數(shù)計(jì)算關(guān)鍵碼的地址,不同的地方是它將具有相同地址的關(guān)鍵碼元素歸于同一子集合,每一個(gè)子集合稱為一個(gè)桶,各個(gè)桶中的元素通過一個(gè)單鏈表連接起來,哈希表中存儲各鏈表的頭節(jié)點(diǎn)指針。
所以,開散列中每個(gè)桶存放的都是發(fā)生哈希沖突的元素。
開散列增容
開散列最好的情況是:每個(gè)哈希桶中剛好掛一個(gè)節(jié)點(diǎn)。然后再繼續(xù)插入元素時(shí),每一次都會發(fā)生哈希沖突。
因此,在元素個(gè)數(shù)剛好等于桶的個(gè)數(shù),再插入時(shí),可以給哈希表增容。
閉散列 VS 開散列
使用開散列處理哈希沖突,需要增設(shè)鏈接指針,似乎增加了存儲開銷。而閉散列需要預(yù)留大量的空閑空間來確保效率,一般表項(xiàng)所占空間有比指針大的多,所以使用開散列反而會比閉散列節(jié)省空間。
字符串哈希算法
如果關(guān)鍵碼key不為整型,比如為字符串類型,又該如何映射其地址呢?
首先當(dāng)然是將字符串轉(zhuǎn)為整形再做運(yùn)算,對于如何轉(zhuǎn)換的問題可以參考BYVoid大佬的這篇關(guān)于字符串哈希算法的文章各種字符串Hash函數(shù)比較,里面給出了各種哈希算法的源碼實(shí)現(xiàn),并對各種算法的性能做了分?jǐn)?shù)排名。
Hash函數(shù) | 數(shù)據(jù)1 | 數(shù)據(jù)2 | 數(shù)據(jù)3 | 數(shù)據(jù)4 | 數(shù)據(jù)1得分 | 數(shù)據(jù)2得分 | 數(shù)據(jù)3得分 | 數(shù)據(jù)4得分 | 平均分 |
---|---|---|---|---|---|---|---|---|---|
BKDRHash | 2 | 0 | 4774 | 481 | 96.55 | 100 | 90.95 | 82.05 | 92.64 |
APHash | 2 | 3 | 4754 | 493 | 96.55 | 88.46 | 100 | 51.28 | 86.28 |
DJBHash | 2 | 2 | 4975 | 474 | 96.55 | 92.31 | 0 | 100 | 83.43 |
JSHash | 1 | 4 | 4761 | 506 | 100 | 84.62 | 96.83 | 17.95 | 81.94 |
RSHash | 1 | 0 | 4861 | 505 | 100 | 100 | 51.58 | 20.51 | 75.96 |
SDBMHash | 3 | 2 | 4849 | 504 | 93.1 | 92.31 | 57.01 | 23.08 | 72.41 |
PJWHash | 30 | 26 | 4878 | 513 | 0 | 0 | 43.89 | 0 | 21.95 |
ELFHash | 30 | 26 | 4878 | 513 | 0 | 0 | 43.89 | 0 | 21.95 |
線性探測 & 二次探測實(shí)現(xiàn)
template<class K>
class Hash
{
public:// 整形直接返回size_t operator()(const K& key){return (size_t)key;}
};template<>
class Hash<string>
{
public:// string類型 -- BKDRHashsize_t operator()(const string& key){size_t hash = 0;for (char c : key){hash *= 131;hash += c;}// 裝成整形返回return hash;}
};
// 閉散列
namespace CloseHash
{// 標(biāo)記哈希表表項(xiàng)的狀態(tài)enum State{EMPTY,EXIST,DELETE};// 哈希表表項(xiàng)的類型template<class K, class V>class HashNode{public:pair<K, V> _kv; // 要存儲的元素State _state = EMPTY;};// 哈希表的實(shí)現(xiàn)template<class K, class V, class Hash = Hash<K>>class HashTable{public:// 插入bool Insert(const pair<K, V>& kv){// 找到了,返回false,插入失敗if (Find(kv.first))return false;// 先檢查擴(kuò)容 -- 負(fù)載因子到0.7就擴(kuò)容if (_table.size() == 0 || 10 * _size / _table.size() >= 7){size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;HashTable<K, V, Hash> newHT;newHT._table.resize(newSize);// 舊表數(shù)據(jù)映射到新表for (auto e : _table){if (e._state == EXIST){// 復(fù)用Insert()newHT.Insert(e._kv);}}// 交換_table.swap(newHT._table);}// 線性探測Hash hash;// key轉(zhuǎn)整形 -> 除留余數(shù)法size_t hashi = hash(kv.first) % _table.size();while (_table[hashi]._state == EXIST){++hashi;hashi %= _table.size();}_table[hashi]._kv = kv;_table[hashi]._state = EXIST;++_size;return true;}// 刪除bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){// 將狀態(tài)標(biāo)記成DELETE即可ret->_state = DELETE;--_size;return true;}return false;}// 查找HashData<K, V>* Find(const K& key){if (_table.empty()){return nullptr;}Hash hash;size_t start = hash(key) % _table.size();size_t hashi = start;while (_table[hashi]._state != EMPTY){if (_table[hashi]._kv.first == key && _table[hashi]._state != DELETE){return &_table[hashi];}++hashi;hashi %= _table.size();if (hashi == start){break;}}return nullptr;}private:vector<HashNode<K, V>> _table;size_t _size = 0; // 存儲有效數(shù)據(jù)的個(gè)數(shù)};
}
// 二次探測
// 只需要將Insert()中的線性探測部分替換成下面的二次探測即可
Hash hash;
size_t start = hash(kv.first) % _table.size();
size_t i = 0;
size_t hashi = start;
while (_table[hashi]._state == EXIST)
{++i;hashi = start + i * i;hashi %= _table.size();
}_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_size;
拉鏈法實(shí)現(xiàn)
// 開散列
//namespace OpenHash
namespace HashBucket
{// 哈希節(jié)點(diǎn)的類型template<class K, class V>class HashNode{public:HashNode(const pair<K, V>& kv): _kv(kv), _next(nullptr){}pair<K, V> _kv; // 要存儲的元素HashNode<K, V>* _next;};template<class K, class V, class Hash = Hash<K>>class HashTable{private:typedef HashNode<K, V> Node;public:// 析構(gòu)~HashTable(){for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_table[i] = nullptr;}}// 引用STL源碼略做修改// 使哈希表每次擴(kuò)容的大小為素?cái)?shù)inline size_t __stl_next_prime(size_t n){static const size_t __stl_num_primes = 28;static const size_t __stl_prime_list[__stl_num_primes] ={53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};for (size_t i = 0; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > n){return __stl_prime_list[i];}}return 0; // 表示出錯(cuò)了}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}Hash hash;// 檢查擴(kuò)容if (_size == _table.size()){vector<Node*> newTable;newTable.resize(__stl_next_prime(_table.size()), nullptr);// 舊表中的節(jié)點(diǎn) 移動 映射到新表for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;// 鏈接到新表size_t hashi = hash(cur->_kv.first) % newTable.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_table[i] = nullptr;}// 交換_table.swap(newTable);}size_t hashi = hash(kv.first) % _table.size();// 頭插Node* newnode = new Node(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;++_size;return true;}bool Erase(const K& key){if (_table.empty()){return false;}Hash hash;size_t hashi = hash(key) % _table.size();Node* prev = nullptr;Node* cur = _table[hashi];while (cur){if (key == cur->_kv.first){// 頭刪if (prev == nullptr){_table[hashi] = cur->_next;}else // 其他位置刪除{prev->_next = cur->_next;}delete cur;--_size;return true;}prev = cur;cur = cur->_next;}return false;}Node* Find(const K& key){if (_table.empty()){return nullptr;}Hash hash;size_t hashi = hash(key) % _table.size();Node* cur = _table[hashi];// 去桶里面找while (cur){if (key == cur->_kv.first){return cur;}cur = cur->_next;}return nullptr;}// 返回有效數(shù)據(jù)個(gè)數(shù)size_t Size(){return _size;}// 表的長度(地址個(gè)數(shù))size_t TableSize(){return _table.size();}// 桶的個(gè)數(shù)size_t BucketNum(){size_t num = 0;for (size_t i = 0; i < _table.size(); ++i){if (_table[i]){++num;}}return num;}// 最大桶的節(jié)點(diǎn)個(gè)數(shù)size_t MaxBucket(){size_t maxLen = 0;for (size_t i = 0; i < _table.size(); ++i){size_t len = 0;Node* cur = _table[i];while (cur){++len;cur = cur->_next;}if (len > maxLen){maxLen = len;}}return maxLen;}private:vector<Node*> _table; // 哈希表存哈希節(jié)點(diǎn)的指針size_t _size = 0; // 存儲有效數(shù)據(jù)的個(gè)數(shù)};
}