자바의정석 - 11장 컬렉션 프레임워크 3. Set

: Set 인터페이스의 구현체는 크게 HashSet과 TreeSet으로 나눠서 생각하면 된다.

HashSet

: Set을 구현하는 가장 대표적인 컬렉션. 일반적인 Set

• 중복된 요소를 추가하고자 한다면 추가되지 않고 false가 반환된다.

• 내부적으로 HashMap을 이용해 만들어져있고, hashing을 통해 구현되어있다.

  • HashMap을 이용한 방법: K-V에서 V를 PRESENT라는 상수(dummy value)로 생성 시점에 초기화해놓고, add 시점에 key값에 해당하는 PRESENT가 존재하는지 아닌지를 따져 중복을 검증한다.

• load factor: default는 0.75. 75%만큼 채워졌을 때 용량이 두배로 늘어난다.

  HashSet(int initialCapaticy, float loadFactor)

• 저장 순서를 유지하고자 한다면 LinkedHashSet 이용

활용 예: Lotto

class HashSetLotto {
  public static void main(String[] args) {
    Set<Integer> set = new HashSet<>();

    while(set.size() < 6) {
      int randomNumber = (int) (Math.random() * 45) + 1;
      set.add(new Integer(randomNumber));
    }

    List<Integer> list = new LinkedList<>(set);
    Collections.sort(list);
    System.out.println(list);
  }
}

• int vs Integer: int는 원시타입이라 산술 연산이 가능하고 non-null이다. Integer는 Wrapper객체라 null을 처리할 수 있어 SQL에 용이하고 산술연산을 하려면 언박싱해야한다.

Hash 커스터마이즈

• HashSet 내부적으로 equals(), hashCode() 호출한다. 따라서, 중복 기준을 다르게 하려한다면 equals(), hashCode()를 목적에 맞게 오버라이드 해야한다. JDK1.8부터는 hash()

hash 조건

1. 동일한 객체에는 여러번 hash()를 호출해도 동일한 int값을 반환해야한다.
2. equals()를 통해 true가 나왔다면 hash()를 호출했을 때 결과가 같아야한다.
3. equals() 를 통해 false가 나왔어도 hash()에서 같은 값이 나올 수는 있다(충돌). 그러나, 성능을 위해서 되도록이면 다르게 나오도록 해싱을 잘해야한다.

TreeSet

: Set중에서 순차적으로 값을 저장하기 위해 쓰인다. 범위검색이나 정렬이 필요한 경우에 이것을 사용한다.

• 이진탐색트리(BST) 중 Self-balancing 특성을 갖는 레드블랙트리로 데이터를 저장하는 컬렉션이다.
• 일반적인 검색의 경우 HashMap이 TreeMap보다 뛰어나기 때문에 보통은 HashSet을 사용한다.
• TreeSet에 저장하는 Object가 Comparable을 구현하던가 혹은 Comparator를 제공해서 두 객체를 비교할 방법을 알려줘야 한다.

활용 예: Lotto

class TreeSetLotto {
  public static void main(String[] args) {
    Set<Integer> set = new TreeSet<>();

    while(set.size() < 6) {
      int randomNumber = (int) (Math.random() * 45) + 1;
      set.add(new Integer(randomNumber));
    }

    System.out.println(list);
  }
}

• TreeSet이 Node 추가, 삭제 시점에 알아서 정렬해주기 때문에 List에 넣어 정렬하는 과정이 필요없다.

Reference)

자바의 정석 3판