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

我一直试图理解 和 的内部实现。java.util.HashMapjava.util.HashSet

以下是我脑海中浮现的疑惑:

  1. 在 HashMap/HashSet 中的重要性是什么?此哈希代码在内部使用的位置?@Override public int hashcode()
  2. 我通常看到HashMap的密钥是类似的。我可以像?我需要遵守哪些合同才能成功实现?StringmyMap<String,Object>someObjectmyMap<someObject, Object>

提前致谢!

编辑:

  1. 我们是说键的哈希代码(检查!)是哈希表中映射值的实际内容吗?当我们做java时,Java是在内部调用以获取Hash表中的数字以查找结果值?myMap.get(someKey);someKey.hashCode()

答:是的。

编辑2:

  1. 在 中,从何处为 Hash 表生成密钥?它是否来自我们正在添加的对象,例如。 然后决定将其放置在哈希表中的位置?(因为我们不在哈希集中提供密钥)。java.util.HashSetmySet.add(myObject);myObject.hashCode()

答:添加的对象将成为键。价值是假的!


答案 1

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

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

实用的旁注:eclipse(可能还有其他IDE)可以为您的类自动生成一对equals()和hashcode()实现,只需基于类成员。

编辑

对于您的其他问题:是的,没错。查看HashMap.get(Object key)的源代码;它调用key.hashcode来计算内部哈希表中的位置(bin),并返回该位置的值(如果有的话)。

但是要小心“手工制作”的哈希码/等于方法 - 如果您使用对象作为键,请确保哈希码之后不会更改,否则您将找不到映射的值。换句话说,用于计算等于和哈希码的字段应该是最终的(或在创建对象后“不可更改”)。

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

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

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

编辑 2

如果将对象添加到 HashSet,则 Object 是内部哈希表的键,该值已设置但未使用(只是 Object 的静态实例)。以下是 openjdk 6 (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;
}

答案 2

哈希容器喜欢,并通过将其内容拆分为“桶”来提供对存储在其中的元素的快速访问。HashMapHashSet

例如,存储在中的数字列表(概念上)在内存中看起来类似于:.1, 2, 3, 4, 5, 6, 7, 8List[1, 2, 3, 4, 5, 6, 7, 8]

将同一组数字存储在 中看起来更像这样:。在此示例中,列表已拆分为 4 个存储桶。Set[1, 2] [3, 4] [5, 6] [7, 8]

现在想象一下,您想从 和 中找到值。对于列表,您必须从列表的开头开始并检查每个值,直到达到6,这将需要6个步骤。使用一个集合,您可以找到正确的存储桶,检查该存储桶中的每个项目(在我们的示例中只有2个),使此过程成为一个3步骤。您拥有的数据越多,这种方法的价值就会显著增加。6ListSet

但是等等,我们怎么知道要看哪个桶呢?这就是该方法的用武之地。要确定要在其中查找项的存储桶,请调用 Java 哈希容器,然后对结果应用一些函数。此函数尝试平衡存储桶数和项目数,以实现尽可能快的查找。hashCodehashCode

在查找过程中,找到正确的存储桶后,该存储桶中的每个项目将像在列表中一样一次比较一个。这就是为什么在覆盖时还必须覆盖的原因。因此,如果任何类型的对象同时具有 方法和方法,则可以将其用作 中的键或 .要正确实现这些方法,必须遵循一个契约,这方面的规范文本来自Josh Bloch的伟大著作《Effective Java: Item 8:Always override hashCode,当你覆盖equals时总是覆盖hashCode”。hashCodeequalsequalshashCodeMapSet