0

私は次のメソッドを書いています：

public static int hash2(String key, int tableSize) {
    int hashVal = 0;

    for(int i=0; i<key.length();i++) {
        hashVal = 37 * hashVal + key.charAt(i);
    }

    System.out.println(hashVal);

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

    return hashVal;
}

私は、乗算や除算を使用せずにforループを書き直すという任務を負っています。私の唯一のツールは、16ビットの2進数の加算とシフトです。

どういうわけかhashValに37を掛けてから、この値にkey.charAt（i）を追加する必要があることに気付きました。私はそれを複数の方法で試しました：

    for(int i=0; i<key.length();i++) {
        hashVal2 = hashVal2<<19 - hashVal2;
        hashVal2 += key.charAt(i);
    }

また

    for(int i=0; i<key.length();i++) {
        hashVal2 = hashVal2<<18 + hashVal2;
        hashVal2 += key.charAt(i);
    }

また

    for(int i=0; i<key.length();i++) {
        for(int j=0; j<37;j++) {
            hashVal2 += hashVal2;
        }
        hashVal2 += key.charAt(i);
    }

ただし、これらのいずれも、hashVal（またはhashVal2）に元のメソッドと同じ値を返すことはありません。私はビットシフトを誤解していますか、それともループの原因は何かですか？他に何を試すべきかわからない。

4

2 に答える 2

4

37を掛けることは、2の特定の累乗を加えることと同じです。

x * 37 == x * (32 + 4 + 1)

これは、シフトする方法を示しています。

32 == 2 5
4 == 2 2
1 == 2 0

最後に、すべてのiに対してx * 2 i ==（x << i）。したがって、xに37を掛けると、次のように計算できます。

(x << 5) + (x << 2) + (x)

残りの演習はかなり簡単なはずです。

于 2012-09-28T03:45:04.460 に答える
1

1ビット左シフトすると、数値に2が乗算されます。したがって、37を乗算するには、37を2進数に変換します。100101になります

Number * 2^5 + Number * 2^2 + Number * 2^0
Number << 5 + Number << 2 + Number

forループは次のようになります。

for(int i=0; i<key.length();i++) {
    hashVal = (hashVal << 5) + (hashVal << 2) + hashVal + key.charAt(i);
}
于 2012-09-28T03:52:15.190 に答える