HashCode 사용하는 이유

자바에서 Collection을 사용하는 단순한 연산이 특정 상황에서 비효율적일 수 있기 때문에 hashCode를 사용한다.

 

예를 들면 다음과 같다.

List<String> words = Arrays.asList("Welcome", "to", "junwoo");
if (words.contains("junwoo"){
	System.out.println("Junwoo is in the list");
}

"junwoo"가 있는지 확인하는 위의 코드는 List의 사이즈가 커질수록 비효율적인 선형탐색 과정을 거친다.

 

hashCode의 이해

• hashCode는 hashing 알고리즘에 의해 만들어진 Integer 값을 리턴한다.
• 똑같은 Object는 반드시 똑같은 hashCode를 리턴해야 하지만 반대는 필수적이지 않다.

두 번째의 경우 개발자들이 유의할 점이 있다.
동일하지 않은 Object에 대해 다른 hashCode를 리턴하는 것이 필수적이지 않더라도
다른 hashCode를 만드는 것이 hashTable 성능 향상에 도움을 준다.

 

hashCode의 구현

구현 1

public class User {
    private long id;
    private String name;
    private String email;
    
    // standard getters/setters/constructors
    
    @Override
    public int hashCode(){
    	return 1;
    }
    
    @Override
    public boolean equals(Object o){
    	if(this == 0) return true;
        if(o == null) return false;
        if(this.getClass() != o.getClass()) return false;
        User user = (User) o;
        return id == user.id
        	&& (name.equals(user.name) && email.equals(user.email));
    }
}

User 클래스는 위에 명시한 기준을 고수하여 equals()와 hashCode()를 재정의하였다.

다만 hashCode()는 고정된 값을 리턴하도록 설계였을 뿐이다.

 

그러나 이러한 방법은 hashTable 성능을 퇴화시킨다. 

왜냐하면 모든 Object들이 단일 버킷에 저장되기 때문이다.

 

구현 2

@Override
public int hashCode(){
	return (int) id * name.hashCode() * email.hashCode();
}

현재 hashCode를 개선해보면 User 클래스에 존재하는 모든 필드들을 이용하여 

다른 Object에 대해서는 다른 hashCode를 리턴하도록 설계할 수 있다.

일반적으로 equals() 일관성을 유지하는 한 합리적인 hashCode 구현이라고 할 수 있다.

 

구현 3

@Override
public int hashCode(){
	int hash = 7;
    hash = 31 * hash + (int) id;
    hash = 31 * hash + (name == null ? 0 : name.hashCode());
    hash = 31 * hash + (email == null ? 0 : email.hashCode());
    return hash;
}

해시 코드를 계산하는데 사용하는 해시 알고리즘이 좋을수록 해시 테이블 성능이 향상된다.

위 코드는 두개의 소수를 이용하여 hashCode를 계산하였다.

---

그러나 우리는 equals를 구현할 때마다 이러한 복잡한 방식으로 hashCode를 구현하지 않는다.

왜냐하면 우리가 사용하는 IDE에서 커스텀한 hashCode를 정의해주기 때문이다.

또한 7 버전 이후 JAVA는 안전한 해싱을 위한 hash() 메서드를 제공해준다.

Objects.hash(name, email)

 

IntelliJ에서 hashCode 정의

@Override
public int hashCode(){
	int result = (int) (id ^ (id >>> 32));
    result = 31 * result + name.hashCode();
    result = 31 * result + email.hashCode();
    return result;
}

 

eclipse에서 hashCode 정의

@Override
public int hashCode(){
	final int prime = 31;
    int result = 1;
    result = prime * result + ((email == null) ? 0 : email.hashCode());
    result = prime * result + ((int)(id ^ (id >>> 32));
    result = prime * result + ((name == null) ? 0 : name.hashCode());
    return result;
}

우리가 주목해야 할 점은 hashCode를 구현하는 점에서 31이라는 숫자를 사용하는 것이다.

이유는 곱셈보다 bit shift가 훨씬 빠르기 때문이다.

31 * i == (i << 5) - i

위와 같이 31을 곱하는 것은 정수를 왼쪽으로 5번 shift해서 빼는 결과랑 동일하다.

 

31이란 32 - 1 이다.

32는 2의 5승(2^5)이며 결국 31 = 2^5 - 1 이다.

따라서 2^5는 왼쪽으로 5번 shift한 결과와 같다.

 

결과적으로 32 = (<<5) -1 이다.

쉽게 말하면 곱셈보다 비트 연산의 성능이 훨씬 빨라 31을 곱하는 것은 비트 연산을 사용해

계산할 수 있기때문에 hashCode 는 31값을 선택할 것이다.

 

참조 : Guide to hashCode() in Java | Baeldung

Guide to hashCode() in Java | Baeldung