整数用のハッシュを設定しますか？

Question

私はintのセットのためのハッシュを作成する必要があります。私は一種の知っているときに問題が、ある

Outer loop - TableSize = 10 to 1000 
Middle loop - k = 1 to 500 
Inner loop - create a table, and set it to -1 
Inner inner loop - step through 10 #s loc = f(num) 

：私は彼らがこのように設定されていると私は間違いなく、4つのループを必要と知っている

f(x) = k * x % TableSize. 

：私が使用する必要があるハッシュ関数はこれです外側と中間のループを設定する方法は、私は最後の2つのループについて立ち往生しています。

文字列に関しては、ハッシュテーブルを設定する方法は分かっていますが、（設定が少し違うと聞いたように）int型の方法はわかりません。また、要件に基づいて、私は内側のループでテーブルを作成するか、単に別の関数を呼び出すでしょうか？

これは私の.hファイルにあるすべてです。

#pragma once 
#include <iostream> 
#include <string> 

using namespace std; 

class intHash{ 

public: 
intHash(int tableSize); 
~intHash(); 

void someStuff(){ 
    for (int TableSize = 10; TableSize < 1000; TableSize++){ 
     for (int k = 1; k < 500; k++){ 
      for(){ 
       intHash(-1); 
       for(){ 

       } 
      } 
     } 
    } 
} 


private: 
string *hashTable; 
}; 

Answer 1

これはちょっと楽しいことでした。もちろん、これをそのままの状態にしておくと、大きな時間を過ごすというあなたの任務は失敗します。

このハッシュは、ハッシュが使用されているかどうかを判断するためにブール値を使用しています。開口部が見つかるまで、テーブルを1歩進んで衝突を処理します。もう1つの方法は、それぞれの場所にリストを設定し、比較してリストを歩くことです。いずれも動作します。

別のタイプを使用するには、HashValueTableEntry値のタイプを変更するだけです。型はそのまま使用するためにある種の算術をサポートする必要がありますが、より複雑な型の新しいハッシュ関数が必要です。

とにかく、これはあなたにハッシュ関数の作業アイデアを与えます。

#include <iostream> 

class intHash 
{ 
public: 
    typedef int HashValueType; 

    intHash(int tableSize) 
    { 
     m_tableSize = tableSize; 
     m_hashTable = new HashValueTableEntry[tableSize]; 
    } 

    ~intHash() 
    { 
     delete[] m_hashTable; 
    } 

    HashValueType add(int value) 
    { 
     int hashValue = hash(value); 
     m_hashTable[hashValue].inUse = true; 
     m_hashTable[hashValue].value = value; 

     return hashValue; 
    } 

    bool get(HashValueType hashValue, int *value) 
    { 
     if(m_hashTable[hashValue].inUse) 
     { 
      *value = m_hashTable[hashValue].value; 
      return true; 
     } 

     return false; 
    } 

    void remove(HashValueType hashvalue) 
    { 
     m_hashTable[hashvalue].inUse = false; 
    } 

private: 
    struct HashValueTableEntry 
    { 
     HashValueTableEntry() : value(0), inUse(false) {} 
     int value; 
     bool inUse; 
    }; 

    int hash(int value) 
    { 
     static const int k = 7; 
     int currentHash = (value * k) % m_tableSize; 

     int overflowCounter = 0; 

     // Collision resolution 
     while(m_hashTable[currentHash].inUse == true && 
       m_hashTable[currentHash].value != value) 
     { 
      currentHash++; 
      if(overflowCounter++ == m_tableSize) 
      { 
       // assert, end the world, error whatever. 
       // At this point though, currentHash is garbage and should be handled. 
       break; 
      } 
     } 

     return currentHash; 
    } 

    HashValueTableEntry *m_hashTable; 
    int m_tableSize; 
}; 

int main(void) 
{ 
    intHash hash(100); 
    int hashValues[100]; 

    for(int i=0; i<10; i++) 
    { 
     hashValues[i] = hash.add(i); 

     // Purposely setup hash collisions to show that it is handled. 
     hashValues[i+10] = hash.add(i+100); 
    } 

    for(int i=0; i<20; i++) 
    { 
     int tableValue = 0; 
     hash.get(hashValues[i], &tableValue); 
     std::cout << "Hash is " << hashValues[i] << " value is " << tableValue << std::endl; 
    } 

    return 0; 
}