JavaSE|hashCode()方法和equals()方法

电玩女神 2022-02-15 15:46 359阅读 0赞

### JavaSE|hashCode方法和equals方法 ###

*  hashCode()
 *   *  源码规范
     *  hashCode() 在 HashMap 中的使用
     *  自定义的hashCode()方法
 *  equals(Object)
 *   *  源码规范
     *  equals(Object) 和 hashCode() 方法的关系
     *  equals(Object) 和 hashCode() 方法重写实例
 *  相关面试题

# hashCode() #

先看看什么是散列，散列就是将对象通过散列函数映射到一个空间中，以后每次找这个对象，只需用相同的散列函数计算即可知道该对象存放在哪里，而不必一个一个去遍历，所以我们知道散列是为了提高查询速度的。

每种数据类型都需要相应的散列函数，于是Java提供了默认实现，令所有数据类型都继承了一个能够**返回一个32bit整数**的hashCode()方法。  
默认的散列函数会返回一个**和对象内存地址相关的值**，但这只适用于很少的情况。  
Java 为很多常用的数据类型**重写了hashCode()方法**，包括**String、Integer、Double、File和URL**。

## 源码规范 ##

hashCode() Object类中的一个 **native方法**：

/**
 * 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}.
 * 
 * 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 not 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>
 * 
 * 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();

官方文档对该方法的描述：

hashCode() 方法**返回该对象的哈希码值**。支持该方法是为哈希表提供一些优点，例如，java.util.HashMap 提供的哈希表。

hashCode() 的一般规定是：

1.  每当在执行Java程序期间**多次在同一对象上**调用它时，hashCode() 方法必须**始终返回相同的整数**，前提是不修改对象上的equals() 比较中使用的信息。
2.  如果根据**equals(Object)方法两个对象相等**，则对两个对象调用 **hashCode()方法必须生成相同的整数**结果。
3.  如果根据**equals(Object)方法两个对象不相等**，则对两个对象调用 **hashCode()方法并不是必须生成不相同的整数**结果。但是，程序员应该知道为**不等对象生成不同的整数**结果可能会**提高哈希表的性能**。
4.  实际上，由 Object 类定义的 hashCode() 方法确实会**针对不同的对象返回不同的整数**。（这一般是通过将该对象的内部地址转换成一个整数来实现的，但是 JavaTM 编程语言不需要这种实现技巧。）

总结一下：

1.  hashCode()方法返回的是对象的 **哈希码值**，该方法是一个 **native 方法**（即该方法的实现由非java语言实现），具体的计算方法可能会和对象的内存地址有关联（hashCode()计算方法参见 文章： [https://www.jianshu.com/p/be943b4958f4）。][https_www.jianshu.com_p_be943b4958f4]
2.  Object 类定义的 hashCode() 方法确实会**针对不同的对象返回不同的整数**，所以hashCode() 相当于一个对象标识符，主要目的是**为查找提供快捷性**，可以用在HashMap、Hashtable、Set。
3.  equals(Object) 和 hashCode() 方法的关系，后面专门介绍。

## hashCode() 在 HashMap 中的使用 ##

public V put(K key, V value) {
 
 // 取关键字key的哈希值
 return putVal(hash(key), key, value, false, true);
 }
 
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
 
 Node<K,V>[] tab; 
 Node<K,V> p; 
 int n, i;
 //如果 table 还未被初始化，则初始化它
 if ((tab = table) == null || (n = tab.length) == 0)
 n = (tab = resize()).length;
 //根据(n - 1) & hash找到该键对应到数组中存储的索引
 	//如果为 null，那么说明此索引位置并没有被占用
 if ((p = tab[i = (n - 1) & hash]) == null)
 tab[i] = newNode(hash, key, value, null);
 else {
 // 如果哈希表当前位置上已经有节点的话，说明有hash冲突
 Node<K,V> e; 
 K k;
 //当前结点和将要插入的结点的 hash 和 key 相同，说明这是一次修改操作
 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);
 //如果插入后链表长度大于等于 8 ，将链表裂变成红黑树
 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
 treeifyBin(tab, hash);
 break;
 }
 //遍历的过程中，如果发现与某个结点的 hash和key，这依然是一次修改操作 
 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;
 }

哈希算法也称为散列算法，是将数据依特定算法直接指定到一个地址上。这样一来，当集合要添加新的元素时，先调用这个元素的HashCode方法，就一下子能定位到它应该放置的物理位置上。

（1）如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了，如源码所示，该位置没有元素则直接newNode；

if ((p = tab[i = (n - 1) & hash]) == null)
    	tab[i] = newNode(hash, key, value, null);

（2）如果这个位置上已经有元素了，就调用它的equals方法与新元素进行比较，相同的话就不存了；  
（3）不相同的话，也就是发生了Hash key相同导致冲突的情况，那么就在这个Hash key的地方产生一个链表，将所有产生相同HashCode的对象放到这个单链表上去，串在一起。这样一来**实际调用equals方法的次数**就大大降低了。

所以hashCode在上面扮演的角色为**寻域**（寻找某个对象在集合中区域位置）。hashCode可以将集合分成若干个区域，每个对象都可以计算出他们的hash码，可以将hash码分组，每个分组对应着某个存储区域，根据一个对象的hash码就可以确定该对象所存储区域，这样就大大减少查询匹配元素的数量，提高了**查询效率**。

在源码中：

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

可以看到，**先比较hash是否相等**，如果hash不相等则两者一定不相等，&& 运算返回 false；如果hash相等，再去比较key是否相等。这里提供了两种比较key是否相等的方法，一种是通过 “==”，一种是通过 equals(Object) 来比较。

这里存在的考量：

1.  hash 是 int 类型的变量，直接比较 hash 比较快；
2.  提供两种比较 key 的方式应该是因为**有些类重写了 equals(Object)方法**，比如说File、Date、String，以及包装类（Integer、Double等），在他们的“==”操作返回false的情况下，但equals(Object)可能返回true。（eg.当String作为键时）

String 类的 equals(Object) 方法：  
可以看到，在确定传入的Object是一个Stringl类的示例后，就要对两者进行**遍历**，元素挨个比较，会比较慢。  
而每个对象都有hashCode()方法，也就是说与一个哈希值相关联，哈希值是int类型，比较起来会很快。(为什么？比较 1 == 1 会比 ‘1’ == ‘1’ 快吗？）

/**
         * Compares this string to the specified object.  The result is {@code
         * true} if and only if the argument is not {@code null} and is a {@code
         * String} object that represents the same sequence of characters as this
         * object.
         *
         * @param  anObject
         *         The object to compare this {@code String} against
         *
         * @return  {@code true} if the given object represents a {@code String}
         *          equivalent to this string, {@code false} otherwise
         *
         * @see  #compareTo(String)
         * @see  #equalsIgnoreCase(String)
         */
        public boolean equals(Object anObject) {
        
            if (this == anObject) {
        
                return true;
            }
            if (anObject instanceof String) {
        
                String anotherString = (String)anObject;
                int n = value.length;
                if (n == anotherString.value.length) {
        
                    char v1[] = value;
                    char v2[] = anotherString.value;
                    int i = 0;
                    while (n-- != 0) {
        
                        if (v1[i] != v2[i])
                            return false;
                        i++;
                    }
                    return true;
                }
            }
            return false;
        }

## 自定义的hashCode()方法 ##

在Java中，所有的数据类型都继承了hashCode()方法，所以可以将对象中每个变量的hashCode()返回值转化为32位整数并计算得到的散列值，如下所示：

// 示例来自：《算法（第4版）》
    public class Transaction
    {
        
    	private final String who;
    	private final Date when;
    	private final double amout;
    	
    	public int hashCode(){
        
    		int hash = 17; // 这是啥
    		hash = 31 * hash + who.hashCode();
    		hash = 31 * hash + when.hashCode();
    		hash = 31 * hash + ((Double) amount).hashCode();
    		return hash;
    	}
    }

对于基本类型的对象，可以将其转化为对应的包装类型然后再调用hashCode()方法。

# equals(Object) #

## 源码规范 ##

equals(Object) 方法是Object类中的方法，Object类是所有类的超类。所有类都自动继承equals(Object) 方法，但子类中可以对其进行重写。

/**
 * Indicates whether some other object is "equal to" this one.
 * 
 * The {@code equals} method implements an equivalence relation
 * on non-null object references:
 * <ul>
 * <li>It is reflexive: for any non-null reference value
 * {@code x}, {@code x.equals(x)} should return
 * {@code true}.
 * <li>It is symmetric: for any non-null reference values
 * {@code x} and {@code y}, {@code x.equals(y)}
 * should return {@code true} if and only if
 * {@code y.equals(x)} returns {@code true}.
 * <li>It is transitive: for any non-null reference values
 * {@code x}, {@code y}, and {@code z}, if
 * {@code x.equals(y)} returns {@code true} and
 * {@code y.equals(z)} returns {@code true}, then
 * {@code x.equals(z)} should return {@code true}.
 * <li>It is consistent: for any non-null reference values
 * {@code x} and {@code y}, multiple invocations of
 * {@code x.equals(y)} consistently return {@code true}
 * or consistently return {@code false}, provided no
 * information used in {@code equals} comparisons on the
 * objects is modified.
 * <li>For any non-null reference value {@code x},
 * {@code x.equals(null)} should return {@code false}.
 * </ul>
 * 
 * The {@code equals} method for class {@code Object} implements
 * the most discriminating possible equivalence relation on objects;
 * that is, for any non-null reference values {@code x} and
 * {@code y}, this method returns {@code true} if and only
 * if {@code x} and {@code y} refer to the same object
 * ({@code x == y} has the value {@code true}).
 * 
 * Note that it is generally necessary to override the {@code hashCode}
 * method whenever this method is overridden, so as to maintain the
 * general contract for the {@code hashCode} method, which states
 * that equal objects must have equal hash codes.
 *
 * @param obj the reference object with which to compare.
 * @return {@code true} if this object is the same as the obj
 * argument; {@code false} otherwise.
 * @see #hashCode()
 * @see java.util.HashMap
 */
 public boolean equals(Object obj) {
 
 return (this == obj);
 }

官方文档对该方法的描述：

1.  equals(Object)方法指示某个其他对象是否\*\*“等于”\*\*此对象。
2.  equals(Object)方法在非null对象引用上实现**等价关系**：  
    **自反**：对于任何非空引用值\{@code x\}，\{@ code x.equals（x）\}应该返回\{@code true\}。  
    **对称**：对于任何非空引用值\{@code x\}和\{@code y\}，\{@ code x.equals（y）\}应返回\{@code true\}当且仅当\{@code y.equals （x）\}返回\{@code true\}。  
    **传递性**：对于任何非空引用值\{@code x\}，\{@ code y\}和\{@code z\}，如果\{@code x.equals（y）\}返回\{@code true\}和\{@代码y.equals（z）\}返回\{@code true\}，然后\{@code x.equals（z）\}返回\{@code true\}。  
    **一致性**：对于任何非空引用值\{@code x\}和\{@code y\}，\{@code x.equals（y）\}的多次调用始终返回\{@code true\}或一致返回\{@code false \}，如果修改了对象的\{@code equals\}比较中没有使用的信息。
3.  对于任何非空引用值\{@code x\}，\{@ code x.equals（null）\}应返回\{@code false\}。
4.  类\{@code Object\}的\{@code equals\}方法实现了对象上最具辨别力的可能等价关系;也就是说，对于任何非空引用值\{@code x\}和\{@code y\}，此方法返回\{ @code true\}当且仅当\{@code x\}和\{@code y\}**引用相同的对象**时（\{@code x == y\}具有值\{@code true\}）。
5.  请注意，**一旦覆盖此方法，通常需要覆盖\{@code hashCode\}方法**，以便维护\{@code hashCode\}方法的常规协定，该方法声明**相等的对象必须具有相同的哈希码**。

可以看到equals(Object)方法实际**使用“==”操作符进行比较**。所以下面说一下“==”操作符：

java中的数据类型，可分为两类：

1.  基本数据类型，也称原始数据类型（byte,short,char,int,long,float,double,boolean）
2.  复合数据类型(类)

“==”在比较**基本数据类型**时，直接比较他们的**值是否相等**；  
在比较**复合数据类型**时，比较的是他们在**内存中的存放地址**。

对于复合数据类型之间进行equals(Object)比较，在没有重写equals(Object)方法的情况下，他们之间的比较还是基于他们在内存中的存放地址。  
基本数据类型不能用equals(Object)方法比较，因为他们不具有这个方法，并且参数必须是Object类型的。

## equals(Object) 和 hashCode() 方法的关系 ##

String 类重写了 equals(Object)方法，所以为了保证equals(Object)结果和hashCode()比较时的一致性，需要重写hashCode()方法。String 类的 hashCode() 方法：

/**
 * Returns a hash code for this string. The hash code for a
 * {@code String} object is computed as
 * <blockquote><pre>
 * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 * </pre></blockquote>
 * using {@code int} arithmetic, where {@code s[i]} is the
 * ith character of the string, {@code n} is the length of
 * the string, and {@code ^} indicates exponentiation.
 * (The hash value of the empty string is zero.)
 *
 * @return a hash code value for this object.
 */
 public int hashCode() {
 
 int h = hash;
 // String 的 hash 值默认为0
 if (h == 0 && value.length > 0) {
 
 char val[] = value;
 
 for (int i = 0; i < value.length; i++) {
 
 h = 31 * h + val[i];
 }
 hash = h;
 }
 return h;
 }

String重写了hashCode()方法，通过 `h = 31 * h + val[i]`得到自己的hash值，可以看到String的每一位都参与了运算，**保证了String的内容相同时，其hashCode()相同。**

每一种数据类型的 hashCode() 方法都必须和 equals() 方法一致：  
1.如果 a.equals(b) 返回 true，那么 a.hashCode() 返回值必定和 b.hashCode() 返回值相同；  
2.如果两个对象 hashCode() 方法的返回值不同，那么这两个对象一定不同；  
3.如果两个对象 hashCode() 方法的返回值相同，这两个对象也可能不同，需要 equals() 方法进行判断。  
重写 equals() 方法时，有必要重写 hashCode() 方法，以维护 hashCode() 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。

hashCode是**用于查找使用**的，而equals是**用于比较两个对象是否相等**的。

（1）例如内存中有这样的位置 ：

0  1  2  3  4  5  6  7

而我有个类，这个类有个字段叫ID，我要把这个类存放在以上8个位置之一，如果不用HashCode而任意存放，那么当查找时就需要到这八个位置里挨个去找，或者用二分法一类的算法。  
但以上问题如果用HashCode就会使效率提高很多。 定义我们的HashCode为ID％8，比如我们的ID为9，9除8的余数为1，那么我们就把该类存在1这个位置，如果ID是13，求得的余数是5，那么我们就把该类放在5这个位置。依此类推。

（2）但是如果两个类有相同的HashCode，例如9除以8和17除以8的余数都是1，也就是说，我们先通过 HashCode来判断两个类是否存放某个桶里，但这个桶里可能有很多类，那么我们就需要**再通过equals在这个桶里找到我们要的类**。

## equals(Object) 和 hashCode() 方法重写实例 ##

一个equals(Object)结果和hashCode()不一致的例子：

public class HashTest {
 
 private int i; 
 
 public int getI() {
 
 return i; 
 } 
 
 public void setI(int i) {
 
 this.i = i; 
 } 
 
 public int hashCode() {
 
 return i % 10; 
 } 
 
 public final static void main(String[] args) {
 
 HashTest a = new HashTest(); 
 HashTest b = new HashTest(); 
 a.setI(1); 
 b.setI(1); 
 Set<HashTest> set = new HashSet<HashTest>(); 
 set.add(a); 
 set.add(b); 
 System.out.println(a.hashCode() == b.hashCode()); 
 System.out.println(a.equals(b)); 
 System.out.println(set); 
 }

输出结果为：

true
    false
    [HashTest@1, HashTest@1]

在上面代码中重写了hashCode()方法，a和b的hashCode相同，但是由于没有重写equals(Object)，equals(Object)的结果不同，HashSet内部组合一个HashMap，其add()方法是调用HashMap的put()方法实现的。所以如前面对HashMap的put()方法的分析可以知道，当添加b时，因为和a的hashCode()一样，所以它也找到了a的位置，这个时候会进而比较两者的equals(Object)方法，返回为false（默认比较的内存地址），所以会插入一个新节点。这和HashSet **只能存储不重复的对象** 的含义相矛盾。

public boolean add(E e) {
        
            return map.put(e, PRESENT)==null;
        }

所以我们需要重写equals(Object)方法：

public class HashTest {
 
 private int i; 
 
 public int getI() {
 
 return i; 
 } 
 
 public void setI(int i) {
 
 this.i = i; 
 } 
 
 public boolean equals(Object object) {
 
 if (object == null) {
 
 return false; 
 } 
 if (object == this) {
 
 return true; 
 } 
 if (!(object instanceof HashTest)) {
 
 return false; 
 } 
 HashTest other = (HashTest) object; 
 if (other.getI() == this.getI()) {
 
 return true; 
 } 
 return false; 
 }
 
 public int hashCode() {
 
 return i % 10; 
 } 
 
 public final static void main(String[] args) {
 
 HashTest a = new HashTest(); 
 HashTest b = new HashTest(); 
 a.setI(1); 
 b.setI(1); 
 Set<HashTest> set = new HashSet<HashTest>(); 
 set.add(a); 
 set.add(b); 
 System.out.println(a.hashCode() == b.hashCode()); 
 System.out.println(a.equals(b)); 
 System.out.println(set); 
 } 
 }

重写的equals(Object)方法，保证了 i 相等时返回为 true，和hashCode()结果一致，这样上面程序就可以得到符合我们认知的结果：

true
    true
    [HashTest@1]

还有一点，  
**同一对象在执行期间若已经存储在集合中，则不能修改影响hashCode值的相关信息，否则会导致内存泄露问题。**  
具体参见 [https://blog.csdn.net/lijiecao0226/article/details/24609559。][https_blog.csdn.net_lijiecao0226_article_details_24609559]

# 相关面试题 #

Q1：hashCode()的作用是什么？ -> hashCode()相同怎么办？  
A1： hashCode()方法返回的是对象的哈希码值，主要作用是是为HashMap、Hashtable、Set等容器提供查找的便捷性；在通过hashCode()定位的过程中，如果hashCode()相等，这时候再去调用equals(Object)方法，从而判断是否为同一对象

Q2：为什么有的类需要重写hashCode()方法？  
A2：hashCode()方法是一个native方法，其值与对象的内存地址相关，不同对象的的hashCode()返回值不同。举个例子，对于String类，将其作为Set的键值时，因为Set元素具有唯一性，所以具有相同内容的String其应该是一个键（eg, String s1=“a”, s2 = “a”），而不应是两个，但如果不重写hashCode()方法，则s1和s2的hashCode()是不同的，会落在不同的桶里，所以导致会添加两个元素进去。所以我们重写String的hashCode()方法，使得内容相同的String其hashCode()也相同，这个时候他们会落在同一个桶中，进一步比较equals(Object)方法，如果equals(Object)为true，则他们会被认定成同一对象，不会给s2新new一个结点出来，但equals(Object)默认比较的是内存地址是否相同，返回false，这时候会认为s2是一个不同的元素，新new一个结点，所以我们需要同时重写equals(Object)方法，使得其返回值为true。

Q3：哈希算法是可逆的吗，为什么？  
A3：Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种**压缩映射**，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而**不可能从散列值来唯一的确定输入值**。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

参考内容：  
[https://www.cnblogs.com/yangming1996/p/7997468.html][https_www.cnblogs.com_yangming1996_p_7997468.html]  
实例来自：[https://www.cnblogs.com/guodao/p/9702464.html][https_www.cnblogs.com_guodao_p_9702464.html]  
[https://blog.csdn.net/lijiecao0226/article/details/24609559][https_blog.csdn.net_lijiecao0226_article_details_24609559 1]  
《算法（第4版）》

[https_www.jianshu.com_p_be943b4958f4]: https://www.jianshu.com/p/be943b4958f4%EF%BC%89%E3%80%82
[https_blog.csdn.net_lijiecao0226_article_details_24609559]: https://blog.csdn.net/lijiecao0226/article/details/24609559%E3%80%82
[https_www.cnblogs.com_yangming1996_p_7997468.html]: https://www.cnblogs.com/yangming1996/p/7997468.html
[https_www.cnblogs.com_guodao_p_9702464.html]: https://www.cnblogs.com/guodao/p/9702464.html
[https_blog.csdn.net_lijiecao0226_article_details_24609559 1]: https://blog.csdn.net/lijiecao0226/article/details/24609559