首先是hash_map声明
[cpp]
template
class _Ty,
class _Tr = hash_compare<_Kty, less<_Kty> >,
class _Alloc = allocator > >
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 _Hash
: public _Traits // traits serves as base class
{
typedef list
typename _Traits::allocator_type> _Mylist;
typedef vector
typename allocator_type::template
rebind::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 _Whe