HashTableBucket哈希桶

为哈希冲突而形成的开链法：

#pragma once
#include <vector>
#include <string>

template<class K,class V>
class HashTableNode
{
public:
    HashTableNode()
    {}
    HashTableNode(const K& key,const V& value)
        :_key(key)
        ,_value(value)
        ,_next(NULL)
    {}
    K _key;
    V _value;
    HashTableNode<K,V>* _next;
};

template<class K>
struct DefaultHashFun
{
    size_t operator()(const K&key)
    {
        return key;
    }
};
template<>
struct DefaultHashFun<string>
{
    static size_t BKDRHash(const char *s)
    {
        unsigned int seed = 131;
        unsigned hash = 0;
        while (*s)
        {
            hash = hash*seed + (*s++);

        }
        return (hash & 0x7FFFFFFF);
    }
    size_t operator()(const string& key)
    {
        return BKDRHash(key.c_str());
    }
};

template<class K,class V,class HashFun = DefaultHashFun<K>>
class HashTableBucket
{
    typedef HashTableNode<K,V> KVNode;
public:
    HashTableBucket()
        :_size(0)
    {}
    HashTableBucket(const size_t size)
        :_size(size)
    {
        _tables.resize(size);
    }
    void Swap(HashTableBucket<K,V,HashFun>& ht)
    {
        _tables.(ht._tables);//注意这里的交换是借助vector，不是系统
        swap(_size,ht._size);
    }
    HashTableBucket(const HashTableBucket<K,V,HashFun> &ht)
        :_size(0)
    {
        HashTableBucket<K,V,HashFun> newTables(ht._tables.size());
        for(size_t i = 0;i <ht._tables.size();++i)
        {
            cur = _tables[i];
            while(cur)
            {
                newTables.Insert(cur->_key,cur->_value);
                cur = cur->_next;
            }
        }
        Swap(newTables);
    }
    HashTableBucket<K,V>& operator=(const HashTableBucket<K,V,HashFun> &ht)
    {
        if(this != &ht)
        {
            HashTableBucket<K,V,HashFun> tmp(ht);
            this->Swap(tmp);
        }
        return *this;
    }
    ~HashTableBucket()
    {
        for(size_t i = 0;i < _tables.size();++i)
        {
            KVNode* cur = _tables[i];
            while(cur)
            {
                KVNode* del = cur;
                cur = cur->_next;
                delete del;
            }
            _tables[i] = NULL;
        }
        _size = 0;
    }

public:
    size_t HashFunc(const K&key,size_t capacity)
    {
        HashFun hf;
        return hf(key) % capacity;
    }
    bool Insert(const K& key, const V& value)
    {

        _CheckCapacity();

        size_t index = HashFunc(key,_tables.size());
        KVNode* cur = _tables[index];
        while(cur)
        {
            if(cur->_key == key)
            {
                return false;
            }
            cur = cur->_next;
        }
        //头插
        KVNode* tmp = new KVNode(key,value);
        tmp->_next = _tables[index];
        _tables[index] = tmp;

        ++_size;
    }
    bool Remove(const K& key)
    {
        size_t index = HashFunc(key,_tables.size());
        KVNode* cur = _tables[index];
        if(cur = NULL)
        {
            return false;
        }
        if(cur->_key == key)//当删除的结点为头时
        {
            _tables[index] = cur->_next;
            delete cur;
            return true;
        }
        else//不为头时
        {
            KVNode*prev = cur;
            cur = cur->_next;
            while(cur)
            {
                if(cur->_key == key)
                {
                    prev->_next = cur->_next;
                    delete cur;
                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            return false;
        }
    }
    KVNode* Find(const K& key)
    {
        size_t index = HashFunc(key,_tables.size());
        KVNode* cur = _tables[index];
        while(cur)
        {
            if(cur->_key == key)
            {
                return cur;
            }
            cur = cur->_next;
        }
        return NULL;
    }
    void Print()
    {
        for (int i = 0; i < _tables.size(); ++i)
        {
            cout << "table[" << i << "]->";
            KVNode *cur = _tables[i];
            while (cur)
            {
                cout << cur->_value << ":" << cur->_value << "->";
                cur = cur->_next;
            }
            cout << endl;
        }
    }
protected:
    size_t _GetNextPrime(size_t size)
    {
        const int _PrimeSize = 28;
        static const unsigned long _PrimeList[_PrimeSize] =
            {
                53ul, 97ul, 193ul, 389ul, 769ul,
                1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
                49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
                1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
                50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
                1610612741ul, 3221225473ul, 4294967291ul
            };
            if (size == 0)
            {
                return _PrimeList[0];
            }
            for (int i = 0; i < _PrimeSize; ++i)
            {
                if (size == _PrimeList[i])
                {
                    return _PrimeList[i + 1];
                }
            }
    }
    void _CheckCapacity()
    {
        size_t newCapacity = _GetNextPrime(_size);
        if(_size == newCapacity)
        {
            return;
        }

        vector<KVNode*> newTables;
        newTables.resize(newCapacity);

        for(size_t i = 0;i < _tables.size();++i)
        {
            KVNode* cur = _tables[i];
            while(cur)
            {
                //取结点
                KVNode* tmp = cur;
                cur = cur->_next;
                //插结点
                size_t newIndex = HashFunc(tmp->_key,newCapacity);
                tmp->_next = newTables[newIndex];
                newTables[newIndex] = tmp;
            }
            _tables[i] = NULL;
        }
        _tables.swap(newTables);
    }
protected:
    vector<HashTableNode<K,V>*> _tables;
    size_t _size;
};

void Test3()//桶
{
    HashTableBucket<string,string> ht;
    ht.Insert("苹果","apple");
    ht.Insert("香蕉","banana");
    ht.Insert("梨","pea");
    ht.Insert("美女","beauty");
}
int main()
{
    Test3();
    return 0;
}