Java 负值哈希码

Question

这是我的所有代码供引用。

import java.io.*;
import java.util.*;

public class Plagiarism {

    public static void main(String[] args) throws Exception {
        //you are not using 'myPlag' anywhere, you can safely remove it
//      Plagiarism myPlag = new Plagiarism();

        if (args.length == 0) {
            System.out.println("Error: No files input");
            System.exit(0);
        }

        String foo = null;
        for (int i = 0; i < 2; i++) {
            BufferedReader reader = new BufferedReader(new FileReader(args[i]));
            foo = simplify(reader);
            // System.out.print(foo);
            int blockSize = Integer.valueOf(args[2]);

            List<String> list = new ArrayList<String>();
            for (int k = 0; k < foo.length() - blockSize + 1; k++) {
                list.add(foo.substring(k, k + blockSize));

                int x = 33;
                int hash = 0;
                for (String str: list) {
                    for (int o = 0; o < str.length(); o++) {
                        hash = 33*hash + str.charAt(o);
                    }
                }
                System.out.println(hash);

                /* List<Integer> newList = new ArrayList<Integer>(list.size());
                for (String myInt : list) {
                    newList.add(Integer.parseInt(myInt));

                    int x = 33;
                    int hash = 0;
                    for (int o = 0; o < newList.size(); o++) {
                        hash = x*hash + newList.get(o);
                    }
                } */


            }
            // System.out.print(list);
        }




    }

    public static String simplify(BufferedReader input)
            throws IOException {

        StringBuilder sb = new StringBuilder();
        String line = null;
        while ((line = input.readLine()) != null) {
            sb.append(line.replaceAll("[^a-zA-Z]", "").toLowerCase());
        }
        return sb.toString();
    }
}

虽然我想特别关注这部分:

int x = 33;
                    int hash = 0;
                    for (String str: list) {
                        for (int o = 0; o < str.length(); o++) {
                            hash = 33*hash + str.charAt(o);
                        }
                    }
                    System.out.println(hash);

返回的一些值是负哈希值。为什么是这样？即使 block 大小很小(即 2)，它仍然会这样做。我知道这可能与“模 p”有关？我在这里使用霍纳多项式方法。

我想知道是否可以获得一些帮助？

提前谢谢大家。

Answer 1

负值是由整数溢出引起的。任何最高有效位设置为 1 的整数都会解释为负数。

哈希码没有什么特殊含义:只要相等的值相同，不相等的值尽量不同即可。这就是为什么在处理哈希码时可以安全地忽略整数溢出。