hashcode方法的注释
从下面的注释中可以得出以下几点重要信息:
- 如果两个对象通过
equals方法比较返回true, 那么这两个对象的hashcode()方法返回值也必须一样. - 如果用于
equals中比较的信息在运行时没有被改变, 那么该对象的hashcode()方法在每次被调用时的返回值应该是相同的. -
hashcode()返回的hashcode不一定要每次都一致 (比如说用于equals方法中的信息在运行时发生了变化, 那么hashcode应该也会做出相应的变化) -
不要求两个
equals不等的对象,hashcode也要不同. 即允许两个不equals的对象, 有相同的hashcode. 不过, 如果equals不同的对象,hashcode也不同的话, 可能提高hash table(这里应该是泛指使用了哈希的数据结构) 的性能. (本文后面会讲为什么可能提高性能).
/**
* Returns a hash code value for the object. This method is
* supported for the benefit of hash tables such as those provided by
* {@link java.util.HashMap}.
* <p>
* The general contract of {@code hashCode} is:
* <ul>
* <li>Whenever it is invoked on the same object more than once during
* an execution of a Java application, the {@code hashCode} method
* must consistently return the same integer, provided no information
* used in {@code equals} comparisons on the object is modified.
* This integer need not remain consistent from one execution of an
* application to another execution of the same application.
* <li>If two objects are equal according to the {@code equals(Object)}
* method, then calling the {@code hashCode} method on each of
* the two objects must produce the same integer result.
* <li>It is <em>not</em> required that if two objects are unequal
* according to the {@link java.lang.Object#equals(java.lang.Object)}
* method, then calling the {@code hashCode} method on each of the
* two objects must produce distinct integer results. However, the
* programmer should be aware that producing distinct integer results
* for unequal objects may improve the performance of hash tables.
* </ul>
* <p>
* As much as is reasonably practical, the hashCode method defined by
* class {@code Object} does return distinct integers for distinct
* objects. (This is typically implemented by converting the internal
* address of the object into an integer, but this implementation
* technique is not required by the
* Java™ programming language.)
*
* @return a hash code value for this object.
* @see java.lang.Object#equals(java.lang.Object)
* @see java.lang.System#identityHashCode
*/
public native int hashCode();
实例
equals()比较相同, 但是hashcode()不同的两个对象, 对于使用hashcode的集合类来说, 会造成什么问题呢?
首先我们实现这么一个类, equals比较相等, 但是hashcode不同.
注意java7以后, 可以使用Objects.hash()方法来计算哈希值.
Objects.hash()方法如下:
public static int hash(Object... values) {
return Arrays.hashCode(values);
}
我们的不符合规范的类:
public static class HashcodeNotCorrespondingToEquals{
private int id;
private String name;
public HashcodeNotCorrespondingToEquals(int id, String name){
this.id = id;
this.name = name;
}
@Override
public boolean equals(Object obj) {
if (obj == null) return false;
if (!(obj instanceof HashcodeNotCorrespondingToEquals)) return false;
return name.equals(((HashcodeNotCorrespondingToEquals) obj).name);
}
@Override
public int hashCode() {
return Objects.hash(id);
}
}
测试:
public static void testHashCodeBug(){
Set<HashcodeNotCorrespondingToEquals> set = new HashSet<>();
HashcodeNotCorrespondingToEquals bad1 = new HashcodeNotCorrespondingToEquals(1, "wrong");
HashcodeNotCorrespondingToEquals bad2 = new HashcodeNotCorrespondingToEquals(2, "wrong");
HashcodeNotCorrespondingToEquals bad3 = new HashcodeNotCorrespondingToEquals(1, "test");
boolean equals = bad1.equals(bad2);
// true
System.out.println(String.format("%s: %s", "bad1.equals(bad2)", equals));
set.add(bad1);
// false
System.out.println(String.format("set.contains(bad2): %s", set.contains(bad2)));
// false
System.out.println(String.format("set.contains(bad3): %s", set.contains(bad3)));
}
输出:
bad1.equals(bad2): true
set.contains(bad2): false
set.contains(bad3): false
逻辑上来说bad1和bad2应该是相同的东西, 对于set来说应该只能存在其中一个, 但是从第二条输出可以看出set并没有认为两者相等.
究其原因, 是因为HashSet利用了HashMap实现其功能. 可以看到HashSet的add方法如下:
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
其中map就是一个HashMap实例, 而PRESENT是
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
为何两个key是equals的, 但是还是能将两个key都加进去呢? 我们来看看HashMap的put方法如何实现:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put方法调用了putVal方法, 这里直接给出putVal方法.
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
我们主要看以下一部分:
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// .....省略.....
可以看到HashMap是用hashcode来找到对应的tab下标, 即通过对hashcode的处理, 可以找到一个tab的下标, 而tab[(n-1) & hash]即是用来存放某一类hash值的key的, 这里也体现了对不同对象相同hash值的冲突的处理.
正是因为找tab下标这个过程仅使用了hash值, 所以如果key是equals的, 但是hashcode不同, 那么得到的tab下标也很有可能是不同的, 所以可能会导致在tab链中找不到以前加入的和当前key本质上相等的key, 导致set的行为被破坏.
注意这条if判断,
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
从这里可以看出为什么如果实现了equals不同, hashcode也不同的话, 可能会提高hash结构的效率. HashMap检查这个key是否存在, 会依据hashcode来找下标, 然后在对应下标的tab链中, 寻找可能和现在要加的key相等的key.
如果之前加入的某个key的p.hash(p用于遍历现存的key)和当前想要加入的key的hash是不同的, 那么根据短路求值, 后面&&部分根本不会计算了, 所以效率会更高.
