使用 hashcode() 和 length() 进行字符串比较

Question

在 java（或任何其他使用相同哈希码函数的 PL）中可以这样说吗：

Two strings of equal length have same hashcode if and only if they are equal

我们假设哈希码函数是

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

用例：

为了比较两个大量的字符串集合，理论上使用 option 1 比 option 2 会更快，因为哈希码计算将完成一次，因为字符串将缓存其值：

选项 1：

 for(String s1 : collection1){
   for(String s2 : collection2){
     if((s1.hashCode() == s2.hashCode()) && (s1.length()==s2.length()){
        System.out.println("matched");
     }
   }
 }

选项 2

 for(String s1 : collection1){
   for(String s2 : collection2){
     if(s1.equals(s2)){
        System.out.println("matched");
     }
   }
 }

更新：

在@tobias_k评论后我意识到这个说法是错误的，所以我改变了问题。

is there a max length M for string that for any two strings of equal length their hashcode will be same if and only if they are equal

Answer 1

不，那是错误的。

例如：

System.out.println ("ab " + "ab".hashCode());
System.out.println ("bC " + "bC".hashCode());

输出：

ab 3105
bC 3105

相等的 hashCode 并不意味着相等的字符串，即使对于相同长度的字符串也是如此。

Answer 2

Two strings of equal length have same hashcode if and only if they are equal

当然不是。取长度为 100 的字符串。长度为 100 的字符串 比 int 个不同的数字多 个，因此一定有很多冲突。

is there a max length M for string that for any two strings of equal length their hashcode will be same if and only if they are equal

如果存在这样的长度 M，那么它最多为 1（因此不是很有用），如 and 答案中长度为 2 的字符串的哈希码冲突示例所示。

为了让你的比较更快，你可以先比较哈希码，然后只有当哈希码相同时才与equals比较。

for(String s1 : collection1){
    for(String s2 : collection2){
        if (s1.hashCode() == s2.hashCode() && s1.equals(s2)) {
            System.out.println("matched");
        }
    }
}

（注意：我还没有分析这是否真的比最初只使用 equals 快。）

您还可以将 collection1 中的所有字符串放入 Set 中，然后测试 collection2 中的字符串是否在该集合中。这基本上会做同样的事情：首先比较哈希码，如果找到具有相同哈希值的条目，则使用 equals。

Set<String> setFromCollection1 = new HashSet<>(collection1);
for (String s : collection2) {
    if (setFromCollection1.contains(s)) {
        System.out.println("matched");
    }
}

Answer 3

当且仅当它们相等时，两个长度相等的字符串才具有相同的哈希码 - 不一定。

检查此 "FB" 和 "Ea" 的长度相同且具有相同的哈希码，但它们不相等。

    String s = new String("FB");
    String s1 = new String("Ea");
    System.out.println(s.hashCode()); //2236
    System.out.println(s1.hashCode()); //2236
    System.out.println(s.hashCode()==s1.hashCode()); //true
    System.out.println(s.equals(s1)); //false

Answer 4

如果您正在寻找速度并且您的匹配只会发生一次，那么下面的选项是最好的并且它被 java 中的地图实现也使用

if (value1.hashCode() == value2.hashCode() && value1.equals(value2)) {
            System.out.println("matched!");
        }

但是如果你想进行多次匹配，那么你应该寻找更好的匹配算法，因为 java 实现很简单 http://www.javacodegeeks.com/2010/09/string-performance-exact-string.html post 很好地总结了字符串匹配算法的性能。

使用 hashcode() 和 length() 进行字符串比较

String comparison using hashcode() and length()

java

equality