Collections Framework (5) HashSet, TreeSet

HashSet

Set 인터페이스를 구현한 대표 컬렉션으로 요소를 중복해서 저장할 수 없고, 저장 순서를 유지하지 않는다. 저장 순서를 유지하고자 한다면, LinkedHashSet를 사용하면 된다.

HashSet(int initalCapacity, float loadFactor)​

위 생성자는 초기용량과 load factor를 지정하는 생성자인데, load factor란 컬렉션 클래스에 저장공간이 가득 차기 전에 미리 용량을 확보하기 위한 역할을 한다. 기본 값은 0.75로, 저장 공간의 75%가 채워졌을 때 용량이 두 배로 늘어난다.

add 메서드는 새로운 요소를 추가하기 전에 이미 저장되어 있는 요소와 같은 것인지를 판별하기 위해 추가하려는 요소의 equals()와 hashCode()를 호출한다. 따라서, 사용자 정의 클래스를 사용할 때 중복 요소로 판단하게 하기 위해서는 이 2개의 메서드를 목적에 맞게 오버라이딩을 해야한다.

 

hashCode() 오버라이딩 시 충족해야 하는 조건

@Getter
@Setter
public class Member {
	
    private String name;
    private int age;
    
    public Member (String name, int age) {
    	this.name = name;
        this.age = age;
    }
}​

 

1. 실행 중인 어플리케이션 내의 동일한 객체에 대해서 여러 번 hashCode()를 호출하더라도 동일한 int값을 반환해야 한다. 단, 실행시마다 동일한 값을 반환할 필요는 없다.

Member member = new Member("hello", 20);

int hashCode1 = member.hashCode();
int hashCode2 = member.hashCode();

member.setAge(30);

int hashCode3 = member.hashCode();

hashCode1과 hashCode2는 member가 동일한 이름과 나이를 가지고 있는 상태에서 반환된 값이므로 항상 일치해야 한다. 하지만 이 두 값이 실행될 때마다 반드시 같은 값일 필요는 없다. (Object 클래스의 경우 객체의 주소로 해시코드를 만들기 때문에 실행할 때마다 값이 달라질 수 있다.) 반면 hashCode3은 member의 나이를 수정한 뒤에 호출된 값이므로 hashCode1, hashCode2와는 값이 달라도 된다.

2. equals()를 통해 true를 반환받은 두 객체는 각각 hashCode()를 통해 반환된 값이 반드시 같아야 한다.

Member m1 = new Member("hello", 20);
Member m2 = new Member("hello", 20);

boolean result = m1.equals(m2);

int hashCode1 = m1.hashCode();
int hashCode2 = m2.hashCode();

equals()를 통해 비교한 값인 result의 값이 true라면, m1과 m2의 hashCode() 값인 hashCode1과 hashCode2의 값이 같아야 한다.

3. equals()를 통해 비교한 값이 false인 두 객체는 hashCode() 호출에 대해 같은 int값을 반환하는 경우가 존재해도 되지만, 해싱을 사용하는 컬렉션의 성능을 향상시키기 위해서는 다른 값을 반환하도록 하는 것이 좋다.

해싱을 사용하는 컬렉션의 경우, 서로 다른 객체에 대해 같은 hash 값을 반환하도록 하면 중복이 많아져 검색 속도가 떨어지게 된다. 두 객체에 대한 equals()의 값이 true라면 두 객체의 해시코드는 반드시 같아야하지만, 두 객체의 해시코드가 같다고 해서 equals()의 값이 반드시 true여야 하는 것은 아니다. 

 

TreeSet

Binary Search Tree (이진 탐색 트리)의 자료구조 형태로 요소를 저장하는 컬렉션이다. Set 인터페이스를 구현한 클래스이기 때문에 데이터를 중복 저장할 수 없고, 저장 순서를 유지하지 않는다.

이진 탐색 트리의 형태를 갖추기 위해서는 데이터가 추가될 때 비교연산이 필요하다. 그렇기 때문에, TreeSet에 저장될 객체가 Comparable() 메서드를 구현하거나 TreeSet에 Comparator()를 제공해야 한다. 그렇지 않으면 예외가 발생한다. 

* 트리는 데이터를 저장하기 위해 저장 위치를 찾아야 하고, 삭제 시에는 트리를 재구성해야 한다. 따라서 LinkedList에 비해 데이터의 추가와 삭제가 느리다. 반면 검색과 정렬에 있어서는 더 뛰어나다. 따라서, TreeSet은 데이터를 저장할 때 정렬이 이루어진다.

 

참고

Java의 정석 (남궁 성 지음)