equals & hash code 와 이를 같이 재정의 하는 이유

프로그래머스 백엔드 데브코스에서 진행한 Tech Log 활동 목적으로 제작되었습니다.

 

1. String 클래스의 equals & hashcode

소프트웨어 세계에서는 문자열도 이상한 방식으로 관리한다.

바로 동등성을 보장해주기 위함인데,

이때 앞에서 말한 equals 메소드와 HashCode 메소드를 재정의해서 사용한다.

 

이를 재정의하지 않는 클래스를 처음부터 만들어가면서 equals 와 HashCode 에 대해 알아보자

본문에서는 String을 모방한 String_test 객체를 만들어 볼것이며 , 각각의 결과값들을 맞춰나갈 것이다.

equals 비교

먼저 객체의 동등성을 비교하기 위해 equals의 값을 비교해보자

String string1 = new String("hi");
String string2 = new String("hi");

System.out.println("String 객체 hashcode 비교 결과 : "+(string1.equals(string2)));

String_test string1_test = new String_test("hi");
String_test string2_test = new String_test("hi");

System.out.println("String 객체 hashcode 비교 결과 : "+(string1_test.equals(string2_test)));

 

같은 값을 가지는  클래스끼리 비교하였지만

String 객체는 equals 의 true이고 ,

String_test는 equals 의 값이 false 가 나왔다.

hashcode 비교

다음은 객체의 hashcode 값을 비교해보자

String string1 = new String("hi");
String string2 = new String("hi");

System.out.println("String 객체 hashcode 비교 결과 : "+(string1.hashCode() == string2.hashCode()));

String_test string1_test = new String_test("hi");
String_test string2_test = new String_test("hi");

System.out.println("String_test 객체 hashcode 비교 결과 : "+(string1_test.hashCode() == string2_test.hashCode()));

해쉬코드 비교 결과값도 String 객체와 다르게 나오는 것을 볼 수 있다.

 

🧐 왜 이런 결과가 나왔을까?

 

정답은 equals 와 hashcode 의 오버라이딩에 있다.

 

이 둘을 재정의 하기 전에 각각 원래 무슨 역할을 하는 메소드인지 부터 알아보자

2. equals 란 ?

equals 메소드는 2개의 객체가 동등한 지 검사하기 위해 사용되는 메소드이다.

 

예를 들어,

String string1 = new String("hi");
String string2 = new String("hi");

System.out.println(string1 == string2); // false
System.out.println(string1.equals(string2)); // true

다음과 같이 String 클래스를 생성하여 비교하는 경우 "==" 는 동일성을 비교하기 때문에 false 를 출력하지만 , equals 메소드는 동등성을 비교하기 때문에 true를 출력한다.

 

*동등성과 동일성의 차이는 뭘까?

동등성은 대상의 대상의 내용을 비교하고

동일성은 주소값을 비교하여 같은 객체인 지를 비교한다.

 

Object 클래스의 equals 코드를 살펴보자

public boolean equals(Object obj) {
			return this == obj;
    }

근데 정작 Object의 코드를 보면 동등성을 비교해주지 않는다 .(주소값을 비교한다.)

그런데 왜 String 에서는 문자열의 동등성을 비교할 수 있는 걸까?

 

자바 공식문서에 보면 String의 equals 메소드는 다음과 같이 equals 메소드를 재정의 한다고 나와있다.

그렇기에 우리는 equals 메소드를 동등성 비교에 사용할 수 있는 것이다 !

 

그러면 String_test 메소드에도 이런 방식으로 equals를 재정의 하면 동등성 비교가 되지 않을까 ?

우리가 만든 Spring_test 클래스에도 equals 를 재정의 해주었다.

 

class String_test {
    String string;

    public String_test(String string) {
        this.string = string;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        String_test that = (String_test) o;
        return Objects.equals(string, that.string);
    }
}

그리고 결과값도 의도한 대로 true 가 나왔다 !

3. hashCode란 ?

hashCode 메소드는 객체의 해시코드를 리턴한다.

 

*객체의 해시코드란?

객체의 주소값을 변환하여 생성한 고유의 해시값이다.

 

하지만 기존 방식으로 해시코드를 생성한다면 다른 객체에 대해서 다른 문자열이라도 다른 해시코드를 받을 것이다.

→ 이렇게 된다면 동등성을 보장할 수 없다 !

 

따라서 String 클래스는 hashCode 역시 재정의해서 사용한다.

 

자바 공식 문서를 보면 문자열의 문자들을 한 글자씩 가져와서 변환한다는 것을 알 수 있다.

 

그렇기에 다른 주소값의 객체라도 문자열이 같으면 같은 hashcode 가 나오는 것이다.

따라서 우리가 만든 Spring_test 클래스도 hashCode 를 재정의 해보았다.

 

class String_test {
    String string;

    public String_test(String string) {
        this.string = string;
    }

    @Override
    public int hashCode() {
        return Objects.hash(string);
    }
}

String 객체처럼 Spring_test 객체도 같은 값이 나옴을 알 수 있다.

Hash 와 Hash 테이블의 관계

hashCode 메소드를 이용해서 해시코드 값을 받는 다는 것을 알게되었다.

이렇게 얻게 된 해시코드는 어디에 사용되는 걸까?

 

hashCode 와 equals 의 관계를 알기 전 우리는 해시테이블이라는 자료구조에 대해 알아볼 것이다.

 

🧐 자료구조? 그게 뭔가요?

 

도서관에는 정말 많은 책들이 있다.

 

만약 자기가 사서 관리를 맡았는 데 이 많은 책들 중에서 특정 책을 찾거나 정리해야 한다고 생각하면 여간 막막한 일이 아닐 것이다.

 

다행히 이런 일들을 우리가 처음 겪은 게 아니고 옛날부터 많은 기술자들이 고안한 끝에 데이터를 쉽게 찾고 꺼내올 수 있는 규칙과 틀을 미리 만들어 두었다.

 

이것들 중에 하나가 우리가 알아볼 해시 테이블이다.

 

해시테이블이란?

데이터를 key , value 로 저장하는 형태를 말한다.

보통 도서관에서는 도서 관리 번호를 지정하고 , 그 번호를 찾아보면 해당 책을 발견할 수 있다.

이것도 현실 세계에서의 key , value 형태라고 부를 수 있을 것이다.

 

해시 테이블의 원리

다시 소프트웨어로 돌아와서 이러한 형태의 해시 테이블이 어떻게 만들어지는 지 알아보자

도서관의 책들을 key , value 형태로 저장하려고 한다.

 

이때 key는 책 이름 , value는 가격으로 해주었다.

그 결과, 가장 오른쪽에 있는 Bucket에는 해쉬 연산을 통해 나온 인덱스와 value(책 가격) 이 담긴다.

 

이런식으로 저장을 하게 되면 데이터를 찾을 때 Hash 연산을 한번만 수행하면 되므로 매우 빠르게 데이터를 조회할 수 있다.

→ 이런 경우 시간 복잡도는 O(1) 이 된다 !

 

🧐 그런데 만약 서로 다른 책들끼리 같은 해쉬 연산 결과가 나와서 같은 인덱스에 저장된다면 어떻게 될까 ?

이 문제를 해결하기 위한 대표적인 방법 두가지를 소개해보려고 한다.

Separate Chaining 기법

해쉬테이블에서는 하나의 인덱스에 여러 개의 버킷을 연결시키는 것으로 해결할 수 있다.

다시 그림을 보자

분명 다른 책인데, 같은 인덱스에 저장이 되었다.

즉 해시 충돌이 발생하니까 새로운 값을 기존 값과 연결시킨 거라고 볼 수 있다.

 

하지만 이렇게 하면 버킷에 하나의 데이터만 저장하는 것 보다 효율이 안좋아진다.

기존엔 해시 함수 결과에 따라 해당 인덱스만 찾아가면 됐었는데 , 이제는 그 안에서 한번 더 탐색을 해야하기 때문이다.

최악의 경우 모든 데이터를 뒤져봐야 할 수도 있다.

→ 시간복잡도는 평균적으로 O(n/m) 최악의 경우 O(n) 을 가지게 될 수 있다.

(해시 테이블의 저장소(Bucket)의 길이를 ‘m’, 키(key)의 수를 ‘n’)

 

이를 보완하기 위해 자바8 이상부터는 하나의 해시 버킷에 할당 된 데이터가 8개 이상이 되면 연결 리스트에서 트리로 구조를 변경한다.

→ 이럴 경우 평균 적인 시간 복잡도는 O(log(n/m)) 이 된다.

 

Open addressing 기법 (개방 주소법)

개방 주소법은 해시값의 인덱스에 데이터가 있을 시에 다른 인덱스를 탐색하여 데이터를 저장하는 방법이다.

같은 인덱스에 여러 개의 데이터를 저장하는 방법과는 상반된 방법이다 !

 

해시 충돌이 발생 했을 시에 어느 인덱스에 데이터를 저장할 것인지를 결정하는 방법은 총 3가지가 있다.

 

선형 탐색 (linear probing)

충돌이 일어났을 때, 한칸 또는 n칸씩 다음 인덱스가 비어있는지 확인해본다.

제곱 탐색 (quadratic probing)

1의 제곱 , 2의 제곱 … 만큼 인덱스를 이동해가면서 비어있는지 확인해본다.

이중 해시 (Double Hash)

위에 두 방법을 통해서 어느 정도 충돌을 해결할 순 있다.

 

하지만 해쉬값이 같을 경우 빈 슬롯을 찾아 접근하는 위치가 동일하므로

접근 슬롯을 중심으로 데이터가 한 곳에 집중되어 있는 현상이 발생할 수 있다.

 

이 상황을 피하기 위해 나온 방법이 이중 해시이다.

말 그대로 해시 함수를 두 번 돌린 것이다.

 

예를 들어,

1차 해시는 키를 삽입하여 데이터의 해시 인덱스를 정한다.

2차 해시는 충돌이 발생하였을 시에 몇 칸 뒤로 인덱스를 이동할 지 정한다.

이처럼 이중 해시를 사용하면 1차 해시값이 같더라도 2차 해시값은 달라지므로,

데이터의 군집 문제를 어느정도 해결할 수 있다.

 

개방 주소법의 경우에도 해당 인덱스에 충돌이 발생했었다면 다음 인덱스를 찾아가면서 탐색을 해야하므로 최악의 경우 O(n) 의 시간 복잡도를 가질 수 있다.

 

🧐 근데 데이터가 점점 많아진다면 어떻게 될까 ?

아마 해쉬 충돌은 빈번해지며 효율은 더욱 나빠질 것이다.

(참고로 자바에서 제공하는 기본 버킷 사이즈는 16이다)

이 상황에 대해 묘사한 재밌는 이론이 있다.

 

비둘기 집 원리

만약 9개의 비둘기 집이 있는 데 10마리 이상의 비둘기가 들어가려고 한다면?

어쩔 수 없이 2마리 이상의 비둘기가 함께 지내야 할 것이다.

이 상황은 무한한(비둘기) 입력에 대해 유한한(비둘기 집) 출력만이 존재하기 때문에 나타난 현상이라고 할 수 있다.

 

소프트웨어에서도 마찬가지다.

key값은 무한하지만 버킷 과 해쉬값 은 유한하다.

이 경우 해쉬테이블은 Dynamic Resizing 을 통해서 버킷의 사이즈를 두 배씩 늘려준다.

 

이때 늘릴 수 있는 최대 길이는 2^30 이다 !

이제 HashCode의 역할과 해시 값을 이용한 해시 테이블도 알아보았으니

이쯤에서 equals and hashcode에 대해 알아보자

4. equals 와 hashcode 을 왜 같이 재정의 해줘야할까 ?

위에서 보았듯이 일반적으로 equals 와 hashcode 는 같이 오버라이딩 해주고 있다.

만약 equals만 오버라이딩 해준다면 여러 문제가 발생할 수 있는데 , 대표적으로 해쉬 자료구조를 사용할 때이다.

중복을 허용하지 않는 set를 예로 들어보자

같은 값의 객체를 넣어준다면 하나만 들어가야 정상일 것이다.

equals만 오버라이딩 하였을 경우

class Test {
    String key;

		public Test(String key) {
        this.key = key;
    }
		
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Test test = (Test) o;
        return Objects.equals(key, test.key);
    }    
}

Set<Test> set = new HashSet<>();
        
set.add(new Test("hi"));
set.add(new Test("hi"));

System.out.println(set.size()); // 결과 2

같은 값을 가지는 객체를 넣어줬는데 두개가 들어가는 결과가 나왔다.

이는 Hash 테이블에서 같은 값을 가짐에도 다른 객체로 인식하였다는 것이다.

hashCode 만 오버라이딩 하였을 경우

class Test {
    String key;

    public Test(String key) {
        this.key = key;
    }

    @Override
    public int hashCode() {
        return Objects.hash(key);
    }
}

Set<Test> set = new HashSet<>();
        
set.add(new Test("hi"));
set.add(new Test("hi"));

System.out.println(set.size()); // 결과 2

마찬가지로 같은 값을 가지는 객체를 넣어줬는데 두개가 들어가는 결과가 나왔다.

이 경우도 같은 값을 가짐에도 다른 객체로 인식하였다는 것이다.

 

🧐 왜 Equals와 HashCode 둘 중 하나만 재정의 하였을 시에 오류가 나는 걸까 ?

이 이유를 알기 위해 해쉬 자료구조의 동작 원리를 순서대로 알아보자

해쉬 맵의 동작 구조

해쉬 자료구조에서 객체가 동등한 지를 비교할 땐 다음 과정을 거친다.

1. 해쉬코드의 값을 비교한다.
2. 해쉬코드의 값이 같다면 equals의 값을 비교한다.
3. 위 두개의 값이 같다면 동등 객체라고 판단한다.

따라서 ,

equals만 재정의 하였을 경우 해쉬코드가 다르게 나왔기 때문이고

hashCode 만 재정의 하였을 경우 equals의 반환값이 false 였기 때문에 다른 객체로 보았던 것이다.

 

이처럼 둘을 동시에 재정의 해주지 않으면, Hash 자료구조를 사용하면서 예상치 못한 결과를 불어올 수 있다.

 

4. equals & hashCode 규약

1. equals() 비교에 사용되는 정보가 변경되지 않았다면, 애플리케이션이 실행되는 동안 그 객체의 hashcode()는 항상 같은 값을 반환해야한다.
2. equals()로 비교했을 때 같다고 판단했다면, 두 객체의 hashCode는 같은 값을 반환해야 한다.
3. equals()가 두 객체를 다르다고 판단한 경우 꼭 hashCode가 다를 필요는 없다.
4. 다른 값을 반환하는 게 좋다.

5. 결론

해시코드와 equals의 차이에 대해 알아보고 , 이 둘을 왜 같이 재정의 해줘야하는지에 대해서도 알아보았다.

만약 이 둘을 같이 재정의 해주지 않는다면 위처럼 해쉬 자료구조를 이용할 때 예상치 못한 결과를 가져온다.

동등성을 보장해주지 못하기 때문에 다른 객체로 인식이 되기 때문이다.

따라서 equals와 hashCode 를 같이 재정의 하도록 하자 !

6.참고 자료

Java HashMap은 어떻게 동작하는가?

equals와 hashCode는 왜 같이 재정의해야 할까?

equals와 hashCode는 왜 같이 재정의해야 할까?

Hashtable의 이해와 구현 #1

Hashtable의 이해와 구현 #1

equals와 hashCode는 왜 같이 재정의해야 할까?

equals와 hashCode는 왜 같이 재정의해야 할까?

[데이터 구조] Hashtable 충돌(collisoion)을 해결하는 방법에 대해서 이해가 필요하다. (open addressing, separate chaining) +설명영상

[데이터 구조] Hashtable 충돌(collisoion)을 해결하는 방법에 대해서 이해가 필요하다. (open addressing, se