Set
- Java
- 2021년 6월 1일
Set은 자바의 Collection중에 객체를 중복하지 않고 하나만 저장하는 자료구조로 List와 다르게 저장순서(index)를 따로 저장하지 않기 때문에 이를 통해 접근할 수 없다.
Set interface 제공 메서드
| 메서드 | 리턴 값 | 설명 |
|---|---|---|
| add(E e) | boolean | 객체 추가성공하면 true |
| addAll(Collection c) | boolean | 컬렉션을 추가하면 데이터들을 Set에 맞게 저장 |
| remove(Object o) | boolean | 객체 삭제 |
| contains(Object o) | boolean | 객체가 포함되었는지 여부 |
| eqauls(Object o) | boolean | 같은지 비교 |
| clear() | void | Set 초기화 |
| iterator() | Iterator | set 요소 접근하기 위한 Iterator객체 반환 |
1. HashSet
Set을 구현한 구현체중에 하나로 Key를 Hash와 하여 저장하는 Set이다.
//선언
Set<Integer> set = new HashSet<>();
//add
System.out.println(set.add(1)); //true
System.out.println(set.add(1)); //false
System.out.println(set.add(0)); //true
System.out.println(set.add(-1)); //true
System.out.println(set.add(2)); //true
//iterator를 이용한 모든 key 접근
Iterator<Integer> it = set.iterator();
while(it.hasNext()){
System.out.println(it.next()); //0, -1, 1, 2
}
//remove
System.out.println(set.remove(1)); //true
//contains
System.out.println(set.contains(1)); //false
it = set.iterator();
while(it.hasNext()){
System.out.println(it.next()); //2
}
HashSet은 Set에서 제공하는 메서드외에는 별도로 제공하는 메서드가 없고 내부적으로는 HashMap으로 동작하기 때문에 접근속도가 빠르다. 그리고 별도의 index를 가지지 않기 때문에 모든 데이터를 순회하고 싶을때는 Iterator를 이용해서 접근하면 된다.
//HashSet 내부
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
위는 HashSet의 내부를 일부 가져온 것인데 살펴보면 내부 필드로 HashMap을 가지고 있어 이를 이용(합성)해서 HashSet을 구현하고 있고 add와 같은 메서드도 Map의 put메서드를 이용해서 데이터를 추가하는 것을 볼 수 있다.
여기서 한가지 더 유심히 볼 부분이 PRESENT라는 객체인데 Set은 key만을 저장하는 자료구조이기 때문에 value는 어떤 객체가 오든 상관이없다. 그래서 HashSet을 만든 개발자는 어떤 HashSet에서든 모든 데이터는 value값을 동일한 value값을 가르키도록 static으로 PRESENT라는 객체를 생성해 메모리를 절약하는식으로 구성을 하였다.
2. LinkedHashSet
HashSet과 거의 동일하지만 데이터의 입력된 순서대로 저장을하고 관리를 한다. 기본적으로는 HashSet보다는 성능이 조금 뒤쳐지지만, HashMap의 capacity가 커지는 경우에는 HashSet보다는 성능이 좋다.
Set<Integer> set = new LinkedHashSet<>();
System.out.println(set.add(1)); //true
System.out.println(set.add(0)); //true
System.out.println(set.add(-1)); //true
System.out.println(set.add(2)); //true
Iterator<Integer> it = set.iterator();
while(it.hasNext()){
System.out.println(it.next()); //1, 0, -1, 2
}
LinkedHashSet도 Set의 메서드만을 갖고 있고, HashSet과 비교해해보면 데이터를 추가한 순서대로 출력하는 것을 볼 수 있다.
3. TreeSet
TreeSet은 정렬된 상태의 Set을 사용하고 싶을때 사용할 수 있는 구현체로 SortedSet을 상속받은 NavigableSet을 구현한 구현체이다.
◾ 제공 메서드
| 메서드 | 리턴 값 | 설명 |
|---|---|---|
| add(E e) | boolean | 객체 추가성공하면 true |
| addAll(Collection c) | boolean | 컬렉션을 추가하면 데이터들을 Set에 맞게 저장 |
| remove(Object o) | boolean | 객체 삭제 |
| contains(Object o) | boolean | 객체가 포함되었는지 여부 |
| eqauls(Object o) | boolean | 같은지 비교 |
| clear() | void | Set 초기화 |
| iterator() | Iterator | set 요소 접근하기 위한 Iterator객체 반환 |
| descendingIterator() | Iterator | 현재 정렬 순서의 반대로의 Iterator객체 반환 |
| ceiling(E e) | E | 객체보다 크거나 같은 객체중 가장 가까운 객체 return |
| higher(E e) | E | 객체보다 큰 객체중 가장 가까운 객체 return |
| floor(E e) | E | 객체보다 작거나 같은 객체중 가장 가까운 객체 return |
| lower(E e) | E | 객체보다 작은 객체중 가장 가까운 객체 return |
| first() | E | 첫번째 객체 return |
| last() | E | 마지막 객체 return |
| headSet(E e) | SortedSet | 객체보다 큰 객체들만 모아 Set return |
| headSet(E,boolean) | NavigableSet | headSet()에서 객체E를 포함할지 결정해서 return |
| subSet(E from,E to) | SorteSet | from는 포함하고 to는 포함하지 않고 to까지의 객체 Set return |
| subSet(E from,boolean, E to,boolean) | NavigableSet | from부터 to 각각 같은거 포함할지 결정해서 Set return |
| tailSet(E e) | SortedSet | 객체보다 작거나 같은 객체Set return |
| tailSet(E,boolean) | NavigableSet | 객체를 포함할지 결정해 Set return |
| pollFirst() | E | 첫번째 객체 삭제하면서 return |
| pollLast() | E | 마지막 객체 삭제하면서 return |
◾ 사용 예
TreeSet<Integer> set = new TreeSet<>(Arrays.asList(4,2,3,-1,0,8,4,2,7,10));
System.out.println(set); //[-1, 0, 2, 3, 4, 7, 8, 10]
//근접한 요소 접근
System.out.println(set.ceiling(4)); //4
System.out.println(set.higher(4)); //7
System.out.println(set.floor(2)); //2
System.out.println(set.floor(2)); //0
System.out.println();
//부분집합 추출
System.out.println(set.headSet(3)); //[-1, 0, 2]
System.out.println(set.headSet(3,true)); //[-1, 0, 2, 3]
System.out.println(set.subSet(3,8)); //[3, 4, 7]
System.out.println(set.subSet(3,false,8,true)); //[4, 7, 8]
System.out.println(set.tailSet(4)); //[4, 7, 8, 10]
System.out.println(set.tailSet(4,false)); //[7, 8, 10]
System.out.println();
//Iterator
Iterator it = set.iterator();
while(it.hasNext()){
System.out.print(it.next() + " "); //-1 0 2 3 4 7 8 10
}
System.out.println();
//역순 Iterator
it = set.descendingIterator(); //10 8 7 4 3 2 0 -1
while(it.hasNext()){
System.out.print(it.next() + " ");
}
System.out.println();
//내림차순 TreeSet 선언
TreeSet<Integer> descSet = new TreeSet<>(Collections.reverseOrder());
descSet.addAll(Arrays.asList(4,2,3,-1,0,8,4,2,7,10));
System.out.println(descSet); //[10, 8, 7, 4, 3, 2, 0, -1]
TreeSet은 이름에서 유추할 수 있듯이 내부적으로 Tree로 구성되어있는 Set이다. 그렇기 때문에 특정 원소를 기준으로 다음,이전값이나 부분집합을 구할 수 있는 것인데 Tree는 데이터에따라 잘못하면 편향트리가 되어 접근하는데 O(N)이 소모되기 때문에 Balancing을 해주어야한다. 그래서 TreeSet도 내부를 봐보면 HashSet이 HashMap을 이용해서 합성한 것 처럼 TreeSet도 TreeMap을 이용해서 합성해 구현되어 있다.
//TreeSet 내부구조 중 일부
private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();
public TreeSet() {
this(new TreeMap<>());
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
TreeMap은 SortedMap의 구현체로 내부적으로 Red Black Tree로 구현되어 있어 balancing을 수행한다. 이런 이유로 HashSet은 O(1)만에 데이터를 접근할 수 있지만 TreeSet은 접근도 O(logN), 삽입/수정도 balancing수행으로 O(logN)만큼의 시간이 소요된다.
특정한 목적이 있지 않는이상 HashSet을 이용하는 것이 performance에 좋다.
