0 
stper** pages;
int tableSize;    
struct Person{

    string name; 
    int age;    
    string homeTown;
};


void fonk1 (int numberOfBuckets)
{
    pages = new stper*[numberOfBuckets]();
    tableSize = numberOfBuckets;
} 

   int hashPerson(Person& person)
   {
    int hashVal = 0;
    for (int i=0; i < (person.getName()).length() ; i++)
        hashVal = 37*hashVal + (person.getName())[i];

    for (int i=0; i < (person.getHomeTown()).length() ; i++)
        hashVal = 37*hashVal + (person.getHomeTown())[i];   
    hashVal+= person.getAge();  

    hashVal %= tableSize;
    if(hashVal < 0)
        hashVal += tableSize;
    return hashVal;
   }

みなさん、こんにちは。私はハッシュが初めてです。私のハッシュ関数は上記の hashPerson 関数にあります。ご覧のとおり、3 つのキーがあります。私の関数はハッシュに適したアルゴリズムですか?どうすれば関数を改善し、衝突の数を減らすことができますか? (構文ミスがあっても無視してください)

4

2 に答える 2

1

std::hash基本コンポーネントの適切なハッシュ値を生成するために使用できます。ここでいくつかの例と説明を見つけることができます。

ブーストのバージョンがインストールされている場合は、それboost::hash_combineが必要な機能を備えていることに気付くかもしれません。ここで良いサンプルを含むブーストのドキュメントを見つけることができます。

于 2013-01-05T23:06:27.767 に答える
1

いくつかの提案があります：

  1. unsignedの代わりに使用しintます。私の経験では、符号なしのオーバーフローが発生した場合でも、負でないままであるため、これによりパフォーマンスが向上することが証明されています (そうしないと、%-ing によって大きな問題が発生する可能性があります - 負のインデックスが発生し、... クラッシュします)。衝突率の減少（経験的に証明されています）。また、結局のところ、関数はテーブル内のインデックスを返すことになっているため、値が符号なしであることは当然です。インデックスは負になることはできません。

  2. 年齢を加算するときは、hashVal に何かを掛けます。たとえば 200 など、考えられる年齢よりも大きい値をお勧めします。

  3. 何が何であるかは決して言いませんがtableSize、衝突率を減らすために、大きな（できるだけ大きな）素数を使用することをお勧めします。

于 2013-01-05T21:25:09.013 に答える