哈希桶的实现

上一篇博客中介绍了用闭散列法的二次探测和开链法构造哈希表的原理即实现方式。
构造哈希表的闭散列法之二次探测地址：http://blog.csdn.net/qq_36221862/article/details/73488162

下面介绍另一种方法：
【开散列法】
开散列法又叫链地址法(开链法)。
开散列方法首先对关键码集合用某一个散列函数计算他们的存放位置。若设散列表地址空间的 所有位置是从0到m-1，则关键码集合中的所有关键码被划分为m个子集合，通过散列函数计算出来的 具有相同地址的关键码归于同一子集合。称同一子集合中的关键码互为同义词，每一个子集合称为 一个桶。通常各个桶中的表项通过一个单链表链接起来，亦称为同义词子表。所有桶号相同的表 项都链接在同一个同义词子表中，各链表的头结点组成一个向量，因此，向量的元素个数与可能 的桶数一致。桶号为i的同义词子表的表头结点是向量中的第i个元素。
设元素的关键码为37,25,14,36,49,68,57,11,散列表为HT[12]，表的大小为12，散列函数为Hash(x) = x % 11;(11是小于等于m接近m的质数) Hash(37)=4 Hash(25)=3 Hash(14)=3 Hash(36)=3 Hash(49)=5 Hash(68)=2 Hash(57)=2 Hash(11)=0
采用开散列法处理冲突：

哈希桶：哈希桶就是盛放不同key链表的容器（即是哈希表），在这里我们可以把每个key的位置看作是一个孔，孔里放了一个链表
相信大家可以看出来，使用一个数组来存放记录方法的哈希冲突太多，基于载荷因子的束缚，空间利用率不高，在需要节省空间的情况下，我们可以用哈希桶来处理哈希冲突。
哈希桶是使用一个顺序表来存放具有相同哈希值的key的链表的头节点，利用这个头节点可以找到其它的key

通常，每个桶中的同义词子表都很短，设有n个关键码通过某一个散列函数，存放到散列表中的m个桶 中，那么每一个桶中的同义词子表的平均长度为n/m。这样以搜索平均长度为n/m的同义词子表代替了 搜索长度为n的顺序表，搜索效率快的多。
应用链地址发处理溢出，需要增设链接指针，似乎增加了存储开销。事实上，由于开地址法必须保持 大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.5 而表项所占空间又比指针大 的多，所以使用链地址法反而比开地址法节省存储空间

代码如下：

HashBucket.cpp

template<class K, class V>
struct HashBucketNode
{
    pair<K, V> _kv;
    HashBucketNode<K, V>* _pNext;

    HashBucketNode(const K& key, const V& value)
        : _kv(pair<K,V>(key, value))
        , _pNext(NULL)
    {}
};

template<class K, class V>
class HashTable;

template<class K, class V, class Ref, class Ptr>
class _HashBucketIterator_
{
public:
    typedef _HashBucketIterator_<K, V, Ref, Ptr> Self;
    typedef HashBucketNode<K, V> Node;

public:
    _HashBucketIterator_()
        : _pNode(NULL)
        , _ht(NULL)
    {}

    _HashBucketIterator_(Node* pNode, HashTable<K, V>* ht)
        : _pNode(pNode)
        , _ht(ht)
    {}

    _HashBucketIterator_(const Self& it)
        : _pNode(it._pNode)
        , _ht(it._ht)
    {}

    Ref operator*()
    {
        return _pNode->_kv;
    }

    Ptr operator->()
    {
        return &(operator*());
    }

    Self& operator++()
    {
        _pNode = Next(_pNode);
        return *this;
    }

    Self operator++(int)
    {
        Self temp(*this);
        Next();
        return temp;
    }

    bool operator==(const Self& it)
    {
        return _pNode == it._pNode && _ht == it._ht;
    }

    bool operator!=(const Self& it)
    {
        return !(*this == it);
    }

private:
    Node* Next(Node* pNode)
    {
        Node* pNext  = pNode->_pNext;
        if(pNext)//如果下一个结点存在则返回它
        {
            return pNext;
        }
        else //否则找下一个不为空的桶
        {
            size_t BucketNo = _ht->_HashFun(_pNode->_kv.first)+1;
            size_t i = BucketNo;
            for( ;i<_ht->_table.size(); ++i)
            {
                pNext = _ht->_table[i];
                if(pNext)
                {
                    return pNext;
                }
            }
        }
        return NULL;//没找到
    }

private:
    Node* _pNode;
    HashTable<K, V> *_ht;
};

HashTable.cpp