哈希表執行衝突避免和解決在C++

Question

我發現這個簡單的實現：

http://www.onextrabit.com/view/502c152965e7d250c5000001

但是它沒有任何勾結迴避。所以我修改它是這樣的：

#include <iostream> 
#include <sstream> 

using namespace std; 

template <typename ElemType> 
class HashTable { 
private: 
    // data 
    ElemType* hashData; 
    // hash table size 
    int tableSize; 
    // djb2 hash function 
    int hashing(string key) { 
     int hash = 5381; 

     for (int i = 0; i < key.length(); i++) 
      hash = ((hash << 5) + hash) + (int)key[i]; 

     return hash % tableSize; 
    } 

public: 
    HashTable(int size) { 
     tableSize = size; 

     // init hash table data given table size 
     hashData = new ElemType[tableSize]; 
    } 

    ~HashTable() { 
     delete[] hashData; 
    } 

    void set(string key, const ElemType& value) { 
     int index = hashing(key); 
     int i = 0; 
     for (;(hashData[index] != (ElemType)NULL) && (i <= tableSize); i++) { 
      index = (index + 1) % tableSize; 
     } 
     if (i > tableSize) { 
      cout << "No empty bucket!" << endl; 
      return ; 
     } 
     hashData[index] = value; 
    } 

    string get(string key) { 
     int index = hashing(key); 
     stringstream result; 
     result << hashData[index]; 
     int i = 0; 
     for (;(hashData[++index] != (ElemType)NULL) && (i <= tableSize); i++) { 
      result << " or " << hashData[index]; 
      index %= tableSize; 
     } 
     return result.str(); 
    } 
}; 

int main() { 

    HashTable<int> hash(50); 

    hash.set("Hello", 12); 
    hash.set("World", 22); 
    hash.set("Wofh", 25); 
    for (int i = 1; i < 10; i++) { 
     hash.set("Wofh", i); 
    } 

    cout << "Hello " << hash.get("Hello") << endl; 
    cout << "World " << hash.get("World") << endl; 
    cout << "Wofh " << hash.get("Wofh") << endl; 
    return 0; 
} 

這是我第一次實現一個哈希表。現在「世界」和「Wofh」從hashing()功能獲得相同的結果。顯然這是造成共謀。但是，當我想要檢索「世界」時，它會顯示所有勾結的值。我的問題是，是否有一種方法僅通過使用線性探測顯示「世界」編號（即22）？

Answer 1

每個表項都需要包含匹配散列的鍵/值對的集合。查找表條目之後，您需要搜索所需的密鑰集。

如果碰撞很少，那麼一對簡單的向量可能就足夠了。如果頻繁搜索速度過慢，並且無法通過放大表格或使用更好的函數來降低頻率，則考慮對矢量進行排序並使用二分查找，或使用std::map或其他散列表（使用不同的散列函數）來存儲碰撞的元素。

當然，除非這是一個學習練習，否則通常只需使用std::unordered_map（如果不能使用C++ 11庫，則使用Boost，TR1或STL等價物）。

另外，在設計管理內存或其他資源的類時，請務必記住Rule of Three。如果有人試圖複製它，你的班級將會出現可怕的錯誤。