首先是hash_map聲明 [cpp] template<class _Kty, class _Ty, class _Tr = hash_compare<_Kty, less<_Kty> >, class _Alloc = allocator<pair<const _Kty, _Ty> > > class hash_map : public _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, false> > 後面是_Hash的內容概要。 其存儲結構： 一個std::list用來存儲Pair數據， 一個Vector用來存儲_Hash的Bucket信息(Bucket Begin和Bucket End. 其實就是list裡面的iterator。）一個Bucket的數據是在list裡面的連續的一段，順序存儲。判定方式通過less方法類來判定。 _Mask是當前索引的掩碼 _Maxidx:是當前的索引個數，或者說是Bucket個數。_Mask = _Maxidx - 1; _Max_bucket_size:當前的Hash表的負載率。默認是1.0。也就是當前的List.size() / _Maxidx如果比該值大就會進行Hash表擴容。這是一個很耗時的過程。 [cpp] // TEMPLATE CLASS _Hash template<class _Traits> class _Hash : public _Traits // traits serves as base class { typedef list<typename _Traits::value_type, typename _Traits::allocator_type> _Mylist; typedef vector<iterator, typename allocator_type::template rebind<iterator>::other> _Myvec; ... _Mylist _List; // list of elements, must initialize before _Vec _Myvec _Vec; // vector of list iterators, begin() then end()-1 size_type _Mask; // the key mask size_type _Maxidx; // current maximum key value float _Max_bucket_size; // current maximum bucket size } 接著看看Hash數據的插入過程 [cpp] // 如果插入的是已經存在key的內容，則插入失敗，返回已有的key的內容 _Pairib _Insert(const value_type& _Val, iterator _Plist) { // try to insert existing node with value _Val // 計算Hash Index的過程。裡面使用了comp的operator()操作 size_type _Bucket = _Hashval(this->_Kfn(_Val)); // 獲取Bucket的結束指針。第一個元素的時候會_Begin(_Bucket)和_End(_Bucket)內容相同 iterator _Where = _End(_Bucket); // 這個線性算法保證在同一個bucket的內容是從小到大。 // 選擇一個where使得當前元素插入在where之前 for (; _Where != _Begin(_Bucket); ) if (this->comp(this->_Kfn(_Val), this->_Kfn(*--_Where))) ; // still too high in bucket list // 如果key比較小，就繼續往前推算，直到Begin else if (_Multi || this->comp(this->_Kfn(*_Where), this->_Kfn(_Val))) { // found insertion point, back up to it // 當前key比where的key要大或者等，則選擇where的後面插入 ++_Where; break; } else { // discard new list element and return existing // Key完全相等，丟棄 _List.erase(_Plist); return (_Pairib(_Where, false)); } // List的當前插入數據的iterator. 對於vector和list進行了插入刪除等操作，其他元素的iterator仍然有效 iterator _Next = _Plist; // 如果where正好在當前元素之後，無需進行順序調整 if (_Where != ++_Next) // 不知道為什麼使用_Splice_same而不是用splice _List._Splice_same(_Where, _List, _Plist, _Next, 1); // move element into place // 進行桶數據修正 _Insert_bucket(_Plist, _Where, _Bucket); // 進行桶擴容 _Check_size(); // 返回當前的映射數據 return (_Pairib(_Plist, true)); // return iterator for new element } Hash索引計算算法： [cpp] // 計算實際key的過程 size_type _Hashval(const key_type& _Keyval) const { // return hash value, masked and wrapped to current table size size_type _Num = this->comp(_Keyval) & _Mask; if (_Maxidx <= _Num) _Num -= (_Mask >> 1) + 1; return (_Num); } _Hash的vector管理過程 [cpp] void _Insert_bucket(iterator _Plist, iterator _Where, size_type _Bucket) { // fix iterators after inserting _Plist before _Where if (_Vec_lo(_Bucket) == end()) // 插入空桶 { // make bucket non-empty _Vec_lo(_Bucket) = _Plist; _Vec_hi(_Bucket) = _Plist; } else if (_Vec_lo(_Bucket) == _Where) // 元素插到桶頭 _Vec_lo(_Bucket) = _Plist; // move beginning back one element else if (++_Vec_hi(_Bucket) != _Plist) // move end up one element // 如果插入到桶尾，則直接把桶尾++ // 否則則桶尾恢復 --_Vec_hi(_Bucket); // or not } 表擴充流程，其實就是所有當前元素的重新插入過程： [cpp] // 進行表擴充 void _Check_size() { // grow table as needed if (max_load_factor() < load_factor()) #if _HAS_INCREMENTAL_HASH _Grow(); // too dense, need to grow hash table #else /* _HAS_INCREMENTAL_www.2cto.comHASH */ { // rehash to bigger table max_size() / 2; size_type _Newsize = bucket_count(); for (int _Idx = 0; _Idx < 3 && _Newsize < _Maxsize; ++_Idx) _Newsize *= 2; // multiply safely by 8 _Init(_Newsize); _Reinsert(end()); } #endif /* _HAS_INCREMENTAL_HASH */ }
