VS2010 STL hashmap

 

首先是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;  

        }  

 

补充：软件开发 , C++ ,