为什么hashCode()为Java中的不同对象返回相同的值？

Question

从我正在阅读Head First Java的书中引用:

关键是,哈希码可以是相同的,而不必保证对象是相等的,因为hashCode()方法中使用的"哈希算法" 可能会为多个对象返回相同的值.

为什么该hashCode()方法可能为不同的对象返回相同的值？这不会导致问题吗？

Answer 1

散列对象意味着" 找到一个好的,描述性的值(数字),可以由同一个实例一次又一次地再现 ".因为Java的哈希码Object.hashCode()是类型int,所以只能有2^32不同的值.这就是为什么当两个不同的对象产生相同的hashCode时,取决于散列算法,你会有所谓的"冲突".

通常情况下,这不会产生任何问题,因为它们hashCode()大多与之一起使用equals().例如,a HashMap将调用hashCode()其键,以了解键是否已经包含在HashMap中.如果HashMap没有找到哈希代码,那么很明显,密钥尚未包含在HashMap中.但如果确实如此,则必须仔细检查具有相同哈希码的所有密钥equals().

即

A.hashCode() == B.hashCode() // does not necessarily mean
A.equals(B)

但

A.equals(B) // means
A.hashCode() == B.hashCode()

如果equals()并且hashCode()正确实施.

有关一般hashCode合同的更精确描述,请参阅Javadoc.

Answer 2

只有超过40亿个可能的哈希码(范围为a int),但是您可以选择创建的对象数量要大得多.因此,某些对象必须通过归类原则共享相同的哈希码.

例如,包含来自AZ的10个字母的可能字符串的数量是26**10,即141167095653376.不可能为所有这些字符串分配唯一的哈希码.也不重要 - 哈希码不需要是唯一的.它只需要对真实数据没有太多的冲突.

Answer 3

哈希表的想法是,你要能够实现所谓的一种有效的方式字典数据结构.字典是一个键/值存储,即要能够存储在某一个键的特定对象,后来就能够使用相同的密钥重新找回它们.

其中最有效的方法来访问值是将它们存储在数组中.例如,我们可以意识到,用来像这样值的键整数和字符串的字典:

String[] dictionary = new String[DICT_SIZE];
dictionary[15] = "Hello";
dictionary[121] = "world";

System.out.println(dictionary[15]); // prints "Hello"

不幸的是,这种方法也不是很一般都:数组的索引必须是一个整数值,但最好我们希望能够使用任意类型的对象为我们的钥匙,不仅是整数.

现在,解决这一问题的方法是使用一种方法将任意对象映射到整数值,然后我们可以将其用作数组的键.在Java中,这是做什么的hashCode().所以现在,我们可以尝试实现String-> String字典:

String[] dictionary = new String[DICT_SIZE];
// "a" -> "Hello"
dictionary["a".hashCode()] = "Hello";

// "b" -> "world"
dictionary["b".hashCode()] = "world";

System.out.println(dictionary["b".hashCode()]); // prints world

但是,嘿,如果有一些我们想要用作关键字的对象,但是它的hashCode方法返回的值大于或等于DICT_SIZE？然后我们得到一个ArrayIndexOutOfBoundsException,这是不可取的.那么,让我们尽可能大,对吧？

public static final int DICT_SIZE = Integer.MAX_VALUE // Ooops!

但这意味着我们必须为数组分配大量的内存,即使我们只打算存储一些项目.所以这不是最好的解决方案,事实上我们可以做得更好.让我们假设我们有一个函数h,对于任何给定的DICT_SIZE映射任意整数到该范围[0, DICT_SIZE[.然后我们可以只应用于关键对象返回的h任何hashCode()方法,并确保我们保持在底层数组的边界.

public static int h(int value, int DICT_SIZE) {
    // returns an integer >= 0 and < DICT_SIZE for every value.
}

该函数称为哈希函数.现在我们可以调整我们的字典实现来避免ArrayIndexOutOfBoundsException:

// "a" -> "Hello"
dictionary[h("a".hashCode(), DICT_SIZE)] = "Hello"

// "b" -> "world"
dictionary[h("b".hashCode(), DICT_SIZE)] = "world"

但这引入了另一个问题:如果h将两个不同的键索引映射到相同的值会怎么样？例如:

int keyA = h("a".hashCode(), DICT_SIZE);
int keyB = h("b".hashCode(), DICT_SIZE);

可能会为keyA和产生相同的值keyB,在这种情况下,我们会不小心覆盖数组中的值:

// "a" -> "Hello"
dictionary[keyA] = "Hello";

// "b" -> "world"
dictionary[keyB] = "world"; // DAMN! This overwrites "Hello"!!

System.out.println(dictionary[keyA]); // prints "world"

好吧,你可能会说,那么我们必须确保我们h以一种永远不会发生的方式实施.不幸的是,这一般是不可能的.请考虑以下代码:

for (int i = 0; i <= DICT_SIZE; i++) {
    dictionary[h(i, DICT_SIZE)] = "dummy";
}

此循环DICT_SIZE + 1在字典中存储值(实际上总是相同的值,即字符串"dummy").嗯,但阵列只能存储DICT_SIZE不同的条目!这意味着,当我们使用时h,我们会覆盖(至少)一个条目.换句话说,h将两个不同的键映射到相同的值!这些"碰撞"是无法避免的:如果n只鸽子试图进入n-1鸽笼,其中至少有两只必须进入同一个洞.

但我们可以做的是扩展我们的实现,以便数组可以在同一索引下存储多个值.这可以通过使用列表轻松完成.所以不要使用:

String[] dictionary = new String[DICT_SIZE];

我们写:

List<String>[] dictionary = new List<String>[DICT_SIZE];

(旁注:注意Java不允许创建泛型类型的数组,因此上面的行不会编译 - 但是你明白了).

这将改变对字典的访问,如下所示:

// "a" -> "Hello"
dictionary[h("a".hashCode(), DICT_SIZE)].add("Hello");

// "b" -> "world"
dictionary[h("b".hashCode(), DICT_SIZE)].add("world");

如果我们的hash h函数为所有键返回不同的值,这将导致列表中每个只有一个元素,并且检索元素非常简单:

System.out.println(dictionary[h("a".hashCode(), DICT_SIZE)].get(0)); // "Hello"

但我们已经知道,通常h有时会将不同的键映射到同一个整数.在这些情况下,列表将包含多个值.为了检索,我们必须通过整个列表来找到"正确"值,但我们如何识别它？

好吧,我们可以始终在列表中存储完整的(键,值)对,而不是单独存储值.然后将分两步执行查找:

1. 应用哈希函数从数组中检索正确的列表.
2. 迭代检索到的列表中存储的所有对:如果找到具有所需键的对,则返回该对中的值.

现在添加和检索已经变得如此复杂,以至于不能为这些操作单独处理自己的方法:

List<Pair<String,String>>[] dictionary = List<Pair<String,String>>[DICT_SIZE];

public void put(String key, String value) {
    int hashCode = key.hashCode();
    int arrayIndex = h(hashCode, DICT_SIZE);

    List<Pair<String,String>> listAtIndex = dictionary[arrayIndex];
    if (listAtIndex == null) {
        listAtIndex = new LinkedList<Pair<Integer,String>>();
        dictionary[arrayIndex] = listAtIndex;
    }

    for (Pair<String,String> previouslyAdded : listAtIndex) {
        if (previouslyAdded.getValue().equals(value)) {
            return; // the value is already in the dictionary;
        }
    }

    listAtIndex.add(new Pair<String,String>(key, value));
}

public String get(String key) {
    int hashCode = key.hashCode();
    int arrayIndex = h(hashCode, DICT_SIZE);

    List<Pair<String,String>> listAtIndex = dictionary[arrayIndex];
    if (listAtIndex != null) {
        for (Pair<String,String> previouslyAdded : listAtIndex) {
            if (previouslyAdded.getKey().equals(key)) {
                return previouslyAdded.getValue(); // entry found!
            }
        }
    }

    // entry not found
    return null;
}

因此,为了使这种方法的工作,我们实际上需要两个比较操作:hashCode方法寻找数组中的列表(这个工程快,如果hashCode()和h都是快速)和equals在列表中去的时候,我们需要的方法.

这是散列的一般概念,你会认识到put和get方法java.util.Map..当然,上面的实现过于简单化,但它应该说明一切的要点.

当然,这种方法并不局限于字符串,它适用于所有类型的对象,因为这些方法hashCode()和equals是顶级类java.lang成员和所有其他类从一个继承.

正如您所看到的,如果两个不同的对象在其hashCode()方法中返回相同的值并不重要:上述方法将始终有效!但仍然希望它们返回不同的值以降低由此产生的哈希冲突的机会h.我们已经看到这些通常不能100%避免,但是我们得到的冲突越少,我们的哈希表变得越有效.在最坏的情况下,所有键都映射到相同的数组索引:在这种情况下,所有对都存储在单个列表中,然后查找值将成为一个操作,其成本与哈希表的大小成线性关系.