对字符串哈希函数感到困惑

Question

当我查看一些字符串哈希函数时，我遇到了这个（下面的代码）。该函数一次处理四个字节的字符串，并将每个四字节块解释为单个长整数值。四字节块的整数值相加。最后，使用取模运算符将所得总和转换为 0 到 M-1 的范围。以下是函数代码：

// Use folding on a string, summed 4 bytes at a time
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 c[] = s.substring(intLength * 4).toCharArray();
     long mult = 1;
     for (int k = 0; k < c.length; k++) {
       sum += c[k] * mult;
       mult *= 256;

据我所知，此行中使用的子字符串函数作为参数：begin index inclusive，子字符串将从指定的 beginIndex[=25 开始=]，它将延伸到字符串的末尾。举个例子，假设我们要散列以下字符串：aaaabbbb。在这种情况下，intLength 将成为 2（函数代码的第二行）。替换 s.substring(intLength * 4).toCharArray() 中的 intlength 值将得到 s.substring(8).toCharArray()，这意味着字符串索引超出范围，因为要散列的字符串有 8 个字符。我不太明白这是怎么回事！

Answer 1

这个散列函数很糟糕，但是回答你的问题：

没有IndexOutOfBoundsException，因为"aaaabbbb".substring(8)是""

最后一个循环的目的是在字符串长度不是 4 的倍数时处理剩余部分。例如，当 s 为 "aaaabbbbcc" 时，则 intLength == 2 , s.substring(8) 是 "cc".

对字符串哈希函数感到困惑

Confused about a string hash function

string

algorithm

function

hash

substring