hashCode()란

원본 글: https://www.baeldung.com/java-hashcode

해싱은 컴퓨터공학에서 기초적인 개념입니다.
Java에서 해싱이 가장 널리 사용되는곳은 HashMap같은 자료구조에 있습니다.

이 글에서는 hashCode()가 어떻게 동작하는지 보고 어떻게 효율적으로 쓸 수 있는지 살펴봅니다.

1. Using hashCode() in Data Structures

길이 가 긴 리스트에서 특정 값을 찾는 이런 특수한 경우에는 문제상황 그대로 코드를 구현하면 비효율적으로 동작할 수 있습니다.

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

Java에서는 위와같은 문제를 해결하기 위한 여러 자료구조가 있습니다. 예를들어서 hash tables를 구현한 Map같은게 있습니다.
hash tables를 사용하게 되면, 입력받은 key값을 기준으로 hashCode() 함수를 동작시켜 해시 값을 계산합니다. 이후 다음에 이 값에 대한 접근하는 것을 더 효율적으로 하기위해 내부적으로 이 값을 사용하여 저장합니다.

2. Understanding How hashCode() Works

보통 hashCode()함수에 값을 넣으면 hashing 알고리즘을 통해서 정수값을 리턴합니다.
같은 객체는 항상 같은 값의 해쉬값을 리턴하게 되고, 서로 다른 객체에 대해서는 서로 다른 해쉬값을 리턴하게 됩니다.
다음은 hashCode()함수 상태에 대한 규칙입니다.

• 하나의 Java application에서 같은 객체가 두번이상 hashCode()가 호출되어도 일반적으로 그 리턴값은 항상 같습니다.
• 만약 두 객체의 equals(Object)함수의 값이 같다면, hashCode()함수의 값도 같습니다.
• 만약 두 객체가 equals(Object) 메서드에 따라 서로 다르다면, hashCode() 메서드의 반환값이 반드시 서로 달라야 하는 것은 아닙니다. 그러나, 서로 다른 객체에 대해 서로 다른 해시 코드 값을 생성하면 해시 테이블의 성능이 향상될 수 있습니다.

3. A Naive hashCode() Implementation

위 방침을 준수한 User 클래스라는 예시를 만들어보겠습니다.

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 obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (this.getClass() != obj.getClass()) return false;
        User user = (User) obj;
        return id == user.id
                && (name.equals(user.name))
                && (email.equals(user.email));
    }

    // getters and setters here

}

User클래스는 hashCode()와 equals()함수를 각각 구현하였습니다. 그리고 hashCode()함수값은 1을 리턴하고 있습니다.
그러나 이 구현은 hash tables의 성능을 저하시킵니다. 모든 객체가 하나의 bucket안에 같은값으로 저장될 것이거든요.

이러한 맥락에서 hash tables의 조회는 선형적으로 수행될 수 밖에 없어서 성능적 이점이 없습니다. 이는 추후 다시 설명합니다.

4. Improving the hashCodd() Implementation

같지 않은 객체에 대하여 다른 결과를 리턴할 수 있도록 Use클래스의 필드를 가지고 hashCode()구현을 바꿔보겠습니다.

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

이 해싱 알고리즘은 이전보다 개선되었습니다. 이메일과 이름의 hashcode와 id를 곱하는것만으로 hashcode를 계산하였기 때문입니다.
일반적으로 equal()함수 구현을 일관성 있게 유지하는한, 이렇게 구성한 hashCode()의 경우 굉장히 합리적인 구현이라고 생각할 수 있습니다.

5. Standard hashCode() Implementations

해시코드를 계산하는 해싱 알고리즘이 향상될수록, 해시 테이블의 성능은 좋아집니다.
계산된 해시에 더 많은 고유한 값을 추가하기 위해서 2개의 소수를 사용하는 "표준" 구현을 살펴보겠습니다.

    @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() 메서드의 역할을 이해하는 것은 중요하지만, 이를 매번 직접 구현할 필요는 없습니다. 대부분의 IDE가 이 메서드들을 자동으로 생성해 주며, Java 7부터는 Objects.hash() 유틸리티 메서드를 사용해 보다 간편하게 해시 값을 생성할 수 있습니다.

Objects.hash(name, email)

Intellij IDEA에서는 다음과 같이 자동 구현됩니다.

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

Esclipse에서는 다음과 같이 자동 구현됩니다.

@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;
}

위의 IDE를 통해서 구현이 가능하지만 Lombok을 통해서도 구현이 가능합니다.

implementation 'org.projectlombok:lombok:1.8.30'

의존성을 추가한 뒤, User 클래스에 어노테이션을 붙여줍니다.

@EqualsAndHashCode 
public class User {
    // fields and methods here
}

비슷하게 Apache Commons Lang 라이브러리에 있는 HashCodeBuilder클래스가 hashCode()함수를 구현하게끔 할 수 있습니다.

implementation 'org.apache.commons:commons-lang3:3.17.0'

의존성을 추가해준 뒤,

    @Override
    public int hashCode() {
        return new HashCodeBuilder(17, 37)
                .append(id)
                .append(name)
                .append(email)
                .toHashCode();
    }

이렇게 작성해주면됩니다.

hashCode()함수를 구현하기 위한 정형화된 방법은 없습니다. 이펙티브 자바라는 책에서 효율적인 해싱 알고리즘을 작성하기 위한 가이드라인을 제공하고 있으니 한 번 읽어보시길 바랍니다.

여기서 '31'이라는 값을 자주사용하고 있습니다. 이는 여러 효율성을 고려한 것입니다.

• 31은 소수라서 해시 충돌을 줄이는 데 유리
• 비트 연산을 활용하여 곱셈을 최적화할 수 있음 (31 * i == (i << 5) - i)
• 비트 연산(<<)은 CPU에서 더 빠르게 처리 가능

이러한 특성때문에 '31'이라는 숫자를 사용합니다.

6. Handling Hash Collisions

해시 테이블(Hash Table)의 동작 방식에서 중요한 개념 중 하나는 해시 충돌(Hash Collision) 입니다.
즉, 아무리 효율적인 해싱 알고리즘을 사용하더라도 서로 다른 두 객체가 같은 해시코드를 가질 가능성이 있다보니 이러한 경우 두 객체가 같은 해시 버킷을 가리키게 됩니다. 하지만 이 객체는 서로 다르기에 해시테이블에서 이를 관리할 방법이 필요합니다.

이를 개선하기 위해서 같은 해시코드를 가지는 객체들은 하나의 연결 리스트(Linked List)로 관리되도록 하였는데, 최악의 경우 하나의 버킷에 여러 객체가 담기다보면 해시테이블의 성능이 O(n)으로 떨어지게 됩니다.

이렇듯 해시충돌은 hashCode()를 얼마나 효율적으로 구현하는게 중요한지 알려주는 지표가 되기도 합니다.
Java8에서는 특정 버킷의 크기가 임계값을 넘어가면 연결 리스트를 트리구조로 변경하여 시간 복잡도가 O(n)이 되는것을 O(log n)로 개선하였습니다.

7. Creating a Trivial Application

이제 위에서 작성한 코드를 테스트해봅니다.

public class Application {

    public static void main(String[] args) {
        Map<User, User> users = new HashMap<>();
        User user1 = new User(1L, "John", "john@domain.com");
        User user2 = new User(2L, "Jennifer", "jennifer@domain.com");
        User user3 = new User(3L, "Mary", "mary@domain.com");

        users.put(user1, user1);
        users.put(user2, user2);
        users.put(user3, user3);
        if (users.containsKey(user1)) {
            System.out.print("User found in the collection");
        }
    }
}

실행이 될 main함수를 작성합니다.

public class User {

    // ...

    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());
        logger.info("hashCode() called - Computed hash: " + hash);
        return hash;
    }
}

hashCode() 구현을 작성합니다.

여기서 중요한건 객체가 해시맵에 저장되고 containKey() 함수로 검사될 때마다 hashCode()가 호출되고 계산된 해시 코드가 콘솔에 출력되는 것을 확인해야합니다.

hashCode() called - Computed hash: 1255477819
hashCode() called - Computed hash: -282948472
hashCode() called - Computed hash: -1540702691
hashCode() called - Computed hash: 1255477819
User found in the collection

8. 결론

효율적인 hashCode() 구현을 위해서는 소수(Prime Number)나 임의의 숫자(Arbitrary Number) 같은 몇 가지 수학적 개념과 논리 및 기본적인 연산을 조합해서 사용하는 경우가 많습니다.

하지만, 꼭 이런 기법들을 사용하지 않더라도 hashCode()를 효과적으로 구현할 수 있습니다.
중요한 것은 서로 다른 객체에 대해 서로 다른 해시코드를 생성하도록 하고,
equals() 메서드와 일관성을 유지하는 것입니다.

---

블로그 주인장 생각: hashCode에 대한 동작방식은 중요합니다. Java8이상부터 해시충돌에 대하여 어떻게 대처하고 있는지에 대한 내용도 같이 가져가면 좋을 것 같습니다.

예제 코드: https://github.com/kkminseok/baeldung-test/blob/main/Java-basic/src/test/java/basic/HashCodeTest.java