Collection - Set

Set

순서에 상관 없이, 어떤 Element가 존재하는지를 확인하기 위한 용도로 많이 사용

중복되는 것을 방지하고, 원하는 값이 포함되어 있는지를 확인하는 것이 주 용도

Set Interface (in Java)

구현한 주요 클래스

• HashSet : 순서가 전혀 필요없는 Element를 HashTable에 저장. Set 중 가장 성능이 좋음

• TreeSet : 저장된 Element의 값에 따라서 정렬되는 Set. red-black이라는 tree 타입으로 값이 저장되며, Hashset보다 약간 성능이 느림

• LinkedHashSet : 연결된 목록 타입으로 구현된 HashTable에 Element를 저장. 저장된 순서에 따라 값이 정렬. 성능이 가장 나쁨

성능의 차이가 나타나는 이유는 데이터 정렬 때문이지만, 데이터가 많지 않으면 체감하기는 어려움

red-black Tree(적흑나무) : 각 노드의 색을 붉은 색 혹은 검은 색으로 구분하여 데이터를 빠르고, 쉽게 찾을 수 있는 구조의 binary tree(이진 트리) [참고 : 위키피디아 : 레드-블랙 트리]

HashSet Class

상속 관계

java.lang.Object
    java.util.AbstractCollection<E>
        java.util.AbstractSet<E> // 3가지 메서드가 구현되어 있음
            java.util.HashSet<E>

java.util.AbstractSet<E>의 메서드들

/* Set은 데이터가 중복되는 것을 허용하지 않으므로, Element가 같은지를 확인하는 작업이 핵심
 * equals()와 hashCode()는 불가분의 관계
 */

// Object Class에 선언된 메서드 오버라이딩
@Override
equals()

// Object Class에 선언된 메서드 오버라이딩
@Override
hashCode()

// Collection을 매개 변수로 받아, 매개 변수 Collection에 포함된 모든 Elements를 지울 때 사용
removeAll(Collection<?> C)

구현한 Interface

// 원격으로 Object를 전송하거나, 파일에 저장할 수 있음을 지정
Serializable

// Object Class의 clone()이 제대로 수행될 수 있음을 지정(복제 가능)
Cloneable

// for-each를 사용할 수 있음
Iterable<E>

// 여러 개의 Objects를 하나의 Object에 담아 처리할 때의 메서드 지정
Collection <E>

/* Set 처리에 관련된 메서드 지정
 * Set은 List의 메서드와 대부분 비슷하지만, 순서가 없으므로 위치와 관련된 메서드는 없음
 *   - get(int index), indexOf(Object o) 같은 것...
 */
Set<E>

생성자

// 16개의 공간과 0.75의 load factor를 갖는 객체를 생성
HashSet()

// 매개 변수로 받은 Collection Object의 데이터를 HashSet에 담음
HashSet(Collection<? extends E> c)

// 매개 변수로 받은 개수만큼의 저장 공간과 0.75의 load factor를 갖는 객체를 생성
HashSet(int initialCapacity)

// 첫 번째 매개 변수로 받은 개수만큼의 저장 공간과 두 번째 매개변수로 받은 만큼의 load factor를 갖는 객체 생성
HashSet(int initialCapacity, float loadFactor)

load factor(로드 팩터)란?
(데이터의 개수) / (저장 공간)을 의미

데이터의 개수 > 로드 팩터
- 저장 공간의 크기는 증가
- 해시 재정리 작업(rehash)해야 함
→ 내부에 갖고 있는 자료구조를 재생성하는 단계를 거쳐야 하므로 성능에 영향

로드팩터 ↑
- 공간이 넉넉해짐
- 데이터를 찾는 시간이 증가함

초기 공간 개수와 로드 팩터는 데이터의 크기를 고려하여 산정하는 것이 좋음
- 초기 크기 > (데이터의 개수)/(로드 팩터) → 데이터를 쉽게 찾기 위한 rehash 작업이 발생하지 않음
- 대량의 데이터를 담아 처리할 때는 초기 크기와 로드 팩터의 값을 조절해가면서 적당한 값을 찾아야 함

잘 모르는 경우, 로드 팩터를 따로 지정하지 말고 기본 값으로 사용할 것

주요 메서드

부모 클래스인 AbstractSet과 AbstractCollection에 선언 및 구현되어 있는 메서드를 그대로 사용하는 경우가 많음

HashSet에 선언되어 있는 메서드 목록

// Element를 추가
boolean add(E e)

// 모든 Elements를 제거
void clear()

// HashSet Object의 복제하되, 담겨있는 Elements들을 복제하진 않음
Object clone()

// 지정한 Object가 있는지 확인
boolean contains(Object o)

// 비었는지 확인
boolean isEmpty()

// Elements를 꺼내기 위한 Iterator 객체를 리턴
Iterator<E> iterator()

// 매개 변수로 넘어온 Object를 제거
boolean remove(Object o)

// Elements의 개수를 리턴
int size()

주의할 점

null인 배열을 매개 변수로 받는다면, NullPointerException이 발생함

Element 호출법

// for-each
for (String temp : JamieSet) {
    System.out.println(temp);
}

// Iterator
import java.util.Iterator;
Iterator<String> it = carSet.iterator();
while(it.hasNext()) {
    System.out.print(iter.next());
}