java.util.HashMap 和 HashSet 的内部实现 [英] Internal implementation of java.util.HashMap and HashSet

问题描述

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

I have been trying to understand the internal implementation of java.util.HashMap and java.util.HashSet.

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

Following are the doubts popping in my mind for a while:

1. @Override public int hashcode() 在 HashMap/HashSet 中的重要性是什么?这个哈希码在内部使用在哪里?
2. 我通常看到 HashMap 的键是 String，例如 myMap.我可以将值映射到 someObject(而不是 String)，例如 myMap<someObject, Object>?我需要遵守哪些合同才能成功实现这一目标?

1. Whats is the importance of the @Override public int hashcode() in a HashMap/HashSet? Where is this hash code used internally?
2. I have generally seen the key of the HashMap be a String like myMap<String,Object>. Can I map the values against someObject (instead of String) like myMap<someObject, Object>? What all contracts do I need to obey for this happen successfully?

提前致谢！

1. 我们是说键的哈希码(检查！)是哈希表中映射值的实际对象吗?而当我们执行 myMap.get(someKey); 时，java 在内部调用 someKey.hashCode() 来获取哈希表中的数字以查找结果值?

1. Are we saying that the hash code of the key (check!) is the actual thing against which the value is mapped in the hash table? And when we do myMap.get(someKey); java is internally calling someKey.hashCode() to get the number in the Hash table to be looked for the resulting value?

回答:是的.

编辑 2:

1. 在java.util.HashSet中，Hash表的key是从哪里生成的?是否来自我们正在添加的对象，例如.mySet.add(myObject); 那么 myObject.hashCode() 将决定这个在哈希表中的位置?(因为我们不在 HashSet 中提供键).

1. In a java.util.HashSet, from where is the key generated for the Hash table? Is it from the object that we are adding eg. mySet.add(myObject); then myObject.hashCode() is going to decide where this is placed in the hash table? (as we don't give keys in a HashSet).

答案:添加的对象成为键.该值是虚拟的！

Answer: The object added becomes the key. The value is dummy!

推荐答案

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

The answer to question 2 is easy - yes you can use any Object you like. Maps that have String type keys are widely used because they are typical data structures for naming services. But in general, you can map any two types like Map<Car,Vendor> or Map<Student,Course>.

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

For the hashcode() method it's like answered before - whenever you override equals(), then you have to override hashcode() to obey the contract. On the other hand, if you're happy with the standard implementation of equals(), then you shouldn't touch hashcode() (because that could break the contract and result in identical hashcodes for unequal objects).

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

Practical sidenote: eclipse (and probably other IDEs as well) can auto generate a pair of equals() and hashcode() implementation for your class, just based on the class members.

编辑

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

For your additional question: yes, exactly. Look at the source code for HashMap.get(Object key); it calls key.hashcode to calculate the position (bin) in the internal hashtable and returns the value at that position (if there is one).

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

But be careful with 'handmade' hashcode/equals methods - if you use an object as a key, make sure that the hashcode doesn't change afterwards, otherwise you won't find the mapped values anymore. In other words, the fields you use to calculate equals and hashcode should be final (or 'unchangeable' after creation of the object).

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

Assume, we have a contact with String name and String phonenumber and we use both fields to calculate equals() and hashcode(). Now we create "John Doe" with his mobile phone number and map him to his favorite Donut shop. hashcode() is used to calculate the index (bin) in the hash table and that's where the donut shop is stored.

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

Now we learn that he has a new phone number and we change the phone number field of the John Doe object. This results in a new hashcode. And this hashcode resolves to a new hash table index - which usually isn't the position where John Does' favorite Donut shop was stored.

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

The problem is clear: In this case we wanted to map "John Doe" to the Donut shop, and not "John Doe with a specific phone number". So, we have to be careful with autogenerated equals/hashcode to make sure they're what we really want, because they might use unwanted fields, introducing trouble with HashMaps and HashSets.

编辑 2

如果将对象添加到 HashSet 中，则 Object 是内部哈希表的键，值已设置但未使用(只是 Object 的静态实例).这是来自 openjdk 6 (b17) 的实现:

If you add an object to a HashSet, the Object is the key for the internal hash table, the value is set but unused (just a static instance of Object). Here's the implementation from the 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;
}

这篇关于java.util.HashMap 和 HashSet 的内部实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！