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 位二进制数的加法和移位。

我意识到我需要以某种方式将 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 转换为二进制。这将是 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 回答