자바의 hashCode () 가이드

1. 개요

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

등 등 - 자바에서 효율적인 해싱 알고리즘은 우리가 사용할 수있는 가장 인기있는 컬렉션의 일부 뒤에 서 의 HashMap (에 대해 자세히 살펴 보도록 의 HashMap ,이 문서를 확인해 주시기 바랍니다)와 HashSet의.

이 기사에서는 hashCode () 가 어떻게 작동하는지, 어떻게 컬렉션으로 재생되는지, 그리고 올바르게 구현하는 방법에 초점을 맞출 것입니다.

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

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

예를 들어, 이것은 거대한 크기의 목록에 대해 매우 비효율적 인 선형 검색을 트리거합니다.

List 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을 사용하여 효율적인 구현을 자동으로 생성 할 수도 있습니다. 이 경우 lombok-maven 종속성을 pom.xml에 추가해야합니다 .

 org.projectlombok lombok-maven 1.16.18.0 pom 

이제 @EqualsAndHashCode로 User 클래스 에 주석을 추가하는 것으로 충분합니다 .

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

마찬가지로 Apache Commons Lang의 HashCodeBuilder 클래스가 우리를 위해 hashCode () 구현 을 생성하도록 하려면 commons-lang Maven 종속성이 pom 파일에 포함되어야합니다.

 commons-lang commons-lang 2.6 

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

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

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

여기서 주목할 수있는 것은 모든 구현이 어떤 형태로든 31 번을 사용한다는 것입니다. 이것은 31이 좋은 속성을 가지고 있기 때문입니다. 그 곱셈은 표준 곱셈보다 빠른 비트 시프트로 대체 될 수 있습니다.

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

7. 해시 충돌 처리

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

이러한 상황은 일반적으로 해시 충돌로 알려져 있으며,이를 처리하기위한 다양한 방법론이 존재하며 각각의 장단점이 있습니다. Java의 HashMap 은 충돌을 처리하기 위해 별도의 연결 방법을 사용합니다.

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

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

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

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

8. 간단한 응용 프로그램 만들기

표준 hashCode () 구현 의 기능을 테스트하기 위해 일부 User 객체를 HashMap에 추가 하고 메서드가 호출 될 때마다 콘솔에 메시지를 기록하기 위해 SLF4J를 사용 하는 간단한 Java 애플리케이션을 만들어 보겠습니다 .

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

public class Application { public static void main(String[] args) { Map users = new HashMap(); User user1 = new User(1L, "John", "[email protected]"); User user2 = new User(2L, "Jennifer", "[email protected]"); User user3 = new User(3L, "Mary", "[email protected]"); 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; } }

The only detail worth stressing here is that each time an object is stored in the hash map and checked with the containsKey() method, hashCode() is invoked and the computed hash code is printed out to the console:

[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. Conclusion

It's clear that producing efficient hashCode() implementations often requires a mixture of a few mathematical concepts, (i.e. prime and arbitrary numbers), logical and basic mathematical operations.

Regardless, it's entirely possible to implement hashCode() effectively without resorting to these techniques at all, as long as we make sure the hashing algorithm produces different hash codes for unequal objects and is consistent with the implementation of equals().

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