Java中字符串的哈希码如何计算

在Java中，字符串的哈希码是通过String类的hashCode()方法计算的。这个方法使用了一个简单的哈希算法，将字符串中的每个字符的ASCII值乘以一个质数（31），然后将所有结果相加。这个算法的优点是计算速度快，缺点是可能会产生哈希冲突（不同的字符串具有相同的哈希码）。

以下是Java中String类的hashCode()方法的简化版本，用于说明其工作原理：

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

在这个方法中，value是一个字符数组，存储了字符串的内容。hash是一个整数变量，用于缓存计算结果，避免重复计算。

这个算法的关键在于选择质数31，因为它是一个较小的质数，可以减少哈希冲突的概率。同时，乘法操作可以通过位移和减法来优化，以提高计算速度：

h = 31 * h + val[i];

可以优化为：

h = (h << 5) - h + val[i];

这是因为31 * h等于(h << 5) - h，其中<<表示左位移操作。左位移操作相当于将数字的二进制表示向左移动指定的位数，右侧用0填充。在这个例子中，左位移5位相当于乘以2的5次方（32），然后减去原始值h，得到相同的结果。