为什么hashCode（）为Java中的不同对象返回相同的值？
从我正在阅读Head First Java的书中引用：
关键是，哈希码可以是相同的，而不必保证对象是相等的，因为
hashCode()方法中使用的“哈希算法”可能会为多个对象返回相同的值。
为什么hashCode()方法可能为不同的对象返回相同的值？ 这不会导致问题吗？
散列对象意味着“ 找到一个好的，描述性的值（数字），可以一次又一次地由同一个实例再现 ”。 因为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 。
只有超过40亿个可能的哈希码（ int的范围），但是你可以选择创建的对象数量要大得多。 因此，某些对象必须通过归类原则共享相同的哈希码。
例如，包含来自AZ的10个字母的可能字符串的数量是26 ** 10，即141167095653376.不可能为所有这些字符串分配唯一的哈希码。 也不重要 – 哈希码不需要是唯一的。 它只需要对真实数据没有太多的冲突。
哈希表的想法是，您希望能够以有效的方式实现称为字典的数据结构。 字典是键/值存储，即，您希望能够在某个键下存储某些对象，然后能够使用相同的键再次检索它们。
访问值的最有效方法之一是将它们存储在数组中。 例如，我们可以实现一个字典，它使用键的整数和字符串的值，如下所示：
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[] dictionary = new List [DICT_SIZE];
（旁注：注意Java不允许创建generics类型的数组，因此上面的行不会编译 - 但你明白了）。
这将改变对字典的访问，如下所示：
// "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会将不同的键映射到同一个整数。 在这些情况下，列表将包含多个值。 为了检索，我们必须通过整个列表来找到“正确”值，但我们如何识别它？
好吧，我们可以始终在列表中存储完整的（键，值）对，而不是单独存储值。 然后将分两步执行查找：
- 应用哈希函数从数组中检索正确的列表。
- 迭代检索到的列表中存储的所有对：如果找到具有所需键的对，则返回该对中的值。
现在添加和检索已经变得如此复杂，以至于不能为这些操作单独处理自己的方法：
List>[] dictionary = List>[DICT_SIZE]; public void put(String key, String value) { int hashCode = key.hashCode(); int arrayIndex = h(hashCode, DICT_SIZE); List> listAtIndex = dictionary[arrayIndex]; if (listAtIndex == null) { listAtIndex = new LinkedList>(); dictionary[arrayIndex] = listAtIndex; } for (Pair previouslyAdded : listAtIndex) { if (previouslyAdded.getValue().equals(value)) { return; // the value is already in the dictionary; } } listAtIndex.add(new Pair(key, value)); } public String get(String key) { int hashCode = key.hashCode(); int arrayIndex = h(hashCode, DICT_SIZE); List> listAtIndex = dictionary[arrayIndex]; if (listAtIndex != null) { for (Pair 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.util.Map. 当然，上面的实现过于简单化，但它应该说明一切的要点。
当然，这种方法不仅限于Strings，它适用于所有类型的对象，因为方法hashCode()和equals是顶级类java.lang.Object的成员，所有其他类都inheritance自该类。
正如您所看到的，如果两个不同的对象在其hashCode()方法中返回相同的值并不重要：上述方法将始终有效！ 但仍然希望它们返回不同的值以降低由h产生的哈希冲突的机会。 我们已经看到这些通常不能100％避免，但是我们得到的冲突越少，我们的哈希表变得越有效。 在最坏的情况下，所有键映射到相同的数组索引：在这种情况下，所有对都存储在单个列表中，然后查找值将成为一个操作，其成本与哈希表的大小成线性关系。
hashCode（）值可用于通过使用哈希码作为存储它的哈希表桶的地址来快速查找对象。
如果多个对象从hashCode（）返回相同的值，则意味着它们将存储在同一个存储桶中。 如果许多对象存储在同一个存储桶中，则意味着平均而言需要更多的比较操作来查找给定对象。
而是使用equals（）来比较两个对象，看它们是否在语义上相等。
据我所知，hashcode方法的工作是创建用于散列元素的存储桶，以便检索更快。 如果每个对象都返回相同的值，则不进行任何散列。
我不得不认为这是一个非常低效的哈希算法，可以让2个对象拥有相同的哈希码。