Overriding Equals, HashCode and CompareTo in Java

In this Java program, we will override all three method for a Person class, which contains a String name, an integer id and a Date for date of birth. In order to override equals, you need to follow certain checks, e.g. checking null, checking type of object etc, Also your equals() method, when compared with null, should return false instead of throwing NullPointerException.

See this post for detailed tips on overriding equals method in Java. For overriding hashCode, you need to choose a prime, usually 31, but you can also choose other prime numbers e.g. 37, 17 etc. The reason for choosing these prime numbers are to generate a uniquely distributed hash code, which eventually helps to avoid collision, when used in hash based collections like Hash table and HashMap.

Sample implementation of Equals, HashCode and CompareTo in Java

In this sample example of overriding equals, hashcode and compareTo method, we will use a class named Person which has 3 properties String name, int id and Date to represent date of birth. We will also use Generics along with Comparable to provide a type safe implementation. Remember we have used getClass() method instead of instance of operator, which means a Person class cannot be equal to its subclass, this could create problem if you are using this class in EJB or any application server, where there is a chance that same class is loaded by two separate class loader.

On those cases its better to use instance of operator because it will allow a Class to be equal to its subclass if rest of properties matched. This is also true for framework like Hibernate, which provides proxy implementation, which is essentially sub class of entity classes. In short, use instance of if your class can be loaded by multiple class loader or it can be used by framework to create proxies.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/**
 * Simple Java Class to represent Person with name, id and date of birth.
 */
public class Person implements Comparable<Person>{
   private String name;
   private int id;
   private Date dob;

    public Person(String name, int id, Date dob) {
        this.name = name;
        this.id = id;
        this.dob = dob;
    }
  
   @Override
   public boolean equals(Object other){
       if(this == other) return true;
      
       if(other == null || (this.getClass() != other.getClass())){
           return false;
       }
      
       Person guest = (Person) other;
       return (this.id == guest.id) &&
              (this.name != null && name.equals(guest.name)) &&
              (this.dob != null && dob.equals(guest.dob));
   }
  
    @Override
   public int hashCode(){
       int result = 0;
       result = 31*result + id;
       result = 31*result + (name !=null ? name.hashCode() : 0);
       result = 31*result + (dob  !=null ? dob.hashCode() : 0);
      
       return result;
   }

    @Override
    public int compareTo(Person o) {
        return this.id - o.id;
    }   
}

Sample JUnit test case for testing Equals and HashCode

Here is simplest of simple test case to verify equals and hashCode in Java. Remember this unit test is not enough, if you want to verify all properties of equals and hashCode. If you should write test cases to check if it verify key properties of equals and hashcode method e.g. if a equal b then b should also be equal to a, or if a a equals b and b equals c then a and c should also be equal to each other. You must also verify whether compareTo() return 0 for equal object and return non zero value for non equal objects.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import java.util.Date;
import org.junit.Test;
import static org.junit.Assert.*;

/**
 * Simple example of using equals and hashCode method
 */
public class EqualsAndHashCodeTest {   

  
   @Test
   public void testEquals(){
       Person james = new Person("James", 21, new Date(1980,12, 1));
       Person same = new Person("James", 21, new Date(1980,12, 1));
       Person similar = new Person("Harry", 21, new Date(1981,12,1));
      
       assertTrue(james.equals(same));
       assertTrue(james.hashCode() == same.hashCode());
    
       assertFalse(james.equals(null));
       
       assertFalse(james.equals(similar));
       assertTrue(james.hashCode() != similar.hashCode());
   } 
  
}

Question

How does the order of the loops affect performance when iterating over a 2D array?

Like the code below:

1
2
3
4
5
6
7

int[][] array = new int[100][100];
for(int i = 0 ; i < 100 ; i++ ){
    for(int j = 0 ; j < 100 ; j++ ){
        System.out.printlin(array[j][i]); // column first
        System.out.printlin(array[i][j]); // row first
    }
}

Which one is more efficient?

Answer

It depends on what programming language you are using.

To answer this question, the first thing you need to know is whether your programming language is row-major or column-major. It will decide the way that how does the computer store 2-D array in 1-D array in memory.

• Row-major order is used in C)/C++/Objective-C (for C-style arrays), Mathematica, PL/I, Pascal), Speakeasy), SAS, and C#)/CLI/.Net.

• Column-major order is used in Fortran, OpenGL and OpenGL ES, MATLAB, GNU Octave, S-Plus R),Julia), Scilab.

• A typical alternative is to use Iliffe vectors, which store elements in the same row contiguously (like row-major order), but not the rows themselves. They are used in Java), Scala) and Swift).

But why does this matter? All memory accesses are the same, right?

NO. Because of CPU caches.

A CPU cache is a hardware cache used by the Central Processing Unit (CPU) of a computer to reduce the average time to access data from the main memory. The cache is a smaller, faster memory which stores copies of the data from frequently used main memory locations.

Data from memory gets brought over to the CPU in little chunks (called ‘cache lines’), typically 64 bytes. If you have 4-byte integers, that means you’re getting 16 consecutive integers in a neat little bundle. It’s actually fairly slow to fetch these chunks of memory.

If you access the data in a consecutive memory order, every time you access a variable, it will directly read from CPU cache. 100*100/16 times fetches from memory.

But if you access the data in a nonconsecutive memory order, it will fetch the data from memory to CPU cache. 100*100 times fetches from memory.

It is very obvious that which way is more efficient.

Question

Implement int sqrt(int x).

Compute and return the square root of x.

Implement pow(x, n).

Solution

• For function pow(), the most important axiom we use is x^n = x^n/2 * x^n/2.

  • we need to consider whether n is odd or even number.
  • we need to consider whether n is negative or positive number.

• One way of calculating square root is to use Newton’s method to find a solution for the equation, giving the iterative formula:

  

  Another way to calculate square root is to use binary search. The square root of x must be in [1,x]. So we can do binary search from 1 to x.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  //pow() function public class Solution { public double myPow(double x, int n) { if(n<0){ // if x^-n = 1/x^n; return 1/pow(x,-n); } return pow(x,n); } private double pow(double x, int n){ // time complexity from O(n) -> O(logn); if( n == 0 ){ return 1; } double v = pow(x,n/2); if(n % 2 == 0){ // if n is EVEN , x^n == x^(n/2) * x^(n/2); return v*v; }else{ return v*v*x; // if n is ODD, x^n = x* x^(n/2) * x^(n/2); } } }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

  //square root function suing Binary Search public class Solution { public int mySqrt(int x) { if( x == 0 || x == 1){ return x; } int start = 0; int end = x; int mid = 0; while( start <= end ){ mid = start + (end - start)/2; if( mid < x/mid){ if( mid + 1 > x/(mid + 1) ){ // if x between mid and mid+1, return mid return mid; } start = mid + 1; }else if ( mid > x/mid ){ end = mid - 1; }else{ return mid; } } return mid; } } //square root function suing Newton's methond. public class Solution { public int mySqrt(int x) { if(x<2) return x; long r = x/2; while (r*r > x){ r = (r + x/r) / 2; } return (int)r; } }

  ​

Problem

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given

For example, given
s = "leetcode",

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Solution

The core of this question is substring matching.

We can use dynamic programming to store if the substring exist in word dic.

F(0,N) = F(0,i) && F(i,j) && F(j,N)

First of all, we get the words’ length range in dictionary. Then use a boolean array to store if from 0 to this position can be segmented into a space-separated sequence of one or more dictionary words.

If dp[i] == true, we search substring of index form i to j ( j In [ i+minWordLength, i+maxWordLength] ). If s[i,j] exist in Dic, set dp[j] = true.

Finally, dp[s.length()] is the result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if( s == null || s.length() == 0 || wordDict.size() == 0 ){
            return false;
        }
        if( wordDict.contains(s) ){
            return true;
        }
        int maxWordLength = 0;
        int minWordLength = Integer.MAX_VALUE;
        for( String str : wordDict ){
            maxWordLength = Math.max(maxWordLength, str.length() );
            minWordLength = Math.min(minWordLength, str.length() );
        }
        
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        
        for(int i = 0 ; i <= s.length(); i++ ){
            if( dp[i] == false ) continue;
            
            for(int j = i+minWordLength; j <= i+maxWordLength && j <= s.length(); j++){
                if( dp[j] == true ) continue;
                String word = s.substring(i,j);
                if( wordDict.contains(word) ){
                    dp[j] = true;
                }
            }
        } 
        
        return dp[s.length()];
    }
}

Question

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example:

For example:
"112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

1

"199100199"

is also an additive number, the additive sequence is:

1

1, 99, 100, 199

.

1

1 + 99 = 100, 99 + 100 = 199

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits '0'-'9', write a function to determine if it’s an additive number.

Solution

The idea is quiet basic.

1. Choose the first number A, it can be the leftmost 1 up to i digits. i<=(L-1)/2, because the third number should be at least as long as the first number.

2. Choose the second number B, it can be the leftmost 1 up to j digits excluding the first number. The limit for j is in 2 conditions:

   • if the length of second number( j - i ) is longer than the first number( i ), then the third number’s length( L - j ) should >= ( j - i ).

   • if the length of second number( j - i ) is shorter than or equals to the first number( i ), then the third number’s length( L - j ) should >= i .

3. Recursively check if there is one solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Solution {
    public boolean isAdditiveNumber(String num) {
        int L = num.length();
        
        for(int i = 1; i <= (L-1)/2 ; i++ ){  // Length of A is from 1 to (L-1)/2. 
            
            if( num.charAt(0) == '0' && i>=2 ) break;
            // Length of B is from 1 to L-(A+B),and L-(A+B) >= max(A,B)
            for( int j = i+1; (L-j) >= i && (L-j) >= j-i ; j++ ){ 
         
              if( num.charAt(i) == '0' && j-i>=2 ) break;      
              
              long A = Long.parseLong( num.substring(0,i) );
              long B = Long.parseLong( num.substring(i,j) );
              String substr = num.substring(j);
              
              if( isAdditive( substr , A, B) == true ) return true; 
            }
        }
        return false;
    }
    
    private boolean isAdditive(String str, long A,long B){
        if( str.equals("") ) return true;
        long sum = A + B;
        String sumStr = String.valueOf(sum);
        if( !str.startsWith(sumStr) ) return false;
        
        return isAdditive( str.substring(sumStr.length()), B, sum);
    }
}