HashSet 동작원리

서버란·2024년 9월 12일
자바

자바 궁금증

목록 보기
18/35
public class HashCodeMain { 
public static void main(String[] args) {

System.out.println("A1".hashCode()); 
System.out.println("A2".hashCode()); 
System.out.println("A3".hashCode()); 
System.out.println("A4".hashCode()); 
System.out.println("A5".hashCode()); 

User user1 = new User(1, "A", 30); 
User user2 = new User(1, "A", 30); 
User user3 = new User(1, "A", 30); 
User user4 = new User(1, "A", 30); 
User user5 = new User(1, "A", 30); 

System.out.println("user1:" + user1.hashCode()); 
System.out.println("user2:" + user2.hashCode()); 
System.out.println("user3:" + user3.hashCode()); 
System.out.println("user4:" + user4.hashCode()); 
System.out.println("user5:" + user5.hashCode()); 

Set<User> set = new HashSet<>(); 
System.out.println("set-user1:" + set.add(user1)); 
System.out.println("set-user2:" + set.add(user2)); 
System.out.println("set-user3:" + set.add(user3)); 
System.out.println("set-user4:" + set.add(user4)); 
System.out.println("set-user5:" + set.add(user5)); 
} 

static class User { 

private final int userNo; 
private final String userName; 
private final int userAge; 

public int getUserAge() { return userAge; } 

public User(int userNo, String userName, int userAge) {
this.userNo = userNo; 
this.userName = userName; 
this.userAge = userAge; 
}

	@Override 
    public String toString() { 
	return "User{" + "userNo=" + userNo + ", userName='" + userName + '\'' + ", userAge=" + userAge + '}'; 
	} 

@Override 
	public boolean equals(Object o) { 
	if (this == o) { return true; } 
	if (o == null || getClass() != o.getClass()) { return false; } 
    
	User user = (User) o; 
	if (userNo != user.userNo) { return false; } 
	if (userAge != user.userAge) { return false; } if(userName != null){ return userName.equals(user.userName); }
	else{ return user.userName == null; 
	} 
} 

@Override public int hashCode() { 
int result = userNo; 
result = 31 * result + (userName != null ? userName.hashCode() : 0); 
result = 31 * result + userAge; return result; } } 
}

  • 해시맵(HashMap)과 해시셋(HashSet)을 제대로 사용하기 위해서는 hashCode()와 equals() 메서드를 반드시 오버라이드해야 합니다.

  • 그 이유는 해시맵과 해시셋의 내부 동작 원리가 해시 테이블(Hash Table)을 기반으로 하기 때문입니다.

  • 코드 설명

  1. User 클래스의 hashCode()와 equals() 오버라이드
  • hashCode(): 객체의 해시 코드를 생성합니다. 해시 코드는 객체를 효율적으로 비교하기 위해 사용됩니다. 같은 값을 가진 객체들은 같은 해시 코드를 가져야 합니다.
  • equals(): 객체 간의 동등성을 비교합니다. 해시셋에서는 두 객체가 같다고 판단되면 중복 삽입을 방지하는데, 이때 equals() 메서드를 사용합니다.
  1. HashSet 동작 원리

  • HashSet은 내부적으로 HashMap을 사용하여 데이터를 관리합니다. 즉, HashSet에 값을 저장할 때 그 값이 HashMap의 키(key)로 저장되는 것입니다. 이때 HashSet의 동작 방식은 다음과 같습니다.

  • user1, user2, user3, user4, user5가 모두 동일한 값을 가지고 있지만, hashCode()와 equals()를 적절히 오버라이드하지 않으면 해시 값이 달라질 수 있습니다. 하지만, 당신의 코드에서는 이 두 메서드를 오버라이드했기 때문에 같은 값을 가진 객체들은 같은 해시 값을 갖게 됩니다.

  • HashSet의 add() 메서드는 값을 추가할 때 내부적으로 두 가지 과정을 거칩니다.

  • 먼저 hashCode()를 호출하여 객체의 해시 값을 계산합니다.
    그다음 equals()를 호출하여 해당 해시 값의 슬롯에 이미 동일한 객체가 있는지 확인합니다.

  1. 해시 충돌과 HashSet의 처리 과정

  • 처음 user1이 HashSet에 추가될 때, hashCode()를 계산하여 해당 해시 값을 기반으로 적절한 슬롯(버킷)을 찾습니다. 이 슬롯에 아직 값이 없으므로 null을 반환하고, user1이 해당 슬롯에 저장됩니다. 이때 add() 메서드는 true를 반환합니다.

  • user2가 추가될 때도 동일한 hashCode()를 가지므로 같은 슬롯에 할당됩니다. 하지만 equals()로 비교한 결과 user1과 동일한 객체로 간주되므로 중복된 값으로 판단하여 추가되지 않습니다. 따라서 add() 메서드는 false를 반환합니다.

  • 이 과정이 user5까지 반복됩니다. 결국 user1만 HashSet에 추가되고, 나머지 user2, user3, user4, user5는 equals() 메서드에 의해 중복된 객체로 판단되어 추가되지 않습니다.

해시맵 동작 원리 더 자세하게 설명

  • HashSet이 내부적으로 HashMap을 사용하는데, HashMap의 동작 원리에서 중요한 부분은 해시 충돌입니다.

  • 해시 테이블에서 여러 키가 동일한 해시 값을 가질 경우 이를 해시 충돌이라고 합니다. 이를 해결하기 위해 자바의 HashMap은 체이닝(Chaining) 기법을 사용합니다.

  • 새로운 키-값 쌍이 들어오면, 그 키의 해시 값을 계산하고, 그 해시 값에 해당하는 인덱스(슬롯)를 찾습니다.

  • 만약 그 슬롯이 비어 있으면(즉, null이면) 해당 값이 저장되고, 반환 값은 null이기 때문에 true가 반환됩니다.

  • 반면 그 슬롯에 이미 값이 있으면(즉, null이 아니면), 체이닝을 통해 연결 리스트로 그 자리에 새 값을 저장합니다.

  • 하지만 이때 equals()로 기존 값과 비교하여 동일한 값이 있으면 덮어쓰지 않고 추가를 방지합니다.

이 과정을 통해 HashSet은 중복 값을 방지할 수 있습니다.

  • 결론
    HashSet은 내부적으로 HashMap을 사용하여 데이터를 저장합니다.
    객체가 추가될 때 hashCode()로 해시 값을 계산한 후, 그 해시 값을 기반으로 적절한 슬롯에 저장합니다.
    동일한 해시 값을 가지는 객체가 이미 존재하면 equals()로 객체의 동등성을 확인하여 중복 삽입을 방지합니다.
    이 과정에서 true, false가 반환되며, 이는 삽입 성공 여부를 나타냅니다.

Q1: equals() 메서드를 오버라이드하지 않으면 어떤 일이 발생하나요? hashCode()만 오버라이드할 때의 문제점은 무엇인가요?

Q2: HashSet의 성능을 높이기 위해 hashCode() 메서드를 어떻게 최적화할 수 있을까요?

Q3: 자바의 다른 컬렉션 클래스들(예: TreeSet, LinkedHashSet)에서의 중복 처리 방식은 어떻게 다른가요?

Q1: equals() 메서드를 오버라이드하지 않으면 어떤 일이 발생하나요? hashCode()만 오버라이드할 때의 문제점은 무엇인가요?

  • equals() 메서드를 오버라이드하지 않으면, 기본적으로 객체의 참조 주소(메모리 주소)를 기준으로 객체를 비교하게 됩니다.

  • 즉, 두 객체가 동일한 값을 가지고 있어도 서로 다른 객체로 간주됩니다. 예를 들어, User user1 = new User(1, "A", 30);와 같은 객체를 생성하고, 동일한 값을 가지는 또 다른 객체 user2를 생성하더라도, equals()가 오버라이드되지 않은 경우 이 두 객체는 다르다고 판단됩니다.

  • hashCode()만 오버라이드할 경우, 같은 해시 값을 가질 수는 있지만, equals()가 다르게 동작하면 해시셋이나 해시맵에서 중복된 값이 들어가는 것을 막지 못할 수 있습니다. 이는 데이터의 일관성을 깨트릴 수 있으며, 예를 들어 해시맵에서 같은 키가 두 번 삽입되거나, 해시셋에서 중복된 객체가 들어가는 상황이 발생할 수 있습니다.

  • 결론적으로, hashCode()와 equals()는 항상 같이 오버라이드해야 두 객체가 논리적으로 동일한지 올바르게 비교할 수 있습니다.

Q2: HashSet의 성능을 높이기 위해 hashCode() 메서드를 어떻게 최적화할 수 있을까요?
hashCode()를 최적화하는 방법은 충돌을 최소화하고 균등한 해시 분포를 제공하는 것입니다. 몇 가지 방법을 소개하겠습니다:

  • 충돌을 줄이는 해시 알고리즘: hashCode()에서 사용하는 알고리즘이 중요합니다. 자바의 기본 해시코드 구현 방식인 31 * result는 충돌을 줄이는 데 적합합니다. 그러나 클래스 필드가 많을 경우 각 필드의 고유성을 반영하는 적절한 가중치를 주는 방식이 좋습니다.
@Override
public int hashCode() {
    int result = userNo;
    result = 31 * result + (userName != null ? userName.hashCode() : 0);
    result = 31 * result + userAge;
    return result;
}

  • 중복된 해시 값을 피하기 위한 필드 선택: hashCode() 계산 시 객체의 모든 필드를 사용하기보다는, 중복될 가능성이 적은 필드를 선택하는 것이 좋습니다. 예를 들어, 고유 ID 또는 객체의 유일성을 보장할 수 있는 필드를 사용하면 충돌 가능성이 줄어듭니다.

  • 충돌을 줄이기 위한 전략: hashCode() 계산 시 여러 필드를 조합할 때 고유한 값을 산출하도록 하며, 같은 값으로 인해 해시 충돌이 빈번하게 발생하지 않도록 적절한 필드를 선택하고, 해시 코드의 범위를 충분히 분산시켜야 합니다.

  • 이를 통해 해시맵 또는 해시셋이 데이터를 보다 효율적으로 관리할 수 있고, 성능이 향상됩니다.

Q3: 자바의 다른 컬렉션 클래스들(예: TreeSet, LinkedHashSet)에서의 중복 처리 방식은 어떻게 다른가요?
자바의 각 컬렉션 클래스는 고유한 중복 처리 방식을 가집니다. TreeSet, LinkedHashSet은 중복을 처리하는 방식에서 차이가 있습니다.

TreeSet:

  • TreeSet은 정렬된 순서로 데이터를 저장하며, 내부적으로 이진 트리 구조를 사용합니다.
    중복을 방지하기 위해 객체 간 비교를 할 때 compareTo() 메서드 또는 Comparator 인터페이스를 사용합니다. 따라서 두 객체가 compareTo()에서 0을 반환하면 같은 객체로 간주되어 중복 삽입이 방지됩니다.

  • hashCode()와 equals()는 필수적으로 오버라이드하지 않아도 되지만, Comparable 또는 Comparator를 구현해 객체 간 비교가 가능해야 합니다.
    LinkedHashSet:

  • LinkedHashSet은 삽입 순서를 유지하는 해시셋입니다.

  • 내부적으로 HashSet과 유사하게 동작하므로, hashCode()와 equals() 메서드를 오버라이드하여 중복 삽입을 방지합니다.

  • 하지만 일반 HashSet과 달리 데이터가 추가된 순서를 유지합니다. 따라서 중복 방지 방식은 HashSet과 동일하지만, 데이터가 저장된 순서를 기억하고 이를 유지하는 것이 차이점입니다.
    정리하면:

  • TreeSet은 정렬된 순서로 데이터를 저장하고, 중복 확인을 compareTo()로 처리합니다.

  • LinkedHashSet은 삽입된 순서를 유지하며, HashSet과 동일한 방식으로 hashCode()와 equals()로 중복을 처리합니다.

Q1: hashCode()에서 사용하는 31의 의미와 장점은 무엇인가요? 다른 숫자로 바꿨을 때 어떤 결과가 나올 수 있나요?

Q2: HashMap이나 HashSet에서 해시 충돌이 발생했을 때 자바는 어떤 방법으로 이를 해결하나요?

Q3: TreeSet에서 Comparator를 커스터마이징하면 어떤 상황에서 유용하게 사용할 수 있을까요?

Q1: equals() 메서드를 오버라이드하지 않으면 어떤 일이 발생하나요? hashCode()만 오버라이드할 때의 문제점은 무엇인가요?

  • equals()를 오버라이드하지 않으면, 객체의 참조 주소를 기준으로 비교하게 됩니다. 즉, 값이 같아도 다른 객체로 간주됩니다. hashCode()만 오버라이드할 경우, 해시 값은 같아도 equals()가 제대로 동작하지 않기 때문에 중복 처리가 올바르게 되지 않습니다. 결국, 중복된 객체가 HashSet이나 HashMap에 들어갈 수 있습니다.

Q2: HashSet의 성능을 높이기 위해 hashCode() 메서드를 어떻게 최적화할 수 있을까요?

  • 적절한 필드 선택: 고유성을 보장하는 필드(예: ID)를 사용해 해시 값을 계산합니다.
    충돌을 줄이는 해시 알고리즘: 31 * result와 같은 방식으로 충돌을 최소화하는 알고리즘을 사용합니다.

  • 해시 분포 최적화: 해시 값이 균등하게 분포되도록 해시 계산을 조정해 성능을 향상시킵니다.

Q3: 자바의 다른 컬렉션 클래스들(예: TreeSet, LinkedHashSet)에서의 중복 처리 방식은 어떻게 다른가요?

  • TreeSet: 객체 간 비교를 compareTo()로 수행하여 중복을 처리하고, 정렬된 순서로 데이터를 유지합니다.
  • LinkedHashSet: 삽입 순서를 유지하며, HashSet처럼 hashCode()와 equals()로 중복을 처리합니다.
profile
서버란
백엔드에서 서버엔지니어가 된 사람
이전 포스트

Maven 이란?

다음 포스트

HashMap의 검색 속도는 왜 Array보다 빠른가?

0개의 댓글