unordered_map模拟实现

1 哈希表的改造

1. 模板参数列表的改造

// K:关键码类型
// V: 不同容器V的类型不同，如果是unordered_map，V代表一个键值对，如果是unordered_set,V 为 K
 // KeyOfValue: 因为V的类型不同，通过value取key的方式就不同，详细见unordered_map/set的实现
// HF: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模
template<class K, class V, class KeyOfValue, class HF = DefHashF<T> >
 class HashBucket;

2. 增加迭代器操作

// 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，
template<class K, class V, class KeyOfValue, class HF>
 class HashBucket;
 // 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
template <class K, class V, class KeyOfValue, class HF>
 struct HBIterator 
{
 typedef HashBucket<K, V, KeyOfValue, HF> HashBucket;
 typedef HashBucketNode<V>* PNode;
 typedef HBIterator<K, V, KeyOfValue, HF> Self;
 HBIterator(PNode pNode = nullptr, HashBucket* pHt = nullptr);
 Self& operator++()
 {
 // 当前迭代器所指节点后还有节点时直接取其下一个节点
if (_pNode->_pNext)
 _pNode = _pNode->_pNext;
 else
 {
 // 找下一个不空的桶，返回该桶中第一个节点
size_t bucketNo = _pHt->HashFunc(KeyOfValue()(_pNode
>_data))+1;
 for (; bucketNo < _pHt->BucketCount(); ++bucketNo)
 {
 if (_pNode = _pHt->_ht[bucketNo])
 break;
 }
 }
return *this;
 }
 Self operator++(int);
 V& operator*();
 V* operator->();
 bool operator==(const Self& it) const;
 bool operator!=(const Self& it) const;
 PNode _pNode;             // 当前迭代器关联的节点
HashBucket* _pHt;         // 哈希桶--主要是为了找下一个空桶时候方便
};

3. 增加通过key获取value操作 

template<class K, class V, class KeyOfValue, class HF = DefHashF<T> >
 class HashBucket
 {
 friend HBIterator<K, V, KeyOfValue, HF>;
 // ......
 public:
 typedef HBIterator<K, V, KeyOfValue, HF> Iterator;
 //
 // ...
 // 迭代器
Iterator Begin()
 {
 size_t bucketNo = 0;
 for (; bucketNo < _ht.capacity(); ++bucketNo)
 {
 if (_ht[bucketNo])
 break;
 }
 if (bucketNo < _ht.capacity())
 return Iterator(_ht[bucketNo], this);
 else
 return Iterator(nullptr, this);
 Iterator End(){ return Iterator(nullptr, this);}
 Iterator Find(const K& key);
 Iterator Insert(const V& data);
 Iterator Erase(const K& key);
 // 为key的元素在桶中的个数
size_t Count(const K& key)
 {
 if(Find(key) != End())
 return 1;
 return 0;
}
 size_t BucketCount()const{ return _ht.capacity();}
 size_t BucketSize(size_t bucketNo)
    {
 size_t count = 0;
PNode pCur = _ht[bucketNo];
 while(pCur)
        {
 count++;
 pCur = pCur->_pNext;
        }
 return count;
    }
 // ......
 };

2 unordered_map 

// unordered_map中存储的是pair<K, V>的键值对，K为key的类型，V为value的类型，HF哈希
函数类型
// unordered_map在实现时，只需将hashbucket中的接口重新封装即可
template<class K, class V, class HF = DefHashF<K>>
 class unordered_map
 {
 typedef pair<K, V> ValueType;
 typedef HashBucket<K, ValueType, KeyOfValue, HF> HT;
 // 通过key获取value的操作
struct KeyOfValue
 {
 const K& operator()(const ValueType& data)
 { return data.first;}
 };
 public:
 typename typedef HT::Iterator iterator;
 public:
 unordered_map(): _ht()
 {}
 
 iterator begin(){ return _ht.Begin();}
 iterator end(){ return _ht.End();}
 
 // capacity
 size_t size()const{ return _ht.Size();}
 bool empty()const{return _ht.Empty();}
 ///
 // Acess
 V& operator[](const K& key)
 {
 return (*(_ht.InsertUnique(ValueType(key, V())).first)).second;
 }
 const V& operator[](const K& key)const;
 //
 // lookup
 iterator find(const K& key){ return _ht.Find(key);}
 size_t count(const K& key){ return _ht.Count(key);}
 /
 // modify
 pair<iterator, bool> insert(const ValueType& valye)
 { return _ht.Insert(valye);}
iterator erase(iterator position)
 { return _ht.Erase(position);}
 
 // bucket
 size_t bucket_count(){ return _ht.BucketCount();}
 size_t bucket_size(const K& key){ return _ht.BucketSize(key);}
 private:
 HT _ht;
 };