hashcode and equals

1. Overview

Stands for hashing algorithms to search efficiently used in HashMap, HashSet, and so on. Searching element within collection using hash code as address.

2. Procedure

3. Terminology

3.1 Uniqueness

The same Objects which are true on equal() respectively must generate the same hash code.

Different Object prefers to generate different hash code for performance of searching, but shouldn't be unique.

3.2 Collisions

Having the same hash code even if Objects are not equal. Incapacitate merit of hashing algorithms.

4. Description

class Student {
    private int id;
    private String name;
    public Student(int id, String name) {
        this.name = name;
        this.id = id;
    }
    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (!(obj instanceof Student))
            return false;
        if (obj == this)
            return true;
        return this.getId() == ((Student) obj).getId();
    }
    @Override
    public int hashCode() {
        return id;
    }
}

public class demo {
    public static void main(String[] args) {
        Student alex1 = new Student(1, "Alex");
        Student alex2 = new Student(1, "Alex");
        HashSet< Student > students = new HashSet < Student > ();
        students.add(alex1);
        students.add(alex2);
        System.out.println("HashSet size = " + students.size());
        System.out.println("HashSet contains Alex = " + students.contains(new Student(1, "Alex")));
    }
}

// output 
HashSet size = 1 // without custom equals, it is 2
HashSet contains Alex = true // without custom hashcode, it is false

4.1 equals()

overriding equals() with our custom business forces Java to consider the ID attribute when comparing two Student objects.

4.2 hashcode()

HashSet stores its elements in memory buckets. Each bucket is linked to a particular hash code. When calling students.add(alex1), Java stores alex1 inside a bucket and link it to the value of alex1.hashcode(). Now any time an element with the same hash code is inserted into the set, it will just replace alex1. However, since alex2 has a different hash code, it will be stored in a separate bucket and will be considered a totally different object.

4.3 Relationship between equals() and hashcode()

• If two objects are equal, they MUST have the same hash code.
• If two objects have the same hash code, it doesn't mean that they are equal.
• Overriding equals() alone will make your business fail with hashing data structures like: HashSet, HashMap, HashTable ... etc.
• Overriding hashcode() alone doesn't force Java to ignore memory addresses when comparing two objects.

5. Example

5.1 Primitive Array hashcode() and equals()

private static class Point {
        int[] point;

        public Point(int[] point) {
            this.point = point;
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(this.point);
        }

        @Override
        public boolean equals(Object obj) {
            Point other = (Point) obj;
            return point[0] == other.row() && point[1] == other.col();
        }
        public int row() {
            return point[0];
        }
        public int col() {
            return point[1];
        }

        @Override
        public String toString() {
            return "Point{" +
                    "point=" + Arrays.toString(point) +
                    '}';
        }
    }

6. Reference

https://dzone.com/articles/working-with-hashcode-and-equals-in-java

https://www.baeldung.com/java-hashcode

https://en.wikipedia.org/wiki/Hash_table#Separate_chaining_with_linked_lists

https://minwan1.github.io/2018/07/03/2018-07-03-equals,hashcode/