Java hashcode()字符串冲突

Question

我对哈希码知之甚少.我发现这个代码可以打印出碰撞.

你能告诉我什么是碰撞以及如何减少它？我们为什么要使用哈希码？

public static int getHash(String str, int limit)
{
    int hashCode = Math.abs(str.hashCode()%(limit));
    return hashCode;
}

/**
 * @param args
 */
public static void main(String[] args)
{
    int hashLimit = 10000;
    int stringsLimit = 10000;
    String[] arr = new String[hashLimit];
    List<String> test = new ArrayList<String>();
    Random r = new Random(2);
    for ( int i = 0 ; i < stringsLimit ; i++ )
    {
        StringBuffer buf = new StringBuffer("");
        for ( int j = 0 ; j < 10 ; j++ )
        {
            char c = (char)(35+60*r.nextDouble());
            buf.append(c);
        }
        test.add(buf.toString());
        //System.out.println(buf.toString());
    }
    int collisions = 0;
    for ( String curStr : test )
    {
        int hashCode = getHash(curStr,hashLimit);
        if ( arr[hashCode] != null && !arr[hashCode].equals(curStr) )
        {
            System.out.println("collision of ["+arr[hashCode]+"] ("+arr[hashCode].hashCode()+" = "+hashCode+") with ["+curStr+"] ("+curStr.hashCode()+" = "+hashCode+")");
            collisions++;
        }
        else
        {
            arr[hashCode] = curStr;
        }
    }
    System.out.println("Collisions: "+collisions);
}

Answer 1

你能告诉我什么是碰撞以及如何减少它？

冲突是两个不相等的对象具有相同的哈希码.他们是生活中的事实 - 你需要处理它.

我们为什么要使用哈希码？

因为他们基本上可以快速按键查找值.哈希表可以使用哈希代码非常快速地将可能的密钥匹配集合下载到非常小的集合(通常只有一个),此时您需要检查实际的密钥相等性.

您永远不应该假设两个哈希码相等意味着它们派生的对象是相等的.只有相反的情况:假设一个正确的实现,如果两个对象给出不同的哈希码,那么它们就不相等.