【數據結構】處理哈希沖突的開鏈法（哈希桶）算法實現

實現哈希表時，我們常見的方法是線性探測、二次探測，這兩個算法也很簡單。若有興趣，可以查看我的博客 http://10740184.blog.51cto.com/10730184/1771160。但是，這兩個算法有一個共同點就是：空間利用率低。為什么這么說呢？線性探測、二次探測的高效性很大程度上要取決于它的載荷因子，載荷因子即：存放關鍵字個數/空間大小。

通過查閱資料，我發現，使用素數做除數可以減少哈希沖突（具體原因不詳，大師專研的，發現很好用，就在這里分享給大家）。見下：

----素數表

     // 使用素數表對齊做哈希表的容量，降低哈希沖突

     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

    };

開鏈法（哈希桶）結構：

而哈希桶實現時，我們可以將載荷因子設成1.

代碼如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

#include<vector>

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

template<class K,class V>
class HashTable
{
public:
    typedef HashTableNode<K,V> Node;

    HashTable()
        :_table(NULL)
        , _size()
    {}


    size_t _HashFunc(const K& key)
    {
        //_table.size()表示哈希桶的空間大小
        return key % _table.size();
    }
    
    
    //拷貝構造
    HashTable(const HashTable& ht)
    {
        //將哈希表ht拷貝給this
        this->_table.resize(ht._table.size());
        for (int i = 0; i < ht._table.size(); i++)
        {
            Node* cur = ht._table[i];
            while (cur)
            {
                Node* tmp = new Node(cur->_key, cur->_value);
                tmp->_next = _table[i];
                _table[i] = tmp;
                this->_size++;

                cur = cur->_next;
            }
        }    
    }


    HashTable<K, V> operator=(const HashTable<K, V>& ht)
    {    
        if (&ht != this)
        {
            //刪除哈希表this
            for (int i = 0; i < this->_table.size(); i++)
            {
                Node* cur = _table[i];
                while (cur)
                {
                    Node* del = cur;
                    cur = cur->_next;
                    /*delete del;
                    del = NULL;*/
                    Remove(del->_key);
                }
            }

            //將哈希表ht拷貝給this
            this->_table.resize(ht._table.size());
            for (int i = 0; i < ht._table.size(); i++)
            {
                Node* cur = ht._table[i];
                while (cur)
                {
                    Node* tmp = new Node(cur->_key, cur->_value);
                    tmp->_next = _table[i];
                    _table[i] = tmp;
                    this->_size++;

                    cur = cur->_next;
                }
            }        
        }
        return *this;
    }


    //賦值運算符重載的現代寫法
    HashTable<K, V> operator=(HashTable<K, V> ht)
    {
        if (&ht != this)
        {
            swap(_table, ht._table);
            swap(_size, ht._size);
        }    
        return *this;
    }


    ~HashTable()
    {
        //刪除哈希表ht
        if (this->_table.size() !=0)
        {
            for (int i = 0; i < this->_table.size(); i++)
            {
                Node* cur = _table[i];
                while (cur)
                {
                    Node* del = cur;
                    cur = cur->_next;
                    delete del;
                    del = NULL;
                }
            }
        }
    }


    //獲取新的哈希表容量大小
    size_t _GetnewSize()
    {
        static 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 (int i = 0; i < _PrimeSize; i++)
        {
            if (_PrimeList[i]> _table.size())
            {
                return _PrimeList[i];
            }
        }
        return _PrimeList[_PrimeSize - 1];
    }


    //給哈希桶擴容
    void _ExpandCapacity()
    {        
        //開辟新的更大容量的哈希表
        size_t newSize = _GetnewSize();
        vector<Node*> newTable;
        newTable.resize(newSize);

        //將每處順序表上的單鏈表元素摘下來插入到新的順序表上
        for (int i = 0; i < _table.size(); i++)
        {
            Node* cur = _table[i];
            while (cur)
            {
                Node* tmp = cur;
                cur = cur->_next;
                int index = _HashFunc(tmp->_key);
                //頭插法插插節點
                tmp->_next = newTable[index];
                newTable[index] = tmp;
            }
            _table[i] = NULL;
        }
        _table.swap(newTable);
    }


    //插入關鍵字
    bool Insert(const K& key,const V& value)
    {
        //檢查載荷因子，考慮是否擴容
        //哈希桶的載荷因子設置為1
        if (_size == _table.size())
        {
            _ExpandCapacity();
        }

        //往順序表的index處插入節點
        size_t index = _HashFunc(key);
        Node* begin = _table[index];
        while (begin)
        {
            //設計成不可出現重復元素
            if (begin->_key == key)
            {
                return false;
            }

            begin = begin->_next;
        }

        //考慮到同一條單鏈表上，無所謂元素存放順序，且較尾插簡單。--》頭插
        Node* tmp = new Node(key, value);
        tmp->_next =_table[index];
        _table[index] = tmp;
        _size++;
        return true;
    }


    //查找關鍵字
    Node* Find(const K& key)
    {
        int index = _HashFunc(key);
        Node* cur = _table[index];
        while (cur)
        {
            if (cur->_key == key)
                return cur;
            cur = cur->_next;
        }
        return NULL;
    }


    //刪除關鍵字
    bool Remove(const K& key)
    {
        int index = _HashFunc(key);
        Node* cur = _table[index];
        Node* prev = NULL;
        while (cur)
        {
            if (cur->_key == key)
                break;
            prev = cur;
            cur = cur->_next;
        }

        if (cur)
        {
            if (cur == _table[index])
            {            
                _table[index] = cur->_next;
            }
            else
            {
                Node* next = cur->_next;
                prev->_next = next;
            }
            delete cur;
            cur = NULL;
            --_size;
            return true;        
        }
        return false;
    }


    //打印哈希桶
    void PrintHashTable()
    {
        for (int i = 0; i < _table.size(); i++)
        {
            Node* cur = _table[i];
            cout << i<<":" ;
            while (cur)
            {
                cout << cur->_key << "->";
                cur = cur->_next;
            }
            cout << "NULL" << endl;
        }
        cout << endl;
    }
    
private:
    vector<Node*> _table;
    size_t _size;//數據個數
};


void TestHashTableBucket()
{
    typedef HashTableNode<int, char> Node;

    HashTable<int, char> ht;
    ht.Insert(1, 'a');
    ht.Insert(2, 'b');
    ht.Insert(3, 'c');
    ht.Insert(4, 'd');
    ht.Insert(5, 'd');
    ht.Insert(54, 'x');
    ht.Insert(55, 'y');
    ht.Insert(56, 'z');

    ht.PrintHashTable();


    /*Node* ret = ht.Find(5);
    cout << ret->_value << endl;

    ht.Remove(1);
    ht.Remove(6);
    ht.PrintHashTable();*/

    /*HashTable<int, char> ht1(ht);
    ht1.PrintHashTable();*/

    HashTable<int, char> ht2;
    ht2.Insert(54, 'x');
    ht2.Insert(55, 'y');
    ht2.Insert(56, 'z');
    ht2.Insert(1, 'a');
    ht2.Insert(2, 'b');
    ht2.Insert(3, 'c');
    ht2.Insert(4, 'd');
    ht2.Insert(5, 'd');

    ht2.PrintHashTable();

    ht = ht2;
    ht.PrintHashTable();

}


int main()
{
    TestHashTableBucket();
    system("pause");
    return 0;
}