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);
}

- quad

---

关于您的三个问题，所有三个问题的最佳答案都可以在维基百科上找到。 - ControlAltDel

请查看http://en.wikipedia.org/wiki/Hash_table。 - Steve Kuo

Answer 1

请问什么是哈希冲突以及如何减少冲突？

哈希冲突是指两个不同的对象具有相同的哈希码。哈希冲突是不可避免的，需要采取措施来解决。

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

因为它可以快速地通过关键字查找值。哈希表可以使用哈希码将可能的关键字匹配集合缩小到一个非常小的范围（通常只有一个），然后您需要检查实际的关键字相等性。

您应该永远不要假设两个哈希码相等意味着它们所代表的对象是相等的。只有反过来是正确的：如果两个对象给出不同的哈希码，则它们不相等，假定实现是正确的。

- Jon Skeet

---

你明确将哈希码限制为最多有10,000个不同值，这是一个相当差的起点。不清楚你试图做什么，但如果你要编写自己的哈希表，我建议先进行更多的研究。你必须能够处理冲突，而且有各种不同的方法可以解决冲突。 - Jon Skeet

Answer 2

为了回答你问题的另一部分：为了减少碰撞的概率，你应该实现一个哈希算法，它可以在可能的输入集上提供均匀分布的哈希码。

例如，假设你实现了一个天真的hashCode()方法来哈希MyString实例：

public class MyString {
  private final char[] arr;

  // Constructor and other methods.

  public int hashCode() {
    return arr.length == 0 ? 0 : (int) arr[0];
  }
}

在这个例子中，只使用第一个字符来创建哈希码。因此，如果您对字符串“apple”，“anaconda”，“anecdote”进行哈希处理，则它们都将生成相同的哈希值。更有效的哈希码应该检查字符数组中的所有字母以确定哈希码值，这有望减少碰撞的机会。

- Adamski

Answer 3

如果两个不同的、非相等的对象具有相同的哈希码，我们就会遇到“碰撞”的情况。这可能是一个问题，例如当尝试将这两个对象都用作哈希映射中的键时。

- Andreas Dolk

---

@HelloWorld 改进哈希函数可以减少冲突，但通常最简单的方法是使用更大的数组，即较低的负载因子。 - Peter Lawrey

@HelloWorld，代码通过第二个参数限制了getHash方法的使用，所以您可以通过增加（或消除）该限制来减少它。 - Kirk Woll

@Kirk Woll 谢谢您。我减少了限制，碰撞也减少了。但是还有其他可能的方法吗？ - quad