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

问题描述

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

以下是我心中一阵疑惑：

1. 在HashMap / HashSet中， @Override public int hashcode（）的重要性如何？内部使用这个散列码在哪里？


2. 我一般认为HashMap的关键是 String 就像 MYMAP<字符串，对象> 。我可以将值映射到 someObject （而不是String），如 myMap< someObject，Object> ？我所需要的所有合同都符合这一要求吗？

预先致谢！

编辑：

1. 我们是否说密钥的哈希码（check！）是值在哈希表中映射到的实际东西？当我们做 myMap.get（someKey）; java在内部调用 someKey.hashCode（）来获得数字在哈希表中查找结果值？

答案：是。

编辑2：

2. java.util.HashSet ，从哪里为哈希表生成的密钥？它来自我们正在添加的对象，例如。 mySet.add（myObject）; 然后 myObject.hashCode（）将决定将其放置在散列中的位置表？ （因为我们不在HashSet中给密钥）。

答案：添加的对象变成键。值是假的！

解决方案

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

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

实用注释：eclipse（也可能是其他IDE）可以自动为您的类生成一对equals（）和hashcode（）实现，仅基于类成员。 >

编辑

另外还有一个问题：是的。查看HashMap.get（Object key）的源代码;它调用key.hashcode来计算内部哈希表中的位置（bin），并返回该位置的值（如果有的话）。

但要小心'手工'hashcode / equals方法 - 如果你使用一个对象作为关键字，确保后面的hashcode不会改变，否则你不会再找到映射的值。换句话说，用于计算equals和hashcode 的字段应该是final （或者在创建对象后不可更改）。

假设，我们与字符串名称和字符串phonenumber 有联系，我们使用这两个字段来计算equals（）和hashcode （）。现在我们用他的手机号码创建John Doe，并将他映射到他最喜欢的甜甜圈店。 hashcode（）用于计算散列表中的索引（bin），这是存储甜甜圈店的地方。

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

问题很明显：在这我们想要将John Doe映射到甜甜圈店，而不是John Doe使用特定的电话号码。所以，我们必须小心自动生成的equals / hashcode，以确保它们是我们真正想要的，因为它们可能使用了不需要的字段，引入了HashMaps和HashSets的麻烦。

<如果你添加一个对象到一个HashSet中，Object是内部散列表的关键字，那么这个值就被设置成了

Edit 2 但未使用（只是Object的静态实例）。这里是openjdk 6（b17）的实现：

pre $ //与支持Map $ b中的Object关联的虚拟值$ b private static final Object PRESENT = new Object（）;
私有瞬态HashMap< E，Object>地图;

public boolean add（E e）{
return map.put（e，PRESENT）== null;
}


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. 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?

Thanks in advance !

EDIT:

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?

Answer: Yes.

EDIT 2:

2. 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!

解决方案

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>.

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).

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.

Edit

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).

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).

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.

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.

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.

Edit 2

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屋！