深入了解哈希算法

什么是哈希算法？相信大部分人都不太了解，今天小編為了讓大家更加了解哈希算法，給大家總結了以下內容，一起往下看吧。 

HashTable--哈希表，是一種典型的 "key--value" 形式的數據結構，構建這種數據結構的目的，是為了使用戶通過 key 值快速定位到我的 value ，從而進行相應的增刪查改的工作。當數據量較小時，簡單遍歷也能達到目的，但面對大量數據處理時，造成時間和空間上的消耗，不是一般人可以承擔的起的。

    首先，先簡單了解一下，什么是哈希。

    我們的目的是在一堆數據中查找（這里以×××為例），為了節省空間，我們不可能列出一個有所有數據范圍那么大的數組，因此這里我們需要建立一種映射關系HashFunc，把我的所有數據通過映射放到這段空間當中，因此哈希表也叫作散列表。

關于映射關系 HashFunc ，常見的有以下幾種：

    1>直接定值法

    直接定址法是最簡單的方法，取出關鍵字之后，直接或通過某種線性變換，作為我的散列地址。例如：Hash(key) = key*m+n;其中m、n為常數。

    2、除留余數法

    除留余數法是讓我的關鍵碼 key 通過對我的數組長度取模，得到的余數作為當前關鍵字的哈希地址。

    除了以上的兩種方法，還有平方取中法、折疊法、隨機數法、平方分析法等，雖然方法不同，但目的都是一樣的，為了得到每個關鍵字 key 的地址碼，這里不再贅述。

哈希沖突   

    經過 HashFunc 函數處理之后，得到了每個關鍵字的哈希地址，正如上面提到的，很容易出現兩個關鍵碼的哈希地址相同或者哈希地址已經被其他關鍵字占用的情況，這種情況我們叫做哈希沖突，或者哈希碰撞。這是在散列表中不可避免的。

    這里定義了一個新名詞--載荷因子α

     α = 填入表中的元素個數 / 散列表的長度

        載荷因子表示的是填入表中的數據占表總長度的比例。當我們在哈希表中查找一個對象時，平均查找長度是載荷因子 α 的函數。散列表的底層是一個vector，當載荷因子超過一定量的時候，我們需要對vector進行resize擴容，來減小哈希表的插入及查找壓力。

為了解決哈希沖突，這里有兩種方法閉散列法<開放定址法>和拉鏈法<哈希桶>

開放地址法：

    需要指出的一點，開放地址法構造的HashTable，對載荷因子的要求極其重要。應嚴格限制載荷因子在0.7~0.8以下，超過0.8，查表時的不命中率會成指數上升。

    上面我們提到了兩種HashFunc，針對這兩種方法得到的哈希地址之后，我們可以做如下處理。當得到的地址碼已經被占用，則我當前 key 的地址向后推移即可。這種方法叫做線性探測。

    另外還有一種方法，二次探測法。解決思想是當我的哈希地址沖突后，每次不再是加1，而是每次加1^2，2^2，3^2...直到找到空的地址，這種方法很明顯可以將各個數據分開，但會引入一個問題，會導致二次探測了多次，依然沒有找到空閑的位置。這里用同一組例子來說明。

    除此之外，為了減少哈希沖突，前人總結出了一組素數表，經過數學計算表明，使用蘇鼠標對其做哈希表的容量，可以有效的降低哈希沖突。

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
};

代碼實現與解釋

    這里首先給出哈希表中每個元素結點的類，同時給出 HashTable 的框架除了key、value之外，多增加了一個狀態位，當下面用到的時候，會具體給出原因。

enum State
{
    EMPTY,
    EXIST,
    DELETE
};
template <typename K ,typename V>
struct KVNode
{
    K _key;
    V _value;
    State _state;
    KVNode(const K& key = K(), const V& value = V())
        :_key(key)
        , _value(value)
        , _state(EMPTY)
    {}
};

//Hashtable類
template <typename K, typename V>
class HashTable
{
    typedef KVNode<K, V> Node;
public:
    HashTable()
    :_size(0)
    {}
    bool Insert(const K& key,const V& value)
    {}  
    Node* Find(const K& key)
    {}
    bool Remove(const K& key)
    {}
protected:
    vector<Node> _table;
    size_t _size;
};

    對于哈希表的插入，可以分為以下幾步：

    a) 進行容量檢查

    b) 通過取模得到該關鍵字在HashTable中的位置

    c) 對得到的位置進行調整

        這里要注意的一點，因為對于key_value類型的數據結構而言，關鍵字 key 是唯一 的，因此，當在調整的時候發現了和待插入 key 一樣的值，直接返回 false 結束插入函數。

    d) 對該位置的key、value、state進行調整

    對于哈希表的刪除，這里采用的是偽刪除法。即找到該 key 之后，將該點的狀態改為DELETE即可，因為我們在對 vector 進行擴容的時候，是通過resize實現的，不論是增加元素還是刪除，resize出來的空間不需要去釋放，這里可以減少內存的多次開辟與釋放，提高效率。

    另外，假設我們可以將這段空間的內容清空，會帶來的問題就是，之前我們插入的時候，所有經過該結點調整過的key都需要重新移動，否則這個元素我們再也找不到。這就是我們這里引入三個狀態的原因。

    對于哈希表的查找，要考慮的東西就相對比較多了。

    當找到該結點的位置之后，如果 key 值不是我們想要的 key 值，就需要繼續向后找，只有當結點的狀態位EMPTY時，查找才會停止，當然如果找到的EMPTY還是沒有找到我們想要的 key 值，那么該關鍵字一定不在當前的哈希表中。需要注意，會不會存在一種情況，當我們在vector中遍歷的時候，循環條件是當前結點的狀態不為EMPTY，進入了死循環？會的。這是因為我們引入了DELETE的結果，設想表中的所有節點都是DELETE或者EXIST狀態，且我們要查找的key不在HashTable中，死循環是必然的情況。

    下面給出完整的實現代碼：

template <typename K, typename V>
class HashTable
{
    typedef KVNode<K, V> Node;
public:
    HashTable()
  :_size(0)
  {}
    bool Insert(const K& key,const V& value)
  {
        //容量檢查
        _CheckSize();
        //獲取關鍵字在HashTable中的位置
        size_t index = _GetHashIndex(key);
        //對位置進行調整
        while (_table[index]._state == EXIST)
        {
        // 如果插入的key存在，返回false
        if (_table[index]._key == key)
            return false;
        index++;//線性探測
        if (index == _table.size())
            index = 0;
        }
    //找到位置之后改變該位置的狀態
        _table[index]._key = key;
        _table[index]._value = value;
        _table[index]._state = EXIST;
        _size++;
        return true;
    }
    Node* Find(const K& key)
    {
        // 空表，直接返回
        if (_table.empty())
        return NULL;
        size_t index = _GetHashIndex(key);
        int begin = index;
        while (_table[index]._state != EMPTY)
        {
            if (_table[index]._key == key)
            {
                // 該位置為已刪除結點
                if (_table[index]._state == DELETE)
                    return NULL;
                else
                    return &_table[index];
            }
            //改變循環變量
            index++;
            if (index == _table.size())
                index = 0;
            // 循環一圈，沒有找到
            if (index == begin)
            return NULL;
        }
        return NULL;
    }
    bool Remove(const K& key)
    {
        if (_table.empty())
            return false;
        Node* ret = Find(key);
        if (ret != NULL)
        {
            ret->_state = DELETE;
            --_size;
            return true;
        }
        else
            return false;
    }
protected:
    //獲取key在HashTable中的位置
    size_t _GetHashIndex(const K& key)
    {
        return key % _table.size();
    }
    //現代寫法
    void Swap(HashTable<K, V, HASHTABLE>& ht)
    {
        _table.swap(ht._table);
    }
    //容量檢查
    void _CheckSize()
    {
        //空表，或載荷因子大于等于8
        if ((_table.size() == 0) || ((_size * 10) / _table.size() >= 8))
        {
            size_t newSize = _GetPrimeSize(_table.size());
            HashTable<K, V, HASHTABLE> hasht;
            hasht._table.resize(newSize);
            // 將原來的HashTable中的key，value插入到新表中
            for (size_t i = 0; i < _table.size(); i++)
            {
                if (_table[i]._state == EXIST)
                {
                    hasht.Insert(_table[i]._key, _table[i]._value);
                }
            }
            this->Swap(hasht);
        }
    }
    // 從素數表找到下次擴容的容量
    size_t _GetPrimeSize(const 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
        };
        for (size_t i = 0; i < _PrimeSize; i++)
        {
            if (_PrimeList[i] > size)
                return _PrimeList[i];
        }
        return _PrimeList[_PrimeSize-1];
    }
protected:
    vector<Node> _table;
    size_t _size;
};

拉鏈法：

    對于拉鏈法，這里實際上是構建了哈希桶。如圖：

    同樣一組數據放到拉鏈法構成的哈希表中，每一個結點不再是只記錄key、value值，這里多存放了一個指向next的指針，這樣的話vector的每個點上都可以向下追加任意個結點。拉鏈法似乎更加的有效，載荷因子在這里也顯得不是那么重要，但我們依舊需要考慮這個問題。載荷因子雖然在這里的限制比開放地址法更加寬松了些，但是如果我們只是在10個結點下無限制的串加結點，也是會增大查找的時間復雜度。這里我們把載荷因子提高到1，減輕增容的壓力。另外，vector中保存的是 Node* ，這是為了兼容我的向下指針，這樣的話，也就不再需要狀態標志。初次之外，其他部分和開放地址法相比，思想大致相同。    

template<typename K,typename V>
struct KVNode
{
    K _key;
    V _value;
    KVNode<K, V>* _next;
    KVNode(const K& key, const V& value)
        :_key(key)
        , _value(value)
        , _next(NULL)
    {}
};
template<typename K, typename V>
class HashTableList
{
    typedef KVNode<K, V> Node;
public:
    HashTableList()
    :_size(0)
    {}
    Node* Find(const K& key)
    {}
    bool Insert(const K& key,const V& value)
    {}
    bool Remove(const K& key)
    {}	
protected:
    vector<Node*> _htlist;
    size_t _size;
};

    插入結點：這里我采用的是頭插法，原因其實很簡單，因為頭插的效率比較高，而且只要簡單想想，就可以發現，除了結點已經存在以外，其他這里的所有情況可以統一來處理，這就大大簡化了代碼的冗雜。

    查找結點：查找的話，首先定位到哈希地址，然后只需要在對應的位置向下遍歷即可。

    刪除結點：刪除結點不建議調用Find函數，如沒有找到的話，直接返回，但如果找到的話，還需要再找一遍去刪除。所以這里直接去哈希中找相應的key。首先還是需要定位到key所對應的哈希地址，只要不為NULL，就一直向下查找，找不到就返回false，找到了直接 delete 掉就好。

    下面給出完整的實現代碼：

template<typename K, typename V>
class HashTableList
{
    typedef KVNode<K, V> Node;
public:
    HashTableList()
        :_size(0)
    {}
    Node* Find(const K& key)
    {
        if (_htlist.empty())
            return NULL;
        int index = GetHashIndex(key);
        Node* cur = _htlist[index];
        while (cur)
        {
            if (cur->_key == key)
                return cur;
            cur = cur->_next;
        }
        return NULL;
    }
    bool Insert(const K& key,const V& value)
    {
        _Check();
        size_t index = GetHashIndex(key);
        if (Find(key))
            return false;
        Node* tmp = new Node(key, value);
        tmp->_next = _htlist[index];
        _htlist[index] = tmp;
        _size++;
        return true;
    }
    bool Remove(const K& key)
    {
        if (_htlist.empty())
            return false;
        int index = GetHashIndex(key);
        Node* cur = _htlist[index];
        Node* prev = NULL;
        while (cur)
        {
            if (cur->_key == key)
            {
                if (prev == NULL)
                    _htlist[index] = cur->_next;
                else
                    prev->_next = cur->_next;
                delete cur;
            cur = NULL;
            _size--;
            return true;
            }
            cur = cur->_next;
        }
        return false;
    }
    void Print()  // 測試函數
    {
        for (size_t i = 0; i < _htlist.size(); i++)
        {
            Node* cur = _htlist[i];
            cout << "the  "<< i << "th " << "->";
            while (cur)
            {
                cout << cur->_key << "->";
                cur = cur->_next;
            }
            cout << "NULL" << endl;
        }
    }
protected:
    int GetHashIndex(const K& key)
    {
        return key % _htlist.size();
    }
    
    void Swap(HashTableList<K, V, __HashList>& ht)
    {
        _htlist.swap(ht._htlist);
    }
    
    void _Check()
    {
      if (_htlist.empty() || (_size == _htlist.size())) //  載荷因子提升到1
        {
            size_t newsize = GetNewSize(_size);
            vector<Node*> tmp;
            tmp.resize(newsize);
            // 拷貝
            for (size_t i = 0; i < _htlist.size(); i++)
            {
                Node*  cur = _htlist[i];
                while (cur)  //  哈希鏈處理
                {
                    Node* next = cur->_next;
                    _htlist[i] = next;
                    size_t k = cur->_key;
                    cur->_next = tmp[k % newsize];
                    tmp[k % newsize] = cur;
                    cur = next;
                }
            }
            _htlist.swap(tmp);
        }                                        
    }
    size_t GetNewSize(const size_t& sz)
    {
        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 (sz < _PrimeList[i])
                return _PrimeList[i];
        }
        return _PrimeList[_PrimeSize - 1];
    }
protected:
    vector<Node*> _htlist;
    size_t _size;
};

    關于整數的哈希算法就到這里，下面給出一張本篇文章的一張簡圖，便于大家理解HashTable。對于字符串哈希的處理，下一篇會進行介紹。

關于哈希算法就分享到這里了，希望以上內容可以對大家有一定的參考價值，可以學以致用。如果喜歡本篇文章，不妨把它分享出去讓更多的人看到。