雙探針哈希表

Question

我想編輯我的哈希表來形成一個雙哈希類，但似乎無法得到它的權利。

我想知道是否有人有任何見解。我被告知，我所需要做的就是編輯findPos（），我現在必須使用新策略來提供新探測器。

**我做了一些研究，它說在雙重探測中，你會使用R-（x mod R），其中R>大小和小於表大小的素數。那麼我要做一個新的散列函數？

這裏是我的代碼：

template <typename HashedObj> 
class HashTable 
{ 
    public: 
    explicit HashTable(int size = 101) : array(nextPrime(size)) 
     { makeEmpty(); } 

    bool contains(const HashedObj & x) const 
    { 
     return isActive(findPos(x)); 
    } 

    void makeEmpty() 
    { 
     currentSize = 0; 
     for(auto & entry : array) 
      entry.info = EMPTY; 
    } 

    bool insert(const HashedObj & x) 
    { 
      // Insert x as active 
     int currentPos = findPos(x); 
     if(isActive(currentPos)) 
      return false; 

     if(array[ currentPos ].info != DELETED) 
      ++currentSize; 

     array[ currentPos ].element = x; 
     array[ currentPos ].info = ACTIVE; 
      // Rehash; 
     if(currentSize > array.size()/2) 
      rehash(); 
     return true; 
    } 

    bool insert(HashedObj && x) 
    { 
      // Insert x as active 
     int currentPos = findPos(x); 
     if(isActive(currentPos)) 
      return false; 

     if(array[ currentPos ].info != DELETED) 
      ++currentSize; 

     array[ currentPos ] = std::move(x); 
     array[ currentPos ].info = ACTIVE; 

      // Rehash; see Section 5.5 
     if(currentSize > array.size()/2) 
      rehash(); 

     return true; 
    } 

    bool remove(const HashedObj & x) 
    { 
     int currentPos = findPos(x); 
     if(!isActive(currentPos)) 
      return false; 

     array[ currentPos ].info = DELETED; 
     return true; 
    } 

    enum EntryType { ACTIVE, EMPTY, DELETED }; 

    private: 
    struct HashEntry 
    { 
     HashedObj element; 
     EntryType info; 

     HashEntry(const HashedObj & e = HashedObj{ }, EntryType i = EMPTY) 
      : element{ e }, info{ i } { } 

     HashEntry(HashedObj && e, EntryType i = EMPTY) 
      : element{ std::move(e) }, info{ i } { } 
    }; 

    vector<HashEntry> array; 
    int currentSize; 

    bool isActive(int currentPos) const 
     { return array[ currentPos ].info == ACTIVE; } 

    int findPos(const HashedObj & x) const 
    { 
     int offset = 1; 
     int currentPos = myhash(x); 

     while(array[ currentPos ].info != EMPTY && 
       array[ currentPos ].element != x) 
     { 
      currentPos += offset; // Compute ith probe 
      offset += 2; 
      if(currentPos >= array.size()) 
       currentPos -= array.size(); 
     } 

     return currentPos; 
    } 

    void rehash() 
    { 
     vector<HashEntry> oldArray = array; 

      // Create new double-sized, empty table 
     array.resize(nextPrime(2 * oldArray.size())); 
     for(auto & entry : array) 
      entry.info = EMPTY; 

      // Copy table over 
     currentSize = 0; 
     for(auto & entry : oldArray) 
      if(entry.info == ACTIVE) 
       insert(std::move(entry.element)); 
    } 

    size_t myhash(const HashedObj & x) const 
    { 
     static hash<HashedObj> hf; 
     return hf(x) % array.size(); 
    } 
}; 

Answer 1

我不知道理解你的代碼，但讓我提出一些意見，他們不應該被視爲一個答案，但它們的尺寸更大，什麼是允許的評論。

1. 如果使用二次探測，那麼我認爲在findPos()你應該提前currentPos在有的currentPos*currentPos % array.size()方法。目前，正如我所看到的，您在一個統一中（offset最初爲1）增加currentPos，在2統一之後，在4之後等
2. 可能您試圖快速計算二次探測器。如果是這種情況，那麼offset不應該增加2，而是乘以2。那可能是offset *= 2，但是因爲你應該計算碰撞的次數，你應該增加offset。

3. 也許一個簡單的方法是：

   currentPos += 2*offset++ - 1; // fast way of doing quadratic resolution

你調整大小是確定的，因爲它保證該表將至少有一半是空，因此搜索可獲取的條目時，插入被執行是有保證的。

祝你好運