#pragma once #include<iostream> #include<string> using namespace std; enum State { EMPTY, DELETE, EXIST, }; template<class K, class V> struct HashTableNode { K _key; V _value; }; template<class K> struct __HashFunc //默認(rèn)的返回哈希鍵值key的 仿函數(shù) { size_t operator()(const K& key) { return key; } }; //特化string的__HashFunc 仿函數(shù) template<> struct __HashFunc<string> { size_t operator()(const string& str) { size_t key = 0; for (size_t i = 0; i < str.size(); i++) { key += str[i]; } return key; } }; //實(shí)現(xiàn)哈希表的Key/Value形式的二次探測(cè) template<class K, class V, class HashFunc = __HashFunc<K>> class HashTable { typedef HashTableNode<K, V> Node; public: HashTable(size_t capacity = 10) :_tables(new Node[capacity]) , _size(0) , _states(new State[capacity]) , _capacity(capacity) { // memset 有問(wèn)題 是以字節(jié)為單位初始化的 但第二個(gè)參數(shù)值為int //memset(_states, EMPTY, sizeof(State) * capacity); for (size_t i = 0; i < capacity; i++) { _states[i] = EMPTY; } } ~HashTable() { if (NULL != _tables) { delete[] _tables; _tables = NULL; } if (NULL != _states) { delete[] _states; _states = NULL; } } bool Insert(const K& key, const V& value) { _CheckCapacity(); //用GetNextIndex 解決哈希沖突 size_t index = _HashFunc(key); // 二次探測(cè) size_t i = 1; while (_states[index] == EXIST) { index = _GetNextIndex(index, i++); if (index >= _capacity) { index = index % _capacity; } } _tables[index]._key = key; _tables[index]._value = value; _states[index] = EXIST; _size++; return true; } Node* Find(const K& key) { size_t index = _HashFunc(key); size_t start = index; size_t i = 1; // 存在 或者 被刪除 兩種狀態(tài) while (_states[index] != EMPTY) { if (_tables[index]._key == key) { if (_states[index] == EXIST) { return index; } else // 被刪除 DELETE { return -1; } } index = _GetNextIndex(index, i++); if (index >= _capacity) { index = index % _capacity; } // 因?yàn)橛刑畛湟蜃?nbsp;不為100% 不會(huì)出現(xiàn)全滿且key!=_key 導(dǎo)致死循環(huán)的情況 } return -1; } bool Remove(const K& key) { int index = Find(key); if (index != -1) { _states[index] = DELETE; --_size; return true; } return false; } // 二次探測(cè)計(jì)算出存放位置 size_t _HashFunc(const K& key) { HashFunc hf; return hf(key) % _capacity; // 仿函數(shù)hf() } // 哈希沖突時(shí) 得到下一個(gè)index的可以利用上一個(gè)index的值 這樣能提高效率 比如 string的index計(jì)算就比較費(fèi)時(shí) size_t _GetNextIndex(size_t prev, size_t i) { return prev + 2 * i - 1; } void Print() { for (size_t i = 0; i < _capacity; i++) { if (_states[i] == EXIST) { cout << i << "EXIST:" << _tables[i]._key << "-------" << _tables[i]._value << endl; } else if (_states[i] == DELETE) { cout << i << "DELETE:" << _tables[i]._key << "-------" << _tables[i]._value << endl; } else { cout << i << "EMPTY:" << _tables[i]._key << "-------" << _tables[i]._value << endl; } } } void Swap(HashTable<K, V, HashFunc>& ht) { swap(_size, ht._size); swap(_states, ht._states); swap(_tables, ht._tables); swap(_capacity, ht._capacity); } protected: void _CheckCapacity() // 擴(kuò)容 { // 動(dòng)態(tài)的 可擴(kuò)容的 // 高效哈希表的載荷因子大概在0.7-0.8較好 if (10 * _size / _capacity >= 7) // _size/_capacity為0 因?yàn)槎际恰痢痢?nbsp;所以乘10 // 保證載荷因子在0.7之內(nèi) { HashTable<K, V, HashFunc> tmp(2 * _capacity); for (size_t i = 0; i < _capacity; i++) { if (_states[i] == EXIST) { tmp.Insert(_tables[i]._key, _tables[i]._value); } } Swap(tmp); } } protected: Node* _tables; State* _states;//狀態(tài)表 size_t _size; size_t _capacity; };
創(chuàng)新互聯(lián)www.cdcxhl.cn,專(zhuān)業(yè)提供香港、美國(guó)云服務(wù)器,動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇,持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證, 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源,準(zhǔn)確進(jìn)行流量調(diào)度,確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開(kāi)啟,新人活動(dòng)云服務(wù)器買(mǎi)多久送多久。
成都創(chuàng)新互聯(lián)公司主打移動(dòng)網(wǎng)站、做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)、網(wǎng)站改版、網(wǎng)絡(luò)推廣、網(wǎng)站維護(hù)、域名申請(qǐng)、等互聯(lián)網(wǎng)信息服務(wù),為各行業(yè)提供服務(wù)。在技術(shù)實(shí)力的保障下,我們?yōu)榭蛻舫兄Z穩(wěn)定,放心的服務(wù),根據(jù)網(wǎng)站的內(nèi)容與功能再?zèng)Q定采用什么樣的設(shè)計(jì)。最后,要實(shí)現(xiàn)符合網(wǎng)站需求的內(nèi)容、功能與設(shè)計(jì),我們還會(huì)規(guī)劃穩(wěn)定安全的技術(shù)方案做保障。
當(dāng)前名稱(chēng):哈希表(散列表)二次探測(cè)-創(chuàng)新互聯(lián)
分享URL:http://muchs.cn/article18/djiodp.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供服務(wù)器托管、網(wǎng)站導(dǎo)航、ChatGPT、手機(jī)網(wǎng)站建設(shè)、電子商務(wù)、網(wǎng)站營(yíng)銷(xiāo)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容