深入哈希表（三）--拉链法（哈希桶）实现哈希表

一、简介

为了解决线性探构造哈希表所出现的大量哈希冲突，我们采用了另外一种方法，便是开链法。而在SGI版本的STL中调用的也正是哈希桶的实现方法。

注意：

开链法实现哈希表的时候会出现很多很多的错误，比如各种模板错误，此时需要耐心，慢慢调整。同时又为了扩展hash_map与hash_set更改了一些模板参数，所以经过调试错误的过程，绝对会对模板有一个全新的认识。

二、拉链法实现原理：

采用了由N个头指针构成的数组，在每个表格内部维护一个List，经过哈希函数的计算，我们可以得到某一个List，我们所做的插入删除和查找等操作全部位于这个LIst上。

我们需要注意的是虽然List的遍历是线性的，但是如果List足够短，我们操作起来速度还是很快。

三、拉链法优缺点

优点：

1. 解决了线性探测所导致的太多的哈希冲突。
2. 删除结点相比于开放定址法更容易实现（在线性探测中如果删除结点，后面的结点无法访问）。
3. 搜索的时间下降

缺点：

1. 如果相同元素过多，元素在一个桶内部链接过长，反而导致时间复杂度上升。解决思路是桶中元素不再指向链表，而指向一个红黑树。

四、拉链法实现

哈希表里面存放一个链表的指针，和一个判断的数据。可以把哈希表中的元素看作链表的第一个结点，类似于指针数组。

链表里面包含指向下一个结点的指针，数据tata，结点构造如下：

template <class ValueType>
struct HashNode
{
    ValueType _valueField;

    HashNode* _next;

    HashNode(const ValueType& valueField)
        :_valueField(valueField)
        , _next(NULL)
    {}
};

hashtable数据结构

插入

第一步：检查容量是否需要扩容。
第二步：查看此时的key所对应的哈希桶位置。
第三步：构造出新的结点。
第四步：找到此哈希桶位置所链接的List所对应的结点，如果存在则插入失败，不存在则插入，此时采用头插法（头插只需要考虑结点为空和不为空，但是可以直接处理）。

查找

第一步：找到此key所对应的哈希桶的位置。
第二步：进入此哈希桶所指向的List查看Key是否相同即可。

删除

类似链表删除，定义两个指针，指向前后两个元素。

第一步：找到key所对应的哈希桶的位置。
第二步：定义两个指针，一个是需要删除的指针，一个是它前一个指针。
判断两种情况

• 情况一：要删除结点为链表的头结点
• 情况二：删除结点为其他结点。

第三步：分以上两个结点的情况删除即可。

负载因子判别

size如果等于——table的size，增容时也可以选择重新哈希结点来构造新的哈希表，但是这样做时间复杂度很高，所以我们采用现代的写法。

现代写法是：

1. 创建新表，resize获取容量。
2. 遍历原表把整个结点摘下来，先保存上一个结点，接着拿结点。
3. 找到新表的插入地方，采用头插法插入结点

析构函数

析构函数必须写，因为挂的是结点。
方法：
查找整个vector如果其中哈希桶不为0，则析构掉所链接的链表所有元素，如果为NULL则跳出循环即可。

template <class K>
struct _HashFunc
{
    size_t operator()(const K& key)
    {
        return key%_t;
    }
};
//sting的单独版本
template <>
struct _HashFunc<string> //特化string类型的仿函数
{
    static size_t BKDRHash(const char * str)
    {
        unsigned int seed = 131; // 31 131 1313 13131 131313
        unsigned int hash = 0;
        while (*str)
        {
            hash = hash * seed + (*str++);
        }
        return (hash & 0x7FFFFFFF);
    }

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

template <class ValueType>
struct HashNode
{
    ValueType _valueField;

    HashNode* _next;

    HashNode(const ValueType& valueField)
        :_valueField(valueField)
        , _next(NULL)
    {}
};

template <class K, class V, class Hashfunc = _HashFunc<K> >
class HashTable
{
    typedef V ValueType;
    typedef HashNode<ValueType> Node;
public:
    HashTable()
        :_size(0)
    {
        _tables.resize(_GetPrime(0));
    }
    HashTable(const HashTable& Hash)
    {
        _Copy();
    }
    ~HashTable()
    {
        Node* del = NULL;
        Node* cur = NULL;
        for (size_t i = 0; i < _tables.size(); ++i)
        {
            cur = _tables[i];
            while (cur)
            {
                del = cur;
                delete del;
                del == NULL;
                cur = cur->_next;
            }
        }
    }
    bool Insert(const ValueType& valueField)
    {
        _checkcapcity();
        size_t index = Hashfunc(key);

        Node* NewNode = new Node(valueField);
        if (_tables[index])
        {
            Node* cur = _tables[index];
            while (cur)
            {
                if (cur->_valueField == valueField)
                    return false;
                cur = cur->_next;
            }
        }
        ++_size;
        NewNode->_next = _tables[index];
        _tables[index] = NewNode;
        return true;
    }
    Node* Find(const K& key)
    {
        size_t index = Hashfunc(key);
        Node* cur = _tables[index];
        while (cur)
        {
            if (cur->_valueField==key)
                return cur;
            cur = cur->_next;
        }
        return NULL;
    }
    bool Rremove(const K& key)
    {
        size_t index = Hashfunc(key);
        Node* cur = _tables[index];
        Node* prev = NULL;
        Node* del = NULL;
        while (cur)
        {
            if (cur->_valueField == key)
            {
                if (prev == NULL)
                {
                    del = cur;
                    delete del;
                    _tables[index] == NULL;
                }
                else
                {
                    prev->_next = cur->_next;
                    delete cur;
                }
                --_size;
                return true;
            }
            prev = cur;
            cur = cur->_next;
        }
        return true;
    }
protected:
    int _HashFunc(const K& key)
    {
        if (_tables.size())
        {
            return HashFunc()(key) % _tables.size();
        }
        return -1;
    }
    void _checkcapcity()
    {
        if (_size * 10 == table._size() || __tables.size() == 0)
        {
            HashTable<K, V, HashFunc> hash;
            size_t NewSize = _GetPrime(_tables.size());
            hash._tables.resize(NewSize);
            Node* cur = NULL;
            Node* NewNode = NULL;

            for (size_t i = 0; i < _tables.size(); i++)
            {
                cur = _tables[i];
                if (cur == NULL)
                    continue;
                while (cur)
                {
                    size_t newpos = Hashfunc(cur->_valueField);
                    NewNode = cur;
                    cur = cur->_next;
                    NewNode->_next = hash._tables[newpos];
                    hash._tables[newpos] = NewInsert;
                }

                _tables[i] = NULL;

            }
            Swap(hash);
        }

    }
    static unsigned _GetPrime(const unsigned long 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
        };
        //以下查找比当前数还要大的素数
        for (size_t i = 0; i < _PrimeSize; i++)
        {
            if (size < _PrimeList[i])
                return _PrimeList[i];
        }
        //没找到就返回最后一个数
        return _PrimeList[_PrimeSize - 1];
    }
    Node* Swap(HashTable<K, V, HashFunc>& table)
    {
        if (*this != table)
        {
            _table.swap(table._tables);
            swap(_size, table._size);
        }
    }
private:
    vector<Node*> _tables;
    size_t _size;
};