我正在复习我的数据结构期末考试,在去年的期末考试中遇到一道题。在过去的三个小时里一直在努力,我仍然想不出解决它的办法,只能反复试验。这是问题:
"假设你的哈希表的大小是31,常量g也是31,你使用下面的哈希码
int hash = 0;
int n = s.length();
for (int i = 0; i < n; i++)
hash = g * hash + s.charAt(i);
并且您使用单独的链接来解决冲突。列出五个不同的名称,它们将散列到表中的相同位置。”
我认为必须有某种技巧,可能涉及模运算符来解决这个问题,考虑到哈希表的大小为 31,与常量 g 相同。对不起,如果我听起来像,但我不是要代码或任何东西,只是对这个问题的一些想法/提示。非常感谢任何评论。谢谢
最佳答案
java 字符串可以包含零字符 ("\0"
),因此以下所有内容都将散列为相同的值:
"a"
"\0a"
"\0\0a"
"\0\0\0a"
"\0\0\0\0a"
这是证明(感谢 Eric 指出这是使用的哈希值):
> cat Foo.java
class Foo {
public static void main(String[] args) {
System.out.println("a".hashCode());
System.out.println("\0a".hashCode());
System.out.println("\0a".length());
System.out.println("\0a".equals("a"));
}
}
> javac Foo.java
> java Foo
97
97
2
false
不过,我怀疑这是预期的答案。
此外,如果这是一场考试,我怀疑我能否记住 ASCII 码。因此,在另一个答案中使用样式序列的另一种方法是:
"\002\000"
"\001\037"
等(这些是八进制三元组 - 以上都哈希为 62)。但是为这种风格生成 5 个例子(都是相同的散列)容易吗?
关于java - 在哈希表中查找冲突,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10629285/