2

私は勉強の最初の学期にいて、コンプの一部です。ベクトルを使用して単純なハッシュ マップを実装する必要がありますが、概念を理解するのに問題があります。

まず、ハッシュ関数を実装する必要があります。衝突を避けるには、次のようにダブルハッシュを使用する方がよいと考えました。

do {
    h = (k % m + j*(1+(k % (m-2)));
    j++;
} while ( j % m != 0 );

ここで、h は返されるハッシュ、k はキー、m は hash_map のサイズ (および素数。これらはすべて int 型です) です。

これは簡単でしたが、マップ内のキーと対応する値のペアを挿入または削除できる必要があります。

2 つの関数のシグネチャは bool でなければならないので、true または flase のいずれかを返す必要があります。ベクトルの位置 h に要素がない場合は true を返す必要があると推測しています。(しかし、remove も bool にする必要がある理由がわかりません)。

私の問題は、挿入関数が false を返した場合 (つまり、位置 h にキーと値のペアが既に保存されている場合 - これを find という名前の関数として実装した場合) に何をすべきかです。単純に j を増やすだけで次の空いている場所に移動できることは明らかですが、ハッシュ関数によって計算されたハッシュは、特定のキーが保存されている場所を教えてくれなくなり、remove 関数の間違った動作を引き起こします。

定義済みの STD メソッドを使用しないオンラインの良い例はありますか? (ここ数日、私の Google はおかしな動作をしており、役に立たないヒットをローカル言語で返すだけです)

4

1 に答える 1

2

コメントを回答に移動するように言われたので、ここにあります。get メソッドは、引数を探している値を取ると思います。

私たちがやろうとしているのは、線形プロービングと呼ばれるプロセスです。

値を挿入すると、通常どおりハッシュされます。ハッシュ値が 4 であるとしましょう。

[x,x,x,,,x,x]

ご覧のとおり、次の場所に挿入するだけです。

[x,x,x,x,,x,x]

ただし、挿入時に 4 が使用された場合は、空の次のスロットに移動するだけです。

[x,x,x,**x**,x,,x,x]

線形プロービングでは、最後に到達すると、スロットが見つかるまでループして最初に戻ります。容量がいっぱいになり始めたときに余分なスペースを割り当てることができるベクターを使用しているため、スペースが不足することはありません。

4 の値が 4 でなくなる可能性があるため (この場合は 5)、検索時に問題が発生します。これを解決するために、ちょっとしたハックを行います。負荷バランスが 1 未満である限り、挿入と取得の実行時間の複雑さが O(1) になることに注意してください。

get メソッドでは、配列の 4 の値を返す代わりに、4 の値が返せる場合はその値を探し始めます。そうでない場合は、値が見つかるまで 5 などの値を調べます。

疑似コードでは、新しいものは次のようになります

bool insert(value){
   h = hash(value);
   while(node[h] != null){
      h++;

      if( h = node.length){
          h = 0;
       }
   }
   node[h] = value;

  return true;
}

得る

get(value){
    h = hash(value);
    roundTrip = 0; //used to see if we keep going round the hashmap

   while(true){

      if(node[h] == value)
          return node[h];

      h++;

      if( h = node.length){
          h = 0;
          roundTrip++;
       }

       if(roundTrip > 1){ //we can't find it after going round list once
          return -1;
       }
   }
}
于 2013-07-04T13:36:15.807 に答える