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

Question

我一直在尝试了解 java.util.HashMap 和 java.util.HashSet 的内部实现。

以下是我脑海中暂时浮现的疑问：

1. HashMap/HashSet 中的 @Override public int hashcode() 有何重要性？这个哈希码在内部哪里使用？
2. 我通常认为 HashMap 的键是一个 String，如 myMap。我可以像 myMap 那样将值映射到 someObject （而不是字符串）吗？为了成功实现这一目标，我需要遵守哪些合同？

提前致谢 ！

编辑：

1. 我们是说键的哈希码（检查！）是哈希表中值映射的实际内容吗？当我们执行 myMap.get(someKey); java 内部调用 someKey.hashCode() 来获取哈希表中要查找结果值的数字？

答案：是的。

编辑2：

2. 在java.util.HashSet中，哈希表的密钥从哪里生成？是否来自我们要添加的对象，例如。 mySet.add(myObject); 那么 myObject.hashCode() 将决定将其放置在哈希表中的位置？ （因为我们不在 HashSet 中给出键）。

答案：添加的对象成为关键。价值是虚拟的！

Answer 1

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

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

实用旁注：Eclipse（可能还有其他 IDE）可以根据类成员自动为您的类生成一对 equals() 和 hashcode() 实现。

编辑

对于您的附加问题：是的，完全正确。看一下HashMap.get(Object key);的源码它调用 key.hashcode 来计算内部哈希表中的位置（bin）并返回该位置的值（如果有）。

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

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

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

问题很明显：在本例中，我们希望将“John Doe”映射到 Donut 商店，而不是“具有特定电话号码的 John Doe”。因此，我们必须小心自动生成的 equals/hashcode，以确保它们是我们真正想要的，因为它们可能会使用不需要的字段，从而给 HashMap 和 HashSet 带来麻烦。

编辑2

如果向 HashSet 添加一个对象，则该对象是内部哈希表的键，该值已设置但未使用（只是对象的静态实例）。这是 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;
}

Answer 2

像 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 哈希容器调用 hashCode，然后对结果应用一些函数。此函数尝试平衡存储桶的数量和项目的数量，以尽可能实现最快的查找。

在查找过程中，一旦找到正确的存储桶，就会像在列表中一样一次比较该存储桶中的每个项目。这就是为什么当您覆盖 hashCode 时，您还必须覆盖 equals。因此，如果任何类型的对象同时具有 equals 和 hashCode 方法，则它可以用作 Map 中的键或一个集合。为了正确实现这些方法，必须遵循一项合同，该合同的规范文本来自 Josh Bloch 的伟大著作《Effective Java》：第 8 项：重写 equals 时始终重写 hashCode

Answer 3

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

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

这个哈希码在内部哪里使用？

绝不。此代码的存在只是为了让您可以将一个地图用作另一个地图中的键。

我可以像 myMap 一样将值映射到 someObject （而不是 String）吗？

是的，但是 someObject 必须是一个类，而不是一个对象（你的名字表明你想要传入对象；它应该是 SomeObject 以明确你所指的是类型）。

为了成功实现这一目标，我需要遵守哪些合同？

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

[编辑]

我们是说键的哈希码（检查！）是哈希表中值映射的实际内容吗？

是的。

Answer 4

是的。您可以使用任何对象作为 HashMap 中的键。为此，您必须遵循以下步骤。

1. 覆盖等于。

2. 覆盖哈希码。

java.lang.Object 的文档中非常清楚地提到了这两种方法的约定。 http://java.sun.com/javase/6 /docs/api/java/lang/Object.html

是的，hashCode() 方法由 HashMap 内部使用，因此返回正确的值对于性能非常重要。

这是 HashMap 中的 hashCode() 方法 从

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

上面的代码可以清楚地看出，每个键的 hashCode 不仅仅用于映射的 hashCode()，而且还用于查找放置键、值对的桶。这就是为什么 hashCode() 与 HashMap 的性能有关

Answer 5

1. Java 中的任何Object 都必须有一个hashCode() 方法； HashMap 和 HashSet 也不例外。如果将哈希映射/集合插入另一个哈希映射/集合，则使用此哈希代码。
2. 任何类类型都可以用作 HashMap/HashSet 中的键。这要求 hashCode() 方法为相等的对象返回相等的值，并且 equals() 方法根据契约（自反、传递、对称）实现。 Object 的默认实现已经遵守这些约定，但如果您想要值相等而不是引用相等，您可能需要覆盖它们。

Answer 6

Java 中的 equals()、hashcode() 和哈希表之间通常存在着复杂的关系（就此而言，.NET 也是如此）。引用文档：

public int hashCode()

<块引用>

返回对象的哈希码值。支持此方法是为了利用哈希表（例如 java.util.Hashtable 提供的哈希表）。

hashCode的通用约定是：

• 每当在 Java 应用程序执行期间对同一对象多次调用 hashCode 方法时，如果对象的 equals 比较中使用的信息没有被修改，则 hashCode 方法必须始终返回相同的整数。从应用程序的一次执行到同一应用程序的另一次执行，该整数不需要保持一致。
• 如果根据 equals(Object) 方法，两个对象相等，则对这两个对象调用 hashCode 方法必须产生相同的整数结果。
• 不要求如果两个对象根据 equals(java.lang.Object) 方法不相等，则对这两个对象分别调用 hashCode 方法对象必须产生不同的整数结果。但是，程序员应该意识到，为不相等的对象生成不同的整数结果可能会提高哈希表的性能。

在合理实用的情况下，Object 类定义的 hashCode 方法确实为不同的对象返回不同的整数。 （这通常是通过将对象的内部地址转换为整数来实现的，但 Java™ 编程语言不需要这种实现技术。）

该行

@Overrides public int hashCode()

仅表明 hashCode() 方法是被覆盖。这通常表明在HashMap中使用该类型作为键是安全的。

是的，您可以轻松地使用任何遵守 HashMap 中的 equals() 和 hashCode() 约定的对象作为键。

Answer 7

在回答问题 2 时，虽然您可以使用任何可用作 HashMap 中的键的类，但最佳实践是使用不可变类作为 HashMap 的键。或者至少如果您的“hashCode”和“equals”实现依赖于类的某些属性，那么您应该注意不要提供更改这些属性的方法。

Answer 8

亚伦·迪古拉（Aaron Digulla）是绝对正确的。人们似乎没有意识到的一个有趣的附加说明是，关键对象的 hashCode() 方法没有逐字使用。事实上，它是由 HashMap 重新哈希的，即它调用 hash(someKey.hashCode))，其中 hash() 是一种内部哈希方法。

要了解这一点，请查看源代码： http://kickjava.com /src/java/util/HashMap.java.htm

原因是有些人对 hashCode() 的实现很差，而 hash() 函数给出了更好的哈希分布。这基本上是出于性能原因而完成的。

Answer 9

HashCode 方法适用于 HashSet、HashTable、HashMap 等集合类 - 哈希代码返回支持哈希目的的对象的整数。它是通过将对象的内部地址转换为整数来实现的。在每个重写 equals 方法的类中都应该重写哈希码方法。
HashCode 方法的三个一般联系

• 对于两个相等的对象按照。到 equal 方法，然后为两个对象调用 HashCode，它应该生成相同的整数值。

• 如果为单个对象多次调用它，那么它应该返回常量整数值。

  如果为

• 对于两个不相等的对象，根据。到 equal 方法，然后为两个对象调用 HashCode 方法，不强制它应该产生不同的值。