1

私の質問は、文字列のハッシュ値を生成し、一度に 4 バイトを合計するコードに関するものです。それは完全に機能していますが、このコードのいくつかの行、つまりいくつかの行で実行されるアイデアを理解できません。したがって、ハッシュに精通しているあなたの助けが必要です。

さて、これは完全なコードです：

long sfold(String s, int M) {
 int intLength = s.length() / 4;
 long sum = 0;
 for (int j = 0; j < intLength; j++) {
   char c[] = s.substring(j * 4, (j * 4) + 4).toCharArray();
   long mult = 1;
   for (int k = 0; k < c.length; k++) {
 sum += c[k] * mult;
 mult *= 256;
   }
 }

 char c[] = s.substring(intLength * 4).toCharArray();
 long mult = 1;
 for (int k = 0; k < c.length; k++) {
   sum += c[k] * mult;
   mult *= 256;
 }

 return(Math.abs(sum) % M);

}

ここでは、各 char 値が長整数型に変換され、for ループの各反復で結果が合計されます。私が上で言及した疑わしい 2 行のコードは次のとおりです。

sum += c[k] * mult;
mult *= 256;

ええと、この2行を除いて、コード全体を理解できます...

1) なぜ変数 'mult' が必要なのですか? ハッシュに掛け算方式を使っているのではないでしょうか？

2) 各反復で 'mult' を正確に 256 倍するのはなぜですか? この場合の 256 は何ですか?

あなたの何人かがこのコードに直面したか、これらの行で実行されるアイデアを知っているなら、私もそれを理解するのを手伝ってください:)

4

3 に答える 3

1

char であるため、c[k]サイズは 8 ビットであり、8 ビットは正確に 256 の可能な数値です。たとえば、 がchar[] c = new char[]{'a, 'b', 'c', 'd'}あります。ここ'a'では、少し賢明な形式で、次のように10000001なります。ここで問題は、 をどのように形成するかです。まず、表現をビット単位で取得すると、 になります。次に、ビット単位の形式を取得して乗算します。これは、実際には 8 ビットを左にビット単位でシフトするだけです。つまり、 (ビット形式の 256 は 100000000) と同じで、これを前の合計に追加すると、最後の 8 ビットをビット形式に置き換えるだけです。次に同じことが起こります。b10000010sumasum10000001b256'b' * 25610000001 * 100000000 = 1000000100000000'b' * 256a

したがって、最終的には、以前の をビットごとに連結した数値を受け取るだけですchar(たとえば、10000001 10000010 10000011 10000100)。

それが役立つことを願っています。

于 2013-06-23T11:31:13.617 に答える
0

乗算256は、実際にはビットを左に 8 桁 (1 バイト) シフトすることです。

したがって、それが行うことは次のとおりです。

  • 最初の文字のビットを最下位 8 ビット (最初のバイト) に保持し、
  • 次の文字の 8 ビットは、次の 8 つの位置 (次のバイト) にあり、最大 4 つまで続きます。

4 ビット システムの例を示します (その場合は 16 を掛けます)。 

c[0] = 1101
c[1] = 1001 
c[2] = 0010 
c[3] = 0110

longビットが次のように見える合計を構築します。

0110 0010 1001 1101
c[3] c[2] c[1] c[0]
于 2013-06-23T11:32:13.350 に答える