스터디플래너/공부하기

[자바의 정석] Ch.11 컬렉션 프레임웍(Collections Framework)

술 2022. 5. 24. 08:24

1.8 HashSet

Set인터페이스를 구현한 가장 대표적인 컬렉션이며, 중복된 요소를 저장하지 않는다. add()나 addAll()메소드를 사용하여 새로운 요소를 추가하는데 boolean타입으로 반환하여 true이면 추가, false이면 추가에 실패한 것이다.List처럼 저장순서를 유지하면서 저장하고 싶다면 LinkedHashSet을 사용해야 한다.

 

요새 책의 내용을 그냥 받아적기만 하는 것 같아 다른 걸 좀 더 해야겠다 생각했고 많은 사람들이 공식 문서를 봐야 한다고 해서 찾아봤다. java.util.HashSet은 java.lang.Object > java.util.AbstractCollection > java.util.AbstractSet > java.util.HashSet으로 되어있다. Collection 인터페이스를 구현한 AbstractCollection 클래스를 상속받는데 이름을 보니 추상클래스 같다. 물론 아니겠지만. 추상 컬렉션 클래스를 상속받은 추상 세트 클래스를 상속받은 HashSet클래스 인 듯 하다. Serializable, Cloneable, Iterable, Collection, Set 인터페이스 구현되었다는 걸 봐서는 앞에서 배운 Iterator를 사용할 수 있는 듯 하다.

 

Set의 반복 순서를 보장하지 않고 순서가 보장되지도 않는다. null요소를 허락한다. 이 클래스는 버킷에 분산된 요소를 hash function을 띄어 add() remove(), contains(), size()와 같이 기본적으로 동작하는 메소드를 호출하면 일관된 시간으로 수행한다. Set 인터페이스를 반복하는 것은 HashSet 인스턴스 사이즈, 즉 Set 요소 개수의 합에 인스턴스의 크기까지 더한 값에 비례하여 시간이 필요하다. 따라서 iteration이 중요하다면 최초 capacity를 너무 크지 않게 잡는 것이 중요하다. Set는 synchronized를 제공하지 않는다. 멀티 스레드가 HashSet에 접근하거나 최소 하나의 스레드가 set를 변경한다면 외부적으로 synchronized된 것이다. 이는 자연스럽게 set를 캡슐화한 어떤 객체가 synchronizing을 해낸 것이지 이런 객체가 없었다면 Collections의 synchronizedSet메소드를 사용해서 wrapp되어야 한다. 이 것이 synchronized을 막는 set에 synchronized할 수 있는 방법이다. HashSet은 Java Collections Framework의 멤버이다. 아래는 조상 클래스나 구현한 인터페이스로부터 상속받은 메소드들이다.

HashSet(Collection c) 주어진 컬렉션을 포함하는 HashSet객체를 생성한다.
HashSet(int initialCapacity) 주어진 값을 초기용량으로 하는 HashSet객체를 생성한다.
HashSet(int initialCapacity, float loadFactor) 새로운 객체를 저장한다.
boolean add(Object o) 새로운 객체를 저장한다.
boolean addAll(Collection c) 주어진 컬렉션에 저장된 모든 객체들을 추가한다(합집합).
void clear() 저장된 모든 객체를 삭제한다.
Object clone() HashSet을 복제해서 반환한다(얕은 복사).
boolean contains(Object o) 지정된 객체를 포함하고 있는지 알려준다.
boolean containsAll(Collection c) 주어진 컬렉션에 저장된 모든 객체들을 포함하고 있는지 알려준다.
boolean isEmpty() HashSet이 비어있는지 알려준다.
boolean iterator() Iterator를 반환한다.
boolean remove(Object o) 지정된 객체를 HashSet에서 삭제한다(성공하면 true, 실패하면 false)
boolean removeAll(Collection c) 주어진 컬렉션에 저장된 모든 객체와 동일한 것들을 HashSet에서 모두 삭제한다(차집합)
boolean retainAll(Collection c) 주어진 컬렉션에 저장된 객체와 동일한 것만 남기고 삭제한다(교집합).
int size() 저장된 객체의 개수를 반환한다.
Object[] toArray() 저장된 객체들을 객체배열의 형태로 반환한다. 
// 예제 만들기 1
import java.util.HashSet;
import java.util.Set;

public class HashSetPractice {
    public static void main(String[] args) {
        // Math.random()을 이용하여 Set에 추가할 배열의 인덱스를 정하려고 하는데
        // 배열은 0부터 시작하므로 1부터가 아니라 0부터 5까지 배열을 생성
        Object[] arr = {0, 1, 2, 3, 4, 5};
        Set set = new HashSet();

        for(int i=0; i<10; i++){
            int random = (int)(Math.random()*5 + 1);
            System.out.printf("%d회차 인덱스 %d\n", i, random);
            set.add(arr[random]);
        }

        System.out.println(set);
    }
}
// 예제만들기 2
import java.util.HashSet;
import java.util.Set;

public class HashSetPractice {
    public static void main(String[] args) {
        Object[] arr = {0, 1, 2, 3, 4, 5};
        Set set = new HashSet();

        for(int i=0; i<10; i++){
            int random = (int)(Math.random()*5 + 1);

 			//contains()를 이용하여 배열에 이미 값이 존재한다면 변형된 수를 추가해준다.
			if(set.contains(arr[random])){
                System.out.printf("%d회차 인덱스 %d가 이미 set에 있어 ", i, random);
                random *= (Math.random() * 10 + 1);
                set.add(random);
                System.out.printf("숫자를 조금 바꿔 %d를 set에 넣었지.\n", random);
            }else{
                set.add(arr[random]);
                System.out.printf("%d회차 인덱스 %d\n", i, random);
            }
        }

        System.out.println(set);
    }
}

매일 교재의 예제만 따라 입력하려니 양심에 찔려서 직접 코드를 작성해봤다. for문을 이용하여 1부터 5 중에서 하나의 숫자를 set에 추가하고 작업을 10번 했다. 4를 제외한 1, 2, 3, 5가 두 번이상 추가되었지만 실제 set에 추가된 것은 한 번이다. 사실 random을 이용한 숫자가 무조건 1, 2, 3, 4, 5 중 한번씩 나온다는 보장이 없기 때문에 나도 실행했을 때 다섯 개를 꽉 채운 적은 열 번에 한 번 뿐이다. 두번째 코드는 그러면 다른 메소드를 이용하여 배열에 추가하려는 값이 있는지 확인하고, 그 값이 있다면 또다시 Math.random()을 호출하여 해당 숫자에 변형을 주고, 그 숫자를 추가해보았다. 하고나니 왜 했는지 알 수 없다.

 

책의 예제 중 String "abc"와 Person이라는 객체를 두 번씩 추가했다. Set은 중복을 허용하지 않기 때문에 두 객체가 모두 한 번씩만 추가될 것이라 예상했지만 실제로는 "abc"만 한 번 추가되었고 Person은 속성인 name 과 age가 같음에도 불구하고 두 번 추가되었다. 우리가 보는 이름과 주소가 같을지라도 두 객체의 주소값이 다르기때문에 다른 객체로 인식한 것이다. 따라서 equals()와 hashCode()를 오버라이딩 하면 된다. 나는 equals()만 하면 된다고 생각했는데 hashCode()까지 오버라이딩 해야하는 이유는 add()가 기존에 저장된 요소와 동일한 지 확인할 때 두 메소드를 호출하기 때문이다.

 

String의 hashCode()가 잘 구현되어있어 이를 이용했다고 했는데, 문서에서 찾아보니 아래와 같은 식을 이용하여 계산한다고 한다. S[i]는 S의 i번째 글자이고, n은 문자열의 길이이다. 그냥 아 그렇구나 하고 넘어가기로 했다.

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

hashCode()를 오버라이딩할 때는 다음 세 가지 조건을 만족시켜야 한다.

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

2. equals메소드를 이용한 비교에 의해서 true를 얻은 두 객체에 대해 각각 hashCode()를 호출해서 얻은 결과는 반드시 같아야 한다.

3.equals메서드를 호출했을 때 false를 반환하는 두 객체는 hashCode() 호출에 대해 같은 int값을 반환하는 경우가 있어도 괜찮지만 해싱(hashing)을 사용하는 컬렉션의 성능을 향상시키기 위해서는 다른 int값을 반환하는 것이 좋다.

 

1.9 TreeSet

TreeSet은 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스 이다. 이진 검색 트리는 정렬, 검색, 범위검색(range search)에 높은 성능을 보이는 자료구조이다. 추가, 삭제, 검색에 log n의 시간이 걸린다. 

이진 검색 트리는 다음의 특징을 갖는다.

  • 모든 노드가 최대 두 개의 자식노드를 가질 수 있다.
  • 왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽 자식노드의 값은 부모노드의 값보다 커야 한다.
  • 저장할 때 순차적으로 데이터를 넣지 않으므로 노드의 추가 삭제에 시간이 걸린다.
  • 검색(범위 검색)과 정렬에 유리하다.
  • 중복된 값을 저장하지 못한다.

 

이진 검색 트리는 Set인터페이스를 구현하므로 중복을 허용하지 않으며 저장 순서를 유지하지 않는다. 이진 검색 트리가 자료를 저장하는 방법은 root노드 혹은 parent노드의 왼쪽노드는 root노드/parent노드보다 작은 값을 저장하고, 오른쪽 노드는 큰 값을 저장한다. 이때 노드의 값들을 서로 비교해야하므로 TreeSet이 Comparable을 구현하거나 Comparator를 제공해야 한다.

 

생성자/메소드 설명
TreeSet() 기본 생성자
TreeSet(Collection c) 주어진 컬렉션을 저장하는 TreeSet을 생성
TreeSet(Comparator comp) 주어진 정렬조건으로 정렬하는 TreeSet을 생성
TreeSet(SortedSet s) 주어진 SortedSet을 구현하는 컬렉션을 저장하는 TreeSet을 생성
boolean add(Object o)
boolean addAll(Collection c)		 지정된 객체(o) 또는 Collection(c)의 객체들을 Collection에 추가
Object ceiling(Object o) 지정된 객체와 같은 객체를 반환, 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null
void clear() 저장된 모든 객체를 삭제
Object clone() TreeSet을 복제하여 반환
Comparator comparator() TreeSet의 정렬기준(Comparator)를 반환
boolean contains(Object o)
boolean containsAll(Collection c)		 지정된 객체(o) 또는 Collection의 객체들이 포함되어 있는지 확인
NavigableSet descendingSet() TreeSet에 저장된 요소들을 역순으로 정렬해서 반환
Object first() 정렬된 순서에서 첫번째 객체를 반환
Object floor() 지정된 객체와 같은 객체를 반환, 없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null.
SortedSet headSet(Object toElement) 지정된 객체보다 작은 값의 객체들을 반환
NavigableSet headSet(Object toElement, boolean inclusive) 지정된 객체보다 작은 값의 객체들을 반환. inclusive가 true이면 같은 값의 객체도 포함
Object higher(Object o) 지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 Null
booelan isEmpty() TreeSet이 비어있는지 확인
Iterator iterator() TreeSet의 Iterator를 반환
Object last() 정렬된 순서에서 마지막 객체를 반환
Object lower(Object o) 지정된 객체보다 작은 값을 가진 객체 중에서 제일 가까운 값의 객체를 반환, 없으면 null
Object pollFirst() TreeSet의 첫번째 요소(제일 작은 값의 객체)를 반환
Object pollLast() TreeSet의 마지막 요소(제일 큰 값의 객체)를 반환
boolean remove(Object o) 지정된 객체를 삭제
boolean retainAll(Collection c) 주어진 컬렉션과 공통된 요소만을 남기고 삭제(교집합)
int size() 저장된 객체의 개수를 반환
Splitterator spliterator() TreeSet의 splititerator를 반환
SortedSet subSet(Object fromElement, Object toElement) 범위 검색(fromElement와 toElement사이)의 결과를 반환(끝 범위인 toElement 제외)
NavigableSet<E> subSet(E fromElement, booelan frominclusivve, E toElement, boolean toInclusive) 범위 검색(fromElement와 toElement사이)의 결과를 반환(fromInclusive true이면 끝값에 포함되지 않음)
SortedSet tailSet(Object fromElement) 지정된 객체보다 큰 값의 객체를 반환
Object[] toArray() 저장된 객체를 객체배열로 반환
Object[] toArray(Object[] a) 저장된 객체를 주어진 객체배열에 저장하여 반환 
import java.util.TreeSet;

public class TreeSetPractice {
    public static void main(String[] args) {
        TreeSet set = new TreeSet();
        String from = "b";
        String to = "d";

        set.add("abc");
        set.add("alien");
        set.add("bat");
        set.add("car");
        set.add("dance");
        set.add("disc");
        set.add("elephant");
        set.add("elevator");
        set.add("dZZZ");
        set.add("dzzz");
        set.add("fan");
        set.add("flower");
        set.add("emergency");

        System.out.println(set);
        System.out.println("range search: from " + from + " to " + to);
        System.out.println("result1: " + set.subSet(from, to));
        System.out.println("result2: " + set.subSet(from, to + "zzz"));
        System.out.println("result3: " + set.subSet(from, to + "zzzzzz"));
        System.out.println("result4: " + set.subSet(from, to + "{"));
    }
}

set을 출력한 걸 보면 dZZZ, dance, disc, dzzz이다. 정렬이라는 걸 생각했을 때 우리는 가나다, abc 순으로 생각하기 쉽지만 코드는 컴퓨터에서 돌고 컴퓨터는 아스키 코드값으로 문자열을 검색하므로 dZZZ가 오고 dance가 온다. 

subSet()을 이용하여 범위로 검색할 때, substring같은 메소드가 그러하듯 끝 범위는 포함되지 않는다. 그래서 result1은 c까지 검색한다. 그 다음으로 예제처럼 d에 zzz를 추가했을 때는 끝 범위를 제외하므로 dzzz는 빠진다. 그러면 dzzz도 검색 결과로 나오도록 하는 방법은 무엇이 있을까 생각해봤다. 한 가지는 dzzz보다 z를 하나 더 붙이는 것이고 (실제로는 여러 개를 추가했지만), 다른 한 가지 방법은 아스키코드값으로 더 큰 값을 가지는 {, |, }까지 찾아보는 것이다. 

 

import java.util.TreeSet;

public class TreeSetPractice2 {
    public static void main(String[] args) {
        TreeSet set = new TreeSet();
        int[] score = {80, 90, 50, 35, 45, 65, 10, 100};

        for(int i=0; i< score.length; i++){
            set.add(new Integer(score[i]));
        }

        System.out.println("50보다 작은 값: " + set.headSet(50));
        System.out.println("50보다 작은 값(50포함): " + set.headSet(50, true));
        System.out.println("50보다 큰 값: " + set.tailSet(50));
    }
}

다음 예제도 따라 입력해봤다. TreeSet의 요소 중 입력한 값을 기준으로 그 값보다 큰 값들, 그 값보다 작은 값들을 반환한다. 이 때 subSet에서 그랬듯 끝 범위는 포함하지 않는다. 그러니까 50을 기준으로 headSet과 tailSet을 했을 때, tailSet의 결과값은 50을 포함하지만, headSet의 결과값은 50을 포함하지 않는다. 이 때, 입력한 값 다음으로 true를 입력해주면 headSet의 결과도 50을 포함한다. 아마 headSet과 tailSet의 기본값이 false라서 포함해주지 않나보다.