问java.util.HashMap和HashSet的内部实现

EN

问题2的答案很简单--是的，你可以使用任何你喜欢的对象。具有字符串类型键的映射被广泛使用，因为它们是命名服务的典型数据结构。但一般来说，您可以映射任何两种类型，如Map<Car,Vendor>或Map<Student,Course>。

对于hashcode()方法，就像前面回答的那样--每当你重写equals()时，你就必须重写hashcode()来遵守约定。另一方面，如果您对equals()的标准实现感到满意，那么您就不应该接触hashcode() (因为这可能会破坏约定，并导致不相等对象的hashcode相同)。

实用的附注: eclipse (可能还有其他IDE)可以根据类成员自动为您的类生成一对equals()和hashcode()实现。

编辑

对于你的附加问题:是的，完全正确。查看HashMap.get(对象键)的源代码；它调用key.hashcode来计算内部哈希表中的位置(bin)，并返回该位置的值(如果有)。

但是要小心“手工”的hashcode/equals方法--如果你使用一个对象作为键，确保hashcode在之后不会改变，否则你将找不到映射值。换句话说，你用来计算equals和hashcode的字段应该是最终的(或者在对象创建后是“不可改变的”)。

假设我们有一个与String name和String phonenumber的联系人，我们使用这两个字段来计算equals()和hashcode()。现在我们用他的手机号码创建"John Doe“，并将他映射到他最喜欢的甜甜圈店。hashcode()用于计算哈希表中的索引(bin)，这是存储甜甜圈商店的位置。

现在，我们了解到他有了一个新的电话号码，并且我们更改了John Doe对象的电话号码字段。这会产生一个新的哈希码。这个哈希码解析成一个新的哈希表索引--这个哈希表索引通常不是John to最喜欢的甜甜圈店存储的位置。

问题很明显:在这种情况下，我们想要将"John Doe“映射到甜甜圈商店，而不是"John Doe与特定的电话号码”。因此，我们必须小心自动生成的equals/hashcode，以确保它们是我们真正想要的，因为它们可能会使用不需要的字段，从而给HashMaps和HashSets带来麻烦。

编辑2

如果您将一个对象添加到HashSet，则该对象是内部哈希表的键，值已设置但未使用(只是object的静态实例)。以下是OpenJDK6(B17)的实现：

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;

public boolean add(E e) {
  return map.put(e, PRESENT)==null;
}

像HashMap和HashSet这样的散列容器通过将它们的内容分成“桶”来提供对存储在其中的元素的快速访问。

例如，存储在List中的数字列表：1, 2, 3, 4, 5, 6, 7, 8在内存中(从概念上讲)类似于：[1, 2, 3, 4, 5, 6, 7, 8]。

在Set中存储相同的一组数字看起来更像这样：[1, 2] [3, 4] [5, 6] [7, 8]。在这个例子中，列表被分成了4个存储桶。

现在，假设您想要从List和Set中找到值6。对于一个列表，你必须从列表的开头开始，检查每个值，直到你达到6，这将需要6个步骤。有了一个集合，您可以找到正确的存储桶，检查该存储桶中的每个项目(在我们的示例中只有2个)，这将是一个3步的过程。您拥有的数据越多，这种方法的价值就越大。

但是等等，我们怎么知道要查看哪个存储桶呢？这就是hashCode方法的用武之地。为了确定在其中查找项的存储桶，Java call容器调用hashCode，然后对结果应用一些函数。此函数尝试平衡存储桶的数量和项目的数量，以便尽可能快地查找。

在查找过程中，一旦找到了正确的存储桶，就会像在列表中一样逐个比较该存储桶中的每一项。这就是为什么当你重写hashCode时，你也必须重写equals。因此，如果任何类型的对象同时具有equals和hashCode方法，则可以将其用作Map中的键或Set中的条目。要正确地实现这些方法，必须遵守一个契约。关于这一点的规范文本来自Josh Bloch的杰作Effective：Item 8: Always override hashCode when you override equals

在HashMap/HashSet中@Override public int hashcode()的重要性是什么？

这允许映射的实例根据映射的内容生成有用的哈希码。具有相同内容的两个映射将产生相同的哈希码。如果内容不同，则哈希码也会不同。

这个哈希码的内部用法是什么？

绝不可能。此代码仅存在，因此您可以将一个映射用作另一个映射中的键。

我可以像myMap<someObject, Object>一样根据someObject (而不是String)映射值吗？

是的，但是someObject必须是一个类，而不是一个对象(你的名字表明你想传入object；它应该是SomeObject，以表明你引用的是类型)。

我需要遵守什么合同才能成功地完成这项工作？

该类必须实现hashCode()和equals()。

编辑

我们是说密钥的哈希码(检查！)值在哈希表中的实际映射值是什么？

是。