blocks|key|292021|text|只有40多亿个可能的哈希码(一个int的范围)，但您可以选择创建的对象数量要多得多。因此，某些对象必须通过pigeonhole+principle共享相同的散列码。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|292022|例如，包含从A到Z的10个字母的可能字符串的数量是26**10，即141167095653376。不可能为所有这些字符串分配一个唯一的哈希码。这也不重要-散列代码不需要是唯一的。它只需要对真实数据没有太多的冲突。|292023|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Pigeonhole_principle^0|G|3|1H|K|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@$9|Q|A|R|B|C]]|D|@$9|S|A|T|1|U]]|E|$]]|$1|F|3|G|5|6|7|V|8|@]|D|@]|E|$]]|$1|H|3|-4|5|6|7|W|8|@]|D|@]|E|$]]]|I|$J|$5|K|L|M|E|$N|O]]]]

There are only just over 4 billion possible hashcodes (the range of an <code>int</code>) , but the number of objects you could choose to create is much larger. Therefore some objects must share the same hash code, by the <a href="http://en.wikipedia.org/wiki/Pigeonhole_principle">pigeonhole principle</a>.

For example the number of possible strings containing 10 letters from A-Z is 26**10 which is 141167095653376. It is impossible to assign all of these strings a unique hash code. Nor is it important - the hash code doesn't need to be unique. It just needs to have not too many collisions for real data.

blocks|key|288777|text|据我所知，hashcode方法的工作是创建用于散列元素的存储桶，以便检索可以更快。如果每个对象都将返回相同的值，则不需要进行任何散列。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|288778|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

As I understand, work of hashcode method is to create buckets for hashing the elements, So that retrieval can be faster. If each object will return same value, there is no use of doing any hashing.

blocks|key|3220325|text|hashing+an+object意味着“找到一个良好的、描述性的值(数字)，这个值(数字)可以被同一个实例一次又一次地复制”()。因为来自Java的Object.hashCode()的哈希码的类型是int，所以只能有2%5E32个不同的值。这就是为什么当两个不同的对象产生相同的hashCode时，你会有所谓的“冲突”，这取决于散列算法。|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|CODE|entityRanges|data|3220326|通常，这不会产生任何问题，因为hashCode()通常与equals()一起使用。例如，HashMap将在其密钥上调用hashCode()，以了解密钥是否已包含在HashMap中。如果HashMap没有找到哈希码，那么很明显HashMap中还没有包含密钥。但如果是这样的话，它将不得不使用equals()重新检查具有相同哈希码的所有键。|3220327|也就是说。|3220328|A.hashCode()+==+B.hashCode()+//+does+not+necessarily+mean
A.equals(B)|code-block|syntax|javascript|3220329|但|3220330|A.equals(B)+//+means
A.hashCode()+==+B.hashCode()|3220331|如果正确实现了equals()和hashCode()。|3220332|有关一般hashCode合同的更精确描述，请参阅Javadoc。|3220333|entityMap|0|LINK|mutability|MUTABLE|url|http://download.oracle.com/javase/6/docs/api/java/lang/Object.html#hashCode^0|0|7|L|17|23|H|2S|3|31|4|0|F|A|S|8|18|7|1N|A|40|8|0|0|0|0|0|7|8|G|A|0|4|8|O|7|0|0^^$0|@$1|2|3|4|5|6|7|15|8|@$9|16|A|17|B|C]|$9|18|A|19|B|C]|$9|1A|A|1B|B|D]|$9|1C|A|1D|B|D]|$9|1E|A|1F|B|D]]|E|@]|F|$]]|$1|G|3|H|5|6|7|1G|8|@$9|1H|A|1I|B|D]|$9|1J|A|1K|B|D]|$9|1L|A|1M|B|D]|$9|1N|A|1O|B|D]|$9|1P|A|1Q|B|D]]|E|@]|F|$]]|$1|I|3|J|5|6|7|1R|8|@]|E|@]|F|$]]|$1|K|3|L|5|M|7|1S|8|@]|E|@]|F|$N|O]]|$1|P|3|Q|5|6|7|1T|8|@]|E|@]|F|$]]|$1|R|3|S|5|M|7|1U|8|@]|E|@]|F|$N|O]]|$1|T|3|U|5|6|7|1V|8|@$9|1W|A|1X|B|D]|$9|1Y|A|1Z|B|D]]|E|@]|F|$]]|$1|V|3|W|5|6|7|20|8|@$9|21|A|22|B|D]]|E|@$9|23|A|24|1|25]]|F|$]]|$1|X|3|-4|5|6|7|26|8|@]|E|@]|F|$]]]|Y|$Z|$5|10|11|12|F|$13|14]]]]

hashing an object means "finding a good, descriptive value (number) that can be reproduced by the very same instance again and again". Because hash codes from Java's <code>Object.hashCode()</code> are of type <code>int</code>, you can only have <code>2^32</code> different values. That's why you will have so-called "collisions" depending on the hashing algorithm, when two distinct Objects produce the same hashCode.

Typically, this does not produce any problems, because <code>hashCode()</code> is mostly used together with <code>equals()</code>. For instance, a <code>HashMap</code> will call <code>hashCode()</code> upon its keys, to know whether the keys may already be contained in the HashMap. If the HashMap does not find the hash code, it's obvious the key is not contained in the HashMap yet. But if it does, it will have to double-check all keys having that same hash code using <code>equals()</code>.

I.e.

<pre><code>A.hashCode() == B.hashCode() // does not necessarily mean
A.equals(B)
</code></pre>

But

<pre><code>A.equals(B) // means
A.hashCode() == B.hashCode()
</code></pre>

If <code>equals()</code> and <code>hashCode()</code> are implemented correctly.

For a more precise description of the general <code>hashCode</code> contract, see the <a href="http://download.oracle.com/javase/6/docs/api/java/lang/Object.html#hashCode" rel="nofollow noreferrer">Javadoc</a>.

blocks|key|3006542|text|通过将散列代码用作存储对象的散列表桶的地址，hashCode()值可用于快速查找对象。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3006543|如果多个对象从hashCode()返回相同的值，这意味着它们将存储在相同的存储桶中。如果许多对象存储在同一存储桶中，这意味着平均而言，它需要更多的比较操作来查找给定的对象。|3006544|相反，使用equals()来比较两个对象，看看它们在语义上是否相等。|3006545|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

The hashCode() value can be used to quickly find an object by using the hash code as an address to a hash table bucket where it is stored.

If multiple objects return the same value from hashCode(), it means that they would be stored in the same bucket. If many objects are stored in the same bucket it means that on average it requires more comparison operations to look up a given object.

Instead use equals() to compare two objects to see whether they are semantically equal.

blocks|key|292076|text|我不得不认为这是一个非常低效的散列算法，让两个对象拥有相同的散列代码。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|292077|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

I have to think that's a pretty inefficient hashing algorithm for 2 objects to have the same hash code.

blocks|key|3220486|text|哈希表的想法是，您希望能够以一种有效的方式实现称为字典的数据结构。字典是一个键/值存储，也就是说，您希望能够在某个键下存储某些对象，然后能够使用相同的键再次检索它们。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3220487|访问值的最有效方法之一是将它们存储在数组中。例如，我们可以实现一个字典，它使用整数作为键，使用字符串作为值，如下所示：|3220488|String[]+dictionary+=+new+String[DICT_SIZE];
dictionary[15]+=+"Hello";
dictionary[121]+=+"world";

System.out.println(dictionary[15]);+//+prints+"Hello"|code-block|syntax|javascript|3220489|不幸的是，这种方法根本不是非常通用的:数组的索引必须是整数值，但理想情况下，我们希望能够为键使用任意类型的对象，而不仅仅是整数。|3220490|现在，解决这一点的方法是有一种方法将任意对象映射到整数值，然后我们可以将其用作数组的键。在Java语言中，这就是hashCode()所做的。所以现在，我们可以尝试实现一个String->String字典：|offset|length|style|CODE|3220491|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|3220492|但是，如果有一些我们想用作键的对象，但是它的hashCode方法返回一个大于或等于DICT_SIZE的值，那该怎么办呢？然后我们会得到一个ArrayIndexOutOfBoundsException，这是不可取的。所以，让我们把它做得尽可能大，好吗？|3220493|public+static+final+int+DICT_SIZE+=+Integer.MAX_VALUE+//+Ooops!|3220494|但这意味着我们将不得不为数组分配大量的内存，即使我们只打算存储几个项目。所以这不可能是最好的解决方案，事实上我们可以做得更好。假设我们有一个函数h，对于任何给定的DICT_SIZE，该函数将任意整数映射到范围[0,+DICT_SIZE[中。然后，我们只需将h应用于键对象的hashCode()方法返回的任何内容，并确保我们停留在底层数组的边界内。|3220495|public+static+int+h(int+value,+int+DICT_SIZE)+{
++++//+returns+an+integer+>=+0+and+<+DICT_SIZE+for+every+value.
}|3220496|该函数称为散列函数。现在我们可以调整我们的字典实现来避免ArrayIndexOutOfBoundsException：|3220497|//+"a"+->+"Hello"
dictionary[h("a".hashCode(),+DICT_SIZE)]+=+"Hello"

//+"b"+->+"world"
dictionary[h("b".hashCode(),+DICT_SIZE)]+=+"world"|3220498|但这引入了另一个问题:如果h将两个不同的键索引映射到相同的值，该怎么办？例如：|3220499|int+keyA+=+h("a".hashCode(),+DICT_SIZE);
int+keyB+=+h("b".hashCode(),+DICT_SIZE);|3220500|可能会为keyA和keyB产生相同的值，在这种情况下，我们会意外地覆盖数组中的值：|3220501|//+"a"+->+"Hello"
dictionary[keyA]+=+"Hello";

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

System.out.println(dictionary[keyA]);+//+prints+"world"|3220502|嗯，你可能会说，那么我们只需要确保我们以一种永远不会发生这种情况的方式实现h。不幸的是，这在一般情况下是不可能的。考虑以下代码：|3220503|for+(int+i+=+0;+i+<=+DICT_SIZE;+i%2B%2B)+{
++++dictionary[h(i,+DICT_SIZE)]+=+"dummy";
}|3220504|此循环将dummy值(实际上总是相同的值，即字符串“DICT_SIZE+%2B+1”)存储在字典中。但是数组只能存储DICT_SIZE不同的条目！这意味着，当我们使用h时，我们将覆盖(至少)一个条目。或者换句话说，h会将两个不同的键映射到相同的值！这些“碰撞”是无法避免的:如果n只鸽子试图进入n-1个鸽子洞，那么至少有两只鸽子必须进入同一个洞。|3220505|但我们可以做的是扩展我们的实现，以便数组可以在同一索引下存储多个值。这可以通过使用列表轻松地完成。因此，不要使用：|3220506|String[]+dictionary+=+new+String[DICT_SIZE];|3220507|我们写道：|3220508|List<String>[]+dictionary+=+new+List<String>[DICT_SIZE];|3220509|(附注:请注意，Java不允许创建泛型类型的数组，因此上面的代码不会被编译--但是您已经明白了)。|3220510|这将更改对字典的访问，如下所示：|3220511|//+"a"+->+"Hello"
dictionary[h("a".hashCode(),+DICT_SIZE)].add("Hello");

//+"b"+->+"world"
dictionary[h("b".hashCode(),+DICT_SIZE)].add("world");|3220512|如果我们的散列函数h为我们所有的键返回不同的值，这将导致每个列表只有一个元素，并且检索元素非常简单：|3220513|System.out.println(dictionary[h("a".hashCode(),+DICT_SIZE)].get(0));+//+"Hello"|3220514|但我们已经知道，在一般情况下，h有时会将不同的键映射到同一个整数。在这些情况下，列表将包含多个值。对于检索，我们必须遍历整个列表来找到“正确”的值，但是我们如何识别它呢？|3220515|嗯，我们可以在列表中存储完整的(键，值)对，而不是单独存储值。然后，查找将分两步执行：|3220516|3220517|应用哈希函数通过存储在检索到的列表中的所有对从array.|ordered-list-item|3220518|Iterate中检索正确的列表:如果找到具有所需键的对，则返回该对中的值。|3220519|3220520|现在，添加和检索已经变得如此复杂，对于这些操作，将我们自己的方法分开对待并不是不恰当的：|3220521|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;
}|3220522|因此，为了让这种方法工作，我们实际上需要两个比较操作:在数组中查找列表的hashCode方法(如果hashCode()和h都很快，这种方法会更快)和一个equals方法，我们在遍历列表时需要它。|3220523|这是散列的一般思想，您将从java.util.Map.中识别出put和get方法。当然，上面的实现过于简单了，但它应该说明了所有的要点。|3220524|当然，这种方法并不局限于java.lang.Object，它适用于所有类型的对象，因为方法hashCode()和equals是顶级类java.lang.Object的成员，所有其他类都继承自该类。|3220525|正如您所看到的，如果两个不同的对象在其hashCode()方法中返回相同的值，这并不重要:上面的方法总是有效的！但仍然希望它们返回不同的值，以降低h产生散列冲突的可能性。我们已经看到，这些通常不能100%25避免，但是我们得到的冲突越少，我们的哈希表就变得越有效。在最坏的情况下，所有键映射到相同的数组索引:在这种情况下，所有对都存储在一个列表中，然后查找一个值将变成一个操作，其代价与哈希表的大小成线性关系。|3220526|entityMap^0|0|0|0|0|1K|A|0|0|M|8|15|9|0|0|20|1|29|9|2W|E|3K|1|3S|A|0|0|0|0|D|1|0|0|4|4|9|4|0|0|11|1|0|0|Q|D|1K|9|29|1|2X|1|0|0|0|0|0|0|0|0|9|1|0|0|F|1|0|0|0|0|0|0|0|0|1D|A|1O|1|24|6|0|D|E|V|3|Z|3|0|19|A|1K|6|0|J|A|21|1|0^^$0|@$1|2|3|4|5|6|7|2P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|2Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|2R|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|2S|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|2T|8|@$M|2U|N|2V|O|P]]|9|@]|A|$]]|$1|Q|3|R|5|F|7|2W|8|@]|9|@]|A|$G|H]]|$1|S|3|T|5|6|7|2X|8|@$M|2Y|N|2Z|O|P]|$M|30|N|31|O|P]]|9|@]|A|$]]|$1|U|3|V|5|F|7|32|8|@]|9|@]|A|$G|H]]|$1|W|3|X|5|6|7|33|8|@$M|34|N|35|O|P]|$M|36|N|37|O|P]|$M|38|N|39|O|P]|$M|3A|N|3B|O|P]|$M|3C|N|3D|O|P]]|9|@]|A|$]]|$1|Y|3|Z|5|F|7|3E|8|@]|9|@]|A|$G|H]]|$1|10|3|11|5|6|7|3F|8|@]|9|@]|A|$]]|$1|12|3|13|5|F|7|3G|8|@]|9|@]|A|$G|H]]|$1|14|3|15|5|6|7|3H|8|@$M|3I|N|3J|O|P]]|9|@]|A|$]]|$1|16|3|17|5|F|7|3K|8|@]|9|@]|A|$G|H]]|$1|18|3|19|5|6|7|3L|8|@$M|3M|N|3N|O|P]|$M|3O|N|3P|O|P]]|9|@]|A|$]]|$1|1A|3|1B|5|F|7|3Q|8|@]|9|@]|A|$G|H]]|$1|1C|3|1D|5|6|7|3R|8|@$M|3S|N|3T|O|P]]|9|@]|A|$]]|$1|1E|3|1F|5|F|7|3U|8|@]|9|@]|A|$G|H]]|$1|1G|3|1H|5|6|7|3V|8|@$M|3W|N|3X|O|P]|$M|3Y|N|3Z|O|P]|$M|40|N|41|O|P]|$M|42|N|43|O|P]]|9|@]|A|$]]|$1|1I|3|1J|5|6|7|44|8|@]|9|@]|A|$]]|$1|1K|3|1L|5|F|7|45|8|@]|9|@]|A|$G|H]]|$1|1M|3|1N|5|6|7|46|8|@]|9|@]|A|$]]|$1|1O|3|1P|5|F|7|47|8|@]|9|@]|A|$G|H]]|$1|1Q|3|1R|5|6|7|48|8|@]|9|@]|A|$]]|$1|1S|3|1T|5|6|7|49|8|@]|9|@]|A|$]]|$1|1U|3|1V|5|F|7|4A|8|@]|9|@]|A|$G|H]]|$1|1W|3|1X|5|6|7|4B|8|@$M|4C|N|4D|O|P]]|9|@]|A|$]]|$1|1Y|3|1Z|5|F|7|4E|8|@]|9|@]|A|$G|H]]|$1|20|3|21|5|6|7|4F|8|@$M|4G|N|4H|O|P]]|9|@]|A|$]]|$1|22|3|23|5|6|7|4I|8|@]|9|@]|A|$]]|$1|24|3|-4|5|6|7|4J|8|@]|9|@]|A|$]]|$1|25|3|26|5|27|7|4K|8|@]|9|@]|A|$]]|$1|28|3|29|5|27|7|4L|8|@]|9|@]|A|$]]|$1|2A|3|-4|5|6|7|4M|8|@]|9|@]|A|$]]|$1|2B|3|2C|5|6|7|4N|8|@]|9|@]|A|$]]|$1|2D|3|2E|5|F|7|4O|8|@]|9|@]|A|$G|H]]|$1|2F|3|2G|5|6|7|4P|8|@$M|4Q|N|4R|O|P]|$M|4S|N|4T|O|P]|$M|4U|N|4V|O|P]]|9|@]|A|$]]|$1|2H|3|2I|5|6|7|4W|8|@$M|4X|N|4Y|O|P]|$M|4Z|N|50|O|P]|$M|51|N|52|O|P]]|9|@]|A|$]]|$1|2J|3|2K|5|6|7|53|8|@$M|54|N|55|O|P]|$M|56|N|57|O|P]]|9|@]|A|$]]|$1|2L|3|2M|5|6|7|58|8|@$M|59|N|5A|O|P]|$M|5B|N|5C|O|P]]|9|@]|A|$]]|$1|2N|3|-4|5|6|7|5D|8|@]|9|@]|A|$]]]|2O|$]]

The idea of a hashtable is that you want to be able to realize a datastructure called a dictionary in an efficient way. A dictionary is a key/value store, i.e., you want to be able to store certain objects under a certain key and later on be able to retrieve them again using the same key.
One of the most efficient ways to access values is to store them in an array. For instance, we could realize a dictionary that uses integers for keys and Strings for values like so:
<pre><code>String[] dictionary = new String[DICT_SIZE];
dictionary[15] = &quot;Hello&quot;;
dictionary[121] = &quot;world&quot;;

System.out.println(dictionary[15]); // prints &quot;Hello&quot;
</code></pre>
Unfortunately, this approach is not very general at all: the index of an array has to be an integer value, but ideally we'd like to be able to use arbitrary kinds of objects for our keys, not only integers.
Now, the way to solve this point is to have a way of mapping arbitrary objects to integer values which we could then use as keys for our array. In Java, that's what <code>hashCode()</code> does. So now, we could try to implement a String-&gt;String dictionary:
<pre><code>String[] dictionary = new String[DICT_SIZE];
// &quot;a&quot; -&gt; &quot;Hello&quot;
dictionary[&quot;a&quot;.hashCode()] = &quot;Hello&quot;;

// &quot;b&quot; -&gt; &quot;world&quot;
dictionary[&quot;b&quot;.hashCode()] = &quot;world&quot;;

System.out.println(dictionary[&quot;b&quot;.hashCode()]); // prints world
</code></pre>
But hey, what if there is some object which we'd like to use as a key, but its <code>hashCode</code> method returns a value that's greater than or equal to <code>DICT_SIZE</code>? Then we'd get an ArrayIndexOutOfBoundsException and that would be undesirable. So, let's just make it as big as we can, right?
<pre><code>public static final int DICT_SIZE = Integer.MAX_VALUE // Ooops!
</code></pre>
But that would mean that we would have to allocate ginormeous amounts of memory for our array, even if we only intend to store a few items. So that can't be the best solution, and in fact we can do better. Let's assume we had a function <code>h</code> that for any given <code>DICT_SIZE</code> maps arbitrary integers into the range <code>[0, DICT_SIZE[</code>. Then we could just apply <code>h</code> to whatever the <code>hashCode()</code> method of a key object returns and be certain that we stay in the boundaries of the underlying array.
<pre><code>public static int h(int value, int DICT_SIZE) {
 // returns an integer &gt;= 0 and &lt; DICT_SIZE for every value.
}
</code></pre>
That function is called a hash function. Now we can adapt our dictionary implementation to avoid the ArrayIndexOutOfBoundsException:
<pre><code>// &quot;a&quot; -&gt; &quot;Hello&quot;
dictionary[h(&quot;a&quot;.hashCode(), DICT_SIZE)] = &quot;Hello&quot;

// &quot;b&quot; -&gt; &quot;world&quot;
dictionary[h(&quot;b&quot;.hashCode(), DICT_SIZE)] = &quot;world&quot;
</code></pre>
But that introduces another problem: what if <code>h</code> maps two different key indices to the same value? For instance:
<pre><code>int keyA = h(&quot;a&quot;.hashCode(), DICT_SIZE);
int keyB = h(&quot;b&quot;.hashCode(), DICT_SIZE);
</code></pre>
may yield the same values for <code>keyA</code> and <code>keyB</code>, and in that case we would accidentally overwrite a value in our array:
<pre><code>// &quot;a&quot; -&gt; &quot;Hello&quot;
dictionary[keyA] = &quot;Hello&quot;;

// &quot;b&quot; -&gt; &quot;world&quot;
dictionary[keyB] = &quot;world&quot;; // DAMN! This overwrites &quot;Hello&quot;!!

System.out.println(dictionary[keyA]); // prints &quot;world&quot;
</code></pre>
Well, you may say, then we just have to make sure that we implement <code>h</code> in such a way that this can never happen. Unfortunately, this isn't possible in general. Consider the following code:
<pre><code>for (int i = 0; i &lt;= DICT_SIZE; i++) {
 dictionary[h(i, DICT_SIZE)] = &quot;dummy&quot;;
}
</code></pre>
This loop stores <code>DICT_SIZE + 1</code> values (always the same value, actually, namely the String &quot;dummy&quot;) in the dictionary. Mhh, but the array can only store <code>DICT_SIZE</code> different entries! That means, when we use <code>h</code>, we would overwrite (at least) one entry. Or in other words, <code>h</code> will map two different keys to the same value! These &quot;collisions&quot; can't be avoided: if n pigeons try to go into n-1 pigeon holes, at least two of them have to go into the same hole.
But what we can do is to extend our implementation so that the array can store multiple values under the same index. This can easily be done by using lists. So instead of using:
<pre><code>String[] dictionary = new String[DICT_SIZE];
</code></pre>
we write:
<pre><code>List&lt;String&gt;[] dictionary = new List&lt;String&gt;[DICT_SIZE];
</code></pre>
(Side remark: note that Java doesn't allow the creation of arrays of generic types, so the above line wouldn't compile -- but you get the idea).
That will change the access to the dictionary as follows:
<pre><code>// &quot;a&quot; -&gt; &quot;Hello&quot;
dictionary[h(&quot;a&quot;.hashCode(), DICT_SIZE)].add(&quot;Hello&quot;);

// &quot;b&quot; -&gt; &quot;world&quot;
dictionary[h(&quot;b&quot;.hashCode(), DICT_SIZE)].add(&quot;world&quot;);
</code></pre>
In case our hashfunction <code>h</code> returns different values for all our keys, this will result in lists with only one element each, and retrieving elements is really simple:
<pre><code>System.out.println(dictionary[h(&quot;a&quot;.hashCode(), DICT_SIZE)].get(0)); // &quot;Hello&quot;
</code></pre>
But we already know that in general <code>h</code> will map different keys to the same integer sometimes. In these cases, the lists will contain more than one value. For retrieval, we have to go through the whole list to find the &quot;correct&quot; value, but how would we recognize it?
Well, instead of storing the value alone, we could always store the complete (key,value) pair in the lists. Then lookup would be performed in two steps:
<ol>
<li>Apply the hashfunction to retrieve the correct list from the array.</li>
<li>Iterate through all pairs stored in the retrieved list: if the pair with the desired key is found, return the value from the pair.</li>
</ol>
Now adding and retrieving have become so complex that it's not indecent to treat ourselves separate methods for these operations:
<pre><code>List&lt;Pair&lt;String,String&gt;&gt;[] dictionary = List&lt;Pair&lt;String,String&gt;&gt;[DICT_SIZE];

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

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

 for (Pair&lt;String,String&gt; 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&lt;String,String&gt;(key, value));
}

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

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

 // entry not found
 return null;
}
</code></pre>
So, in order for this approach to work, we actually need two comparison operations: the hashCode method to find the list in the array (this works fast if <code>hashCode()</code> and <code>h</code> are both fast) and an <code>equals</code> method which we need when going through the list.
This is the general idea of hashing, and you will recognize the <code>put</code> and <code>get</code> method from <code>java.util.Map.</code> Of course, the above implementation is an oversimplification, but it should illustrate the gist of it all.
Naturally, this approach is not limited to Strings, it works for all kinds of objects, since the methods <code>hashCode()</code> and <code>equals</code> are members of the top-level class java.lang.Object and all other classes inherit from that one.
As you can see, it doesn't really matter if two distinct objects return the same value in their <code>hashCode()</code> method: the above approach will always work! But still it is desirable that they return different values to lower the chances for hash collisions produced by <code>h</code>. We have seen that these can't be avoided 100% in general, but the less collisions we get, the more efficient our hashtable becomes. In the worst case, all keys map to the same array index: in that case, all pairs are stored in a single list and finding a value will then become an operation with costs linear in the size of the hashtable.

A quote from the book I'm reading <a href="http://www.amazon.co.uk/Head-First-Java-Kathy-Sierra/dp/0596009208" rel="noreferrer">Head First Java</a>:

<blockquote>
 The point is that hashcodes can be the same without necessarily guaranteeing that the objects are equal, because the "hashing algorithm" used in the <code>hashCode()</code> method might happen to return the same value for multiple objects.
</blockquote>

Why might the <code>hashCode()</code> method return the same value for different objects? Does that not cause problems?

Why can hashCode() return the same value for different objects in Java?

我正在读这本书中的一句话的要点是，散列代码可以是相同的，而不必保证对象相等，因为hashCode()方法中使用的“散列算法”可能会恰好为多个对象返回相同的值。为什么hashCode()方法可以为不同的对象返回相同的值？这不会造成问题吗？

问为什么hashCode()可以为Java语言中的不同对象返回相同的值？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么hashCode()可以为Java语言中的不同对象返回相同的值？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么hashCode()可以为Java语言中的不同对象返回相同的值？
EN