为什么hashCode()可以为Java语言中的不同对象返回相同的值？
我正在读Head First Java这本书中的一句话
的要点是，散列代码可以是相同的，而不必保证对象相等，因为
hashCode()方法中使用的“散列算法”可能会恰好为多个对象返回相同的值。
为什么hashCode()方法可以为不同的对象返回相同的值？这不会造成问题吗？
回答 6
Stack Overflow用户
发布于 2010-12-06 01:24:05
hashing an object意味着“找到一个良好的、描述性的值(数字)，这个值(数字)可以被同一个实例一次又一次地复制”()。因为来自Java的Object.hashCode()的哈希码的类型是int，所以只能有2^32个不同的值。这就是为什么当两个不同的对象产生相同的hashCode时，你会有所谓的“冲突”，这取决于散列算法。
通常，这不会产生任何问题，因为hashCode()通常与equals()一起使用。例如，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。
Stack Overflow用户
发布于 2010-12-06 01:13:41
只有40多亿个可能的哈希码(一个int的范围)，但您可以选择创建的对象数量要多得多。因此，某些对象必须通过pigeonhole principle共享相同的散列码。
例如，包含从A到Z的10个字母的可能字符串的数量是26**10，即141167095653376。不可能为所有这些字符串分配一个唯一的哈希码。这也不重要-散列代码不需要是唯一的。它只需要对真实数据没有太多的冲突。
Stack Overflow用户
发布于 2010-12-06 02:56:18
哈希表的想法是，您希望能够以一种有效的方式实现称为字典的数据结构。字典是一个键/值存储，也就是说，您希望能够在某个键下存储某些对象，然后能够使用相同的键再次检索它们。
访问值的最有效方法之一是将它们存储在数组中。例如，我们可以实现一个字典，它使用整数作为键，使用字符串作为值，如下所示：
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";
}此循环将dummy值(实际上总是相同的值，即字符串“DICT_SIZE + 1”)存储在字典中。但是数组只能存储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");如果我们的散列函数h为我们所有的键返回不同的值，这将导致每个列表只有一个元素，并且检索元素非常简单：
System.out.println(dictionary[h("a".hashCode(), DICT_SIZE)].get(0)); // "Hello"但我们已经知道，在一般情况下，h有时会将不同的键映射到同一个整数。在这些情况下，列表将包含多个值。对于检索，我们必须遍历整个列表来找到“正确”的值，但是我们如何识别它呢？
嗯，我们可以在列表中存储完整的(键，值)对，而不是单独存储值。然后，查找将分两步执行：
- 应用哈希函数通过存储在检索到的列表中的所有对从array.
- Iterate中检索正确的列表:如果找到具有所需键的对，则返回该对中的值。
现在，添加和检索已经变得如此复杂，对于这些操作，将我们自己的方法分开对待并不是不恰当的：
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.getKey().equals(key)) {
// the key is already used in the dictionary,
// so let's simply overwrite the associated value
previouslyAdded.setValue(value);
return;
}
}
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方法，我们在遍历列表时需要它。
这是散列的一般思想，您将从java.util.Map.中识别出put和get方法。当然，上面的实现过于简单了，但它应该说明了所有的要点。
当然，这种方法并不局限于java.lang.Object，它适用于所有类型的对象，因为方法hashCode()和equals是顶级类java.lang.Object的成员，所有其他类都继承自该类。
正如您所看到的，如果两个不同的对象在其hashCode()方法中返回相同的值，这并不重要:上面的方法总是有效的！但仍然希望它们返回不同的值，以降低h产生散列冲突的可能性。我们已经看到，这些通常不能100%避免，但是我们得到的冲突越少，我们的哈希表就变得越有效。在最坏的情况下，所有键映射到相同的数组索引:在这种情况下，所有对都存储在一个列表中，然后查找一个值将变成一个操作，其代价与哈希表的大小成线性关系。
https://stackoverflow.com/questions/4360035
复制相似问题