为什么Java中的String.hashCode()有很多冲突？

Question

为什么String.hashcode()有这么多冲突？

我在jdk1.6中读取String.hashCode(),下面是代码

public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

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

这对我来说很混乱,因为它有很多冲突; 虽然它不需要是唯一的(我们仍然可以依赖于equals()),但是更少的冲突意味着更好的性能而无需访问链表中的条目.

假设我们有两个字符,那么只要我们找到两个匹配下面的方程的字符串,那么我们就会有相同的hashcode()

a * 31 +b = c * 31 +d

很容易得出结论,(a-c) * 31 = d-b 一个简单的例子是make ac = 1和db = 31; 所以我写下面的代码进行简单的测试

public void testHash() {
    System.out.println("A:" + (int)'A');
    System.out.println("B:" + (int)'B');
    System.out.println("a:" + (int)'a');

    System.out.println("Aa".hashCode() + "," + "BB".hashCode());
    System.out.println("Ba".hashCode() + "," + "CB".hashCode());
    System.out.println("Ca".hashCode() + "," + "DB".hashCode());
    System.out.println("Da".hashCode() + "," + "EB".hashCode());        
}

它将打印在结果下面,这意味着所有字符串都具有相同的hashcode(),并且它很容易在循环中完成.

A:65 
B:66
a:97
2112,2112
2143,2143
2174,2174
2205,2205

更糟的是,假设我们已经4个字符字符串中,根据算法,假设前两个字符产生A2,第二2个字符产生B2; a2 * 31^2 + b2 因此,如果a2和b2在2个字符串之间相等,那么哈希码仍将是哈希码()冲突.这样的例子是"AaAa","BBBB"等; 那么我们将有6个字符,8个字符......

假设大多数时候我们在字符串中使用ascii表中的字符,这将在hashmap或hashtable中使用,那么这里选择的素数31肯定太小了;

一个简单的解决方法是使用更大的素数(幸运的是,257是素数)可以避免这种冲突.当然,选择一个太大的数字会导致返回的int值溢出,如果字符串很长,但我假设大多数时候用作键的字符串不是那么大？当然,它仍然可以返回一个很长的值来避免这种情况.

下面是我对betterhash()的修改版本,它可以通过运行将在值下面打印的代码轻松解决这些冲突,这对解决这个问题很有效.

16802,17028
17059,17285
17316,17542
17573,17799

但为什么jdk没有解决它？谢谢.

@Test
public void testBetterhash() {
    System.out.println(betterHash("Aa") + "," + betterHash("BB"));      
    System.out.println(betterHash("Ba") + "," + betterHash("CB"));
    System.out.println(betterHash("Ca") + "," + betterHash("DB"));
    System.out.println(betterHash("Da") + "," + betterHash("EB"));
}

public static int betterHash(String s) {
    int h = 0;
    int len = s.length();

    for (int i = 0; i < len; i++) {
        h = 257*h + s.charAt(i);
    }
    return h;
}

Answer 1

我刚刚练习了58,000个英语单词(在这里找到),全都是小写的,也是首字母大写的.知道有多少相撞？二:"兄弟姐妹"和"德黑兰"("德黑兰"的替代拼写).

就像你一样,我拿了一个子域(在我的情况下可能是一个)可能的字符串并分析了它的hashCode冲突率,并发现它是示范性的.谁能说你的可能字符串的任意子域是比我的优化更好的选择？

编写此类的人必须这样做,因为他们无法预测(也不因此优化)其用户将字符串用作键的子域.所以他们选择了一个哈希函数,它在整个字符串域上均匀分布.

如果你有兴趣,这是我的代码(它使用Guava):

    List<String> words = CharStreams.readLines(new InputStreamReader(StringHashTester.class.getResourceAsStream("corncob_lowercase.txt")));
    Multimap<Integer, String> wordMap = ArrayListMultimap.create();
    for (String word : words) {
        wordMap.put(word.hashCode(), word);
        String capitalizedWord = word.substring(0, 1).toUpperCase() + word.substring(1);
        wordMap.put(capitalizedWord.hashCode(), capitalizedWord);
    }

    Map<Integer, Collection<String>> collisions = Maps.filterValues(wordMap.asMap(), new Predicate<Collection<String>>() {
        public boolean apply(Collection<String> strings) {
            return strings.size() > 1;
        }
    });

    System.out.println("Number of collisions: " + collisions.size());
    for (Collection<String> collision : collisions.values()) {
        System.out.println(collision);
    }

编辑

顺便说一下,如果你很好奇,你的哈希函数的相同测试与String.hashCode's 1 相比有13次碰撞.

Answer 2

对不起,我们需要对这个想法投入一些冷水.

1. 您的分析太简单了.你似乎已经挑选了一系列字符串,旨在证明你的观点.这并不表明在所有字符串的域中冲突的数量(统计上)高于预期.

2. 没有人会想到 String.hashCode是高度无冲突的.它的设计并没有考虑到这一点.(如果你想要高度无冲突散列,那么使用加密散列算法......并支付费用.)String.hashCode()被设计为在所有字符串的域中相当不错......并且速度很快.

3. 假设你可以陈述一个更强的案例,这不是陈述它的地方.您需要向重要人员提出此问题 - Oracle的Java工程团队.

4. Java工程团队将权衡这种变化的优势与实现它的成本,为他们以及Java的每个其他用户.最后一点可能足以杀死这个石头死的想法.

^{("高度无冲突散列",是一个想法/术语,我为了这个答案而撤出了.抱歉.但是,要点是,2个字符串的哈希码冲突概率应该与相关性无关例如,"AA"和"bz"由于具有相同的长度而相关.显然,这个想法需要更多的思考.而且我所谈论的意义上的"相关性"也很明显.不可测量......有点像Kolmogorov复杂性.)}

Answer 3

散列时碰撞是不可避免的.该hashCode()方法返回一个整数,该整数用作数组的索引,该数组是具有相同哈希码的所有对象的存储桶.该equals(Object)方法用于将目标对象与桶中的每个对象进行比较,以识别完全匹配的对象(如果存在).

最终,该hashCode()方法只是需要快速而不是太弱(即造成了太多的冲突),其中太弱是一个相当模糊的指标.