我正在读Head First Java这本书中的一句话
的要点是,散列代码可以是相同的,而不必保证对象相等,因为
hashCode()
方法中使用的“散列算法”可能会恰好为多个对象返回相同的值。
为什么hashCode()
方法可以为不同的对象返回相同的值?这不会造成问题吗?
发布于 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。
发布于 2010-12-06 01:13:41
只有40多亿个可能的哈希码(一个int
的范围),但您可以选择创建的对象数量要多得多。因此,某些对象必须通过pigeonhole principle共享相同的散列码。
例如,包含从A到Z的10个字母的可能字符串的数量是26**10,即141167095653376。不可能为所有这些字符串分配一个唯一的哈希码。这也不重要-散列代码不需要是唯一的。它只需要对真实数据没有太多的冲突。
发布于 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
有时会将不同的键映射到同一个整数。在这些情况下,列表将包含多个值。对于检索,我们必须遍历整个列表来找到“正确”的值,但是我们如何识别它呢?
嗯,我们可以在列表中存储完整的(键,值)对,而不是单独存储值。然后,查找将分两步执行:
现在,添加和检索已经变得如此复杂,对于这些操作,将我们自己的方法分开对待并不是不恰当的:
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
复制相似问题