Java equals() & hashcode()

equals()

---

public boolean equals(Object obj)

 

두 non-null object x, y에 대해 x.equals(y)는 x와 y가 "같은"지 체크한다. 여기서, "같다"라는 것은, 즉 true를 return하는 경우는 오직(if and only if) x, y가 같은 object를 참조하는 경우 뿐이다. 

hashCode()

---

public int hashCode()

 

해당 object의 hash code value를 return한다.

hashcode에는 아래와 같은 일반적인 규약이 있다.

• Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in 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.
• If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
• It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the 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.

hash code value는 JVM에 의해 결정된 "the internal address"이다. 

참고) "the internal address"는 Garbage Collection 기능 때문에 고정적인 memory address가 아니다.

 

위의 2번 째 규칙처럼, x.equals(y)가 true면 x와 y의 hashcode는 같다. 하지만 역은 성립하지 않는다.

(이유: hash code value는 int 값으로, 2^32 이 최대 key 개수이므로 hash collision이 불가피하다. 이 때문에 서로 다른 object여도 code value가 같을 수도 있다.)

 

equals(), hashCode() override

---

사용자가 만든 class의 객체들이 서로 같은지 비교해야 할 때가 있다. Java에서 사용자가 만든 class는 모두 Object class를 상속 받고 있기에, 위에서 설명한 Object class의 equals(), hashCode() method를 사용할 수 있다. 하지만, 위의 method들은 같은 object를 참조하는 경우에만 "같다"고 인정한다. 따라서, 때때로 사용자가 만든 class에서 두 method를 override할 필요가 있다.

예시

다음과 같은 Student class를 만들었다고 하자.

public class Student{
    int id;
    String name;
    
    public Student(int id, String name){
        this.id = id;
        this.name = name;
    }
}

동일한 value를 지닌 Student s1, s2를 각각 만들었다고 하자.

Student s1 = new Student(1, "dreamchaser3");
Student s2 = new Student(1, "dreamchaser3");

이 둘은 같은 학생이지만, 위의 equals()를 쓰면 false를 return한다.(서로 다른 객체이므로)

 

위 class에서 equals()를 override하자.

public class Student{
    int id;
    String name;

    public Student(int id, String name){
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object obj){
        if(s1.id == s2.id && s1.name.equals(s2.name)){
            return true;
        }else{
            return false;
        }
    }
}

위 상태에서 s1.equals(s2)를 수행하면, true를 return한다.

 

이렇게 equals() method를 override했으면, hashCode() method도 override해주어야 한다. 그 이유는 다음과 같다.

 

1. 규약적 원인

위의 hashCode() 단에서 일반적 규약에 대해 언급한 바 있다.
그 중 2번 째 항목을 보면,

• If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
  
  

equals() method가 두 object가 "같다"고 한다면, hashCode()도 같은 value를 return해야 한다고 되어 있다.

 

2. 실례적 원인

사실 위의 규약적 원인은 실제적인 이유가 되지 못하고, 오히려 그 규약은 여기서 이야기 할 실례적 원인에 의해 생겨난 규약이라고 할 수 있다. 실례적인 원인은 HashSet, HashTable, HashMap과 같은 Java에서 hash를 사용하는 자료 구조에서 hashcode value를 사용함에서 기인한다. 우선, 대표적으로 HashMap의 동작 과정을 살펴보자.

 

HashMap의 동작과정

---

HashMap에서 bucket index를 결정할 때, 다음과 같은 방식을 사용한다. (Java8 기준)

int index = X.hashCode() % M;

앞서 언급한 바와 같이, hash code value는 int형으로 최대 2^32 개의 숫자 범위를 가진다. 그렇다면, 모든 HashMap object가 그 범위의 bucket index를 모두 커버하려면 2^32 size의 array를 가져야한다. 따라서 memory를 절약하기 위해, 처음 M개(default: 16)의 bucket으로 시작하고, (load factor(default: 0.75) * M) 만큼의 data가 들어가면, (M = M *2), 즉 2배로 bucket의 수를 늘려나간다. 여하튼 위와 같은 방식으로 bucket에 담으면, 1/M의 확률로 같은 bucket에 담기게 된다. 이렇게 hash collision이 발생하더라도 특정 data를 잘 찾을 수 있도록 Java에서는 Seperate Chaining을 채택한다.

→ Separate Chaining: hash 값이 중복되면 node들을 pointer로 연결한다.

• 참고) hash collision에 의해 index 값이 중복되는 경우 말고도, 실제로 이미 존재하는 object가 key 값으로 insert되는 경우도 있을 것이다. 따라서 index 값이 동일한 경우에는 해당 index bucket을 순회하며, equals() method로 이미 존재하는 object인지 확인하고, 이미 존재한다면 해당 object의 value를 새로 들어온 value로 교체한다.

Java8에서는 Separate Chaining을 구현하는 자료구조로 linked list와 tree(Red-Black-Tree)를 모두 사용한다. 여기서 tree 구조는 child node를 2개씩 갖기 때문에 pointer의 개수가 각 노드 당 2개씩이므로 linked list보다 더 많은 memory를 차지한다. 따라서, node 개수가 적은 경우에는 linked list가 더 효율적이다. 그러나, node 개수가 많아지면 순회 시간이 O(logN/M)으로 줄어드므로(linked list - O(N/M)) tree를 쓰는 것이 더 효율적이다.

static final int TREEIFY_THRESHOLD = 8; 
static final int UNTREEIFY_THRESHOLD = 6;

따라서, Java8은 위처럼 같은 bucket에 담긴 node의 개수가 6이하면 linked list로 구현하고, 8이상이면 tree로 구현한다.

두 threshold의 값의 차이가 2인 것은, 특정 data가 반복되어 삽입/삭제 되는 경우 불필요하게 계속해서 자료구조가 바뀌는 현상이 생기는 것을 방지하기 위함이다.

 

그러나, 앞서 살짝 언급했던 바와 같이, bucket의 수 M은 (load factor * M)만큼 차면, M이 2배가 된다. 즉, M은 2^a 이다. 여기서 문제가 발생하는데, hashCode() 값이 고루 분포되었다 할지라도, M(=2^a )으로 나누면 결국 하위 a비트만 사용하게 된다. 따라서, hash collision이 많이 발생할 것이다. 이에 따라, Java HashMap에서는 보조 해시 함수를 쓰는데, Java8에서의 보조 해시 함수는 다음과 같다.

static final int hash(Object key) { 
    int h; 
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 
}

→ 상위 16비트 값을 XOR 연산한다.

 

결론적으로 HashMap에서의 key 값으로 들어온 object X의 index 값을 결정하는 것은 다음과 같다.

int hash = X.hashCode();
int index = hash ^ (hash >>> 16); 

 

다시, hashCode()를 equals()와 함께 override해야하는 실례적 원인으로 돌아오자. 위의 예시를 다시 들면,

Student s1과 s2는 override된 equals()에 의해 동일한 객체로 간주된다. 그런데 만일,

HashMap<Student, String> advisors = new HashMap<Student, String>;
advisors.put(s1, "Prof.Lee");
advisors.put(s2, "Prof.Lee");

라고 한다면, s1과  s2는 같은 object이므로 key 값 충돌이 발생해야한다. 하지만, Student class의 hashCode()가 override되지 않아 s1과 s2는 대개 같은 hashCode를 지니지 않을 것이다. 위의 HashMap의 동작 과정에서 설명했듯이, key object의 hashCode()를 이용해 bucket index를 결정한다. 결국 equals()에 의해 동일한 객체로 간주됨에도 hash data structure에 버젓이 서로 다른 key-value pair로 존재하게 된다. 이러한 이유로 equals()를 override할 때에는 hashCode()도 함께 override해주어야 한다.

 

참고

---

https://docs.oracle.com/javase/7/docs/api/java/lang/Object.html

https://stackoverflow.com/questions/13860194/what-is-an-internal-address-in-java

https://stackoverflow.com/questions/4360035/why-can-hashcode-return-the-same-value-for-different-objects-in-java

http://d2.naver.com/helloworld/831311

http://skylit.tistory.com/35