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

Question

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

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

@Override public int hashcode()HashMap/HashSet 中的重要性是什么？这个哈希码在内部使用在哪里？
我通常看到 HashMap 的键是Stringlike myMap<String,Object>。我可以将值映射到someObject（而不是字符串）myMap<someObject, Object>吗？我需要遵守哪些合同才能成功实现？

提前致谢！

编辑：

我们是说键的哈希码（检查！）是哈希表中映射值的实际事物吗？而当我们在myMap.get(someKey);内部调用 javasomeKey.hashCode()来获取哈希表中的数字以查找结果值时呢？

回答：是的。

编辑2：

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

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

score 15 · Accepted Answer

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

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

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

编辑

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

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

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

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

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

编辑 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;
}

score 6 · Accepted Answer

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

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

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

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

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

在查找过程中，一旦找到正确的存储桶，该存储桶中的每个项目都会像列表一样一次比较一个。这就是为什么当你覆盖时你hashCode也必须覆盖equals。因此，如果任何类型的对象同时具有 anequals和 ahashCode方法，则它可以用作 a 中的键Map或 a 中的条目Set。为了正确实现这些方法，必须遵循一个合同，关于此的规范文本来自 Josh Bloch 的好书 Effective Java：Item 8: Always override hashCode when you override equals

score 5 · Accepted Answer

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

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

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

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

我可以将值映射到someObject（而不是String） likemyMap<someObject, Object>吗？

是的，但someObject必须是一个类，而不是一个对象（你的名字表明你想传入对象；应该SomeObject清楚地表明你指的是类型）。

我需要遵守哪些合同才能成功实现？

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

[编辑]

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

是的。

score 5 · Accepted Answer

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

覆盖等于。
覆盖哈希码。

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

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

这是来自 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;
}

从上面的代码可以看出，每个key的hashCode不仅用于map的hashCode()，还用于查找bucket来放置key,value对。这就是为什么 hashCode() 与 HashMap 的性能有关

score 3 · Accepted Answer

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

score 2 · Accepted Answer

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

public int hashCode()

返回对象的哈希码值。支持这种方法是为了哈希表的好处，例如由java.util.Hashtable.

hashCode 的一般合约是：

每当在 Java 应用程序执行期间对同一个对象多次调用它时，hashCode 方法必须始终返回相同的整数，前提是没有修改对象上的 equals 比较中使用的信息。该整数不需要从应用程序的一次执行到同一应用程序的另一次执行保持一致。

如果两个对象根据 equals(Object) 方法相等，则对两个对象中的每一个调用 hashCode 方法必须产生相同的整数结果。

如果根据 equals() 方法，如果两个对象不相等，则不需要对两个对象中的每一个java.lang.Object调用该hashCode方法都必须产生不同的整数结果。但是，程序员应该意识到，为不相等的对象生成不同的整数结果可能会提高哈希表的性能。

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

线

@Overrides public int hashCode()

只是告诉该hashCode()方法已被覆盖。这通常表明可以安全地使用类型作为 a 中的键HashMap。

是的，您可以轻松地使用任何遵守合约的对象equals()作为hashCode()密钥HashMap。

score 2 · Accepted Answer

Aaron Digulla 是绝对正确的。人们似乎没有意识到的一个有趣的附加说明是键对象的 hashCode() 方法没有逐字使用。事实上，它被 HashMap 重新散列，即它调用hash(someKey.hashCode))，其中hash()是一个内部散列方法。

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

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

score 2 · Accepted Answer

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

score 0 · Accepted Answer

HashSet、HashTable、HashMap 等集合类的 HashCode 方法 – 哈希码返回为哈希目的而支持的对象的整数。它是通过将对象的内部地址转换为整数来实现的。哈希码方法应该在每个覆盖equals方法的类中被覆盖。HashCode方法的三个通用联系方式

对于两个相等的对象 acc。等于方法，然后为两个对象调用 HashCode 它应该产生相同的整数值。
如果为单个对象多次调用它，那么它应该返回常量整数值。
对于两个不相等的对象 acc。等于方法，然后为两个对象调用 HashCode 方法，它不必须产生不同的值。

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

9 回答 9

Related

Reference