1. 개요

해싱은 컴퓨터 과학의 기본 개념입니다.

Java에서 효율적인 해싱 알고리즘은 HashMap (이 심층 기사 확인 ) 및 HashSet같은 가장 인기 있는 컬렉션 뒤에 있습니다 .

이 사용방법(예제)에서는 hashCode()가 작동하는 방식, 컬렉션에서 작동하는 방식 및 올바르게 구현하는 방법에 중점을 둘 것입니다.

2. 데이터 구조에서 hashCode() 사용하기

컬렉션에 대한 가장 간단한 작업은 특정 상황에서 비효율적일 수 있습니다.

예를 들어, 이것은 선형 검색을 트리거하며, 이는 거대한 List에 대해 매우 비효율적입니다.

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

Java는 특히 이 문제를 처리하기 위한 여러 데이터 구조를 제공합니다. 예를 들어, 여러 Map 인터페이스 구현은 해시 테이블 입니다.

해시 테이블을 사용할 때 이러한 컬렉션은 hashCode() 메서드를 사용하여 주어진 키에 대한 해시 값을 계산합니다 . 그런 다음 액세스 작업이 훨씬 더 효율적으로 되도록 이 값을 내부적으로 사용하여 데이터를 저장합니다.

3. hashCode() 작동 방식 이해

간단히 말해, hashCode() 는 해싱 알고리즘에 의해 생성된 정수 값을 반환합니다.

( equals() 에 따라) 동일한 객체 는 동일한 해시 코드를 반환해야 합니다. 다른 객체는 다른 해시 코드를 반환할 필요가 없습니다.

hashCode() 의 일반 계약은 다음과 같이 명시합니다.

  • Java 애플리케이션을 실행하는 동안 동일한 객체에 대해 두 번 이상 호출될 때마다 hashCode() 는 객체에 대한 같음 비교에 사용된 정보가 수정되지 않는 한 일관되게 동일한 값을 반환해야 합니다. 이 값은 한 애플리케이션 실행에서 동일한 애플리케이션의 다른 실행까지 일관성을 유지할 필요가 없습니다.
  • equals(Object) 메서드 에 따라 두 객체가 같으면 두 객체 각각에 대해 hashCode() 메서드를 호출 하면 동일한 값이 생성되어야 합니다.
  • equals(java.lang.Object) 메소드 에 따라 두 객체가 같지 않으면 두 객체 각각에 대해 hashCode 메소드를 호출 할 때 고유한 정수 결과를 생성할 필요가 없습니다. 그러나 개발자는 같지 않은 개체에 대해 고유한 정수 결과를 생성하면 해시 테이블의 성능이 향상된다는 점을 알아야 합니다.

“합리적으로 실용적인 한, Object 클래스에 의해 정의된 hashCode() 메서드 는 고유한 개체에 대해 고유한 정수를 반환합니다. (이것은 일반적으로 개체의 내부 주소를 정수로 변환하여 구현되지만 JavaTM 프로그래밍 언어에서는 이 구현 기술이 필요하지 않습니다.)

4. 순진한 hashCode() 구현

위의 계약을 완전히 준수 하는 순진한 hashCode() 구현은 실제로 매우 간단합니다.

이를 보여주기 위해 메서드의 기본 구현을 재정의 하는 샘플 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 o) {
        if (this == o) 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));
    }
    
    // getters and setters here
}

사용자 클래스에 사용자 정의 구현을 제공 등호 ()해시 코드 () 완전히 각각의 계약 준수합니다. 더욱이 hashCode()가 고정 값을 반환하는 것이 불법적인 것은 아닙니다 .

그러나 이 구현은 모든 객체가 동일한 단일 버킷에 저장되기 때문에 해시 테이블의 기능을 기본적으로 0으로 저하시킵니다.

이러한 맥락에서 해시 테이블 조회는 선형으로 수행되며 실질적인 이점을 제공하지 않습니다. 이에 대해서는 섹션 7에서 더 자세히 설명합니다.

5. hashCode() 구현 개선

같지 않은 객체에 대해 다른 결과를 생성할 수 있도록 User 클래스 의 모든 필드를 포함 하여 현재 hashCode() 구현을 개선해 보겠습니다 .

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

이 기본 해싱 알고리즘은 확실히 이전 알고리즘보다 훨씬 뛰어납니다. 이름이메일 필드 의 해시 코드 id를 곱하여 객체의 해시 코드를 계산하기 때문 입니다.

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

6. 표준 hashCode() 구현

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

계산된 해시 코드에 더 많은 고유성을 추가하기 위해 두 개의 소수를 사용하는 "표준" 구현을 살펴보겠습니다.

@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가 사용자 정의 hashCode()equals() 구현을 생성할 수 있기 때문 입니다. 그리고 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;
}

그리고 Eclipse 는 다음을 생성합니다.

@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 기반 hashCode() 구현 외에도 Lombok을 사용하여 효율적인 구현을 자동으로 생성하는 것도 가능합니다 .

이 경우 pom.xml에 lombok-maven 의존성을 추가해야 합니다 .

<dependency>
    <groupId>org.projectlombok</groupId>
    <artifactId>lombok-maven</artifactId>
    <version>1.16.18.0</version>
    <type>pom</type>
</dependency>

이제 @EqualsAndHashCode로 User 클래스 에 어노테이션을 추가하는 것으로 충분합니다 .

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

마찬가지로 Apache Commons Lang의 HashCodeBuilder 클래스hashCode() 구현 을 생성하도록 하려면 pom 파일에 commons-lang Maven 의존성을 포함합니다.

<dependency>
    <groupId>commons-lang</groupId>
    <artifactId>commons-lang</artifactId>
    <version>2.6</version>
</dependency>

그리고 hashCode() 는 다음과 같이 구현할 수 있습니다.

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

일반적으로 hashCode() 구현과 관련하여 보편적인 방법은 없습니다 . Joshua Bloch의 Effective Java를 읽는 것이 좋습니다 . 효율적인 해싱 알고리즘을 구현 하기 위한 철저한 지침 List을 제공합니다 .

여기에서 이러한 모든 구현은 어떤 형태로든 31번을 활용한다는 점에 유의하십시오. 31은 좋은 속성을 가지고 있기 때문입니다. 그 곱셈은 표준 곱셈보다 빠른 비트 시프트로 대체될 수 있습니다.

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

7. 해시 충돌 처리

해시 테이블의 고유한 동작은 이러한 데이터 구조의 관련 측면을 나타냅니다. 효율적인 해시 알고리즘을 사용하더라도 둘 이상의 객체가 같지 않더라도 동일한 해시 코드를 가질 수 있습니다. 따라서 해시 코드는 해시 테이블 키가 다르더라도 동일한 버킷을 가리킵니다.

이러한 상황을 일반적으로 해시 충돌이라고 하며 이를 처리하는 다양한 방법이 있으며 각각 장단점이 있습니다. Java의 HashMap충돌 처리를 위해 별도의 연결 방법사용 합니다 .

“두 개 이상의 객체가 동일한 버킷을 가리키면 단순히 연결 List에 저장됩니다. 이 경우 해시 테이블은 연결 List의 배열이며, 동일한 해시를 가진 각 객체는 배열의 버킷 인덱스에서 연결 List에 추가됩니다.

최악의 경우 여러 버킷에 연결된 List이 있고 List에서 개체 검색이 선형으로 수행됩니다.”

해시 충돌 방법론은 hashCode()를 효율적 으로 구현하는 것이 중요한 이유를 간단히 보여줍니다 .

Java 8은 HashMap 구현에 흥미로운 개선 사항을 가져왔습니다 . 버킷 크기가 특정 임계값을 초과하면 트리 맵이 연결 List을 대체합니다. 이를 통해 비관적인 O(n) 대신 O( logn ) 조회를 달성할 수 있습니다 .

8. 간단한 애플리케이션 만들기

이제 표준 hashCode() 구현 의 기능을 테스트합니다 .

일부 User 개체를 HashMap에 추가 하고 메서드가 호출될 때마다 콘솔에 메시지를 기록하기 위해 SLF4J사용 하는 간단한 Java 응용 프로그램을 만들어 보겠습니다 .

다음은 샘플 애플리케이션의 진입점입니다.

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");
        }
    }
}

그리고 이것은 hashCode() 구현입니다:

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

여기서 객체가 해시 맵에 저장되고 containsKey() 메서드로 확인할 때마다 hashCode() 가 호출되고 계산된 해시 코드가 콘솔에 출력 된다는 점에 유의하는 것이 중요합니다 .

[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -282948472
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -1540702691
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819
User found in the collection

9. 결론

효율적인 hashCode() 구현 을 생성 하려면 종종 몇 가지 수학적 개념(예: 소수 및 랜덤의 숫자), 논리적 및 기본 수학적 연산의 혼합이 필요합니다.

그럼에도 불구 하고 이러한 기술을 전혀 사용하지 않고도 hashCode()를 효과적으로 구현할 수 있습니다 . 해싱 알고리즘이 같지 않은 객체에 대해 다른 해시 코드를 생성하고 equals() 구현과 일치하는지 확인하기만 하면 됩니다 .

항상 그렇듯이 이 기사에 표시된 모든 코드 예제 는 GitHub에서 사용할 수 있습니다 .

Junit footer banner