Intro
Set 자료구조.. 뭘까?? 우선 Set에 대해 자세히 공부하기 전에 저는 'Set은 값들의 순서를 보장하지않고 중복되지 않는 자료구조' 정도로 알고있습니다. 그리고 Set자료구조를 사용할 때는 주로 중복을 제거해서 사용해야하는 경우 자주 사용했었습니다. 이번 글에서는 Java에는 어떤 종류의 Set이 있고 각각의 Set의 특징에 대해 살펴보겠습니다.
Set이 왜 필요할까?
위에서 언급했던 것처럼 Set은
순서에 상관없이, 어떤 데이터가 존재하는지를 확인하는 용도로 많이 사용됩니다.
예를 들어
어떤 서버에 사용자가 요청한 로그가 있을 때 이 서버에 요청한 IP를 기준으로 사용자의 수가 얼마나 되는지 확인해보려고 한다.
1분간 동일한 서버에 요청하는 중복 사용자의 수는 굉장히 많은데 만약 배열을 써서 확인을 하게된다면 indexOf()라는 메서드로 해당 IP가 있는지 확인한 다음에 add() 메서드로 추가해주어야한다.
하지만 만약 Set을 사용하게 된다면 데이터를 그냥 추가만 해주면 된다.
Set인터페이스를 구현한 주요 클래스
java에서 Set인터페이스를 구현한 주요 클래스는 HashSet, TreeSet, LinkedHashSet이 있고 특징은 아래와 같습니다.
HashSet : 순서가 전혀 필요없는 데이터를 해시 테이블에 저장한다. Set 중에 가장 성능이 좋다.
TreeSet : 저장된 데이터의 값에 따라서 정렬되는 셋이다. red-black이라는 트리 타입으로 값이 저장되며, Hashset 보다 약산 성능이 느리다.
LinkedHashSet : 연결된 목록 타입으로 구현된 해시 테이블에 데이터를 저장한다. 저장된 순서에 따라 값이 정렬된다. 대신 성능이 이 셋중에서 가장 나쁘다.
이렇게 성능차이가 발생하는 이유는 데이터 정렬 때문입니다.
HashSet에 대해서 파헤쳐보자
Set을 구현한 여러 클래스 중에서 HashSet에 대해 자세히 살펴보겠습니다.
우선 HashSet 클래스의 상속 관계를 보겠습니다.
java.lang.Object
- java.util.AbstractCollection<E>
- java.util.AbstractSet<E>
- java.util.HashSet<E>AbstractCollection을 확장한 것은 ArrayList와 동일하지만 HashSet은 AbstractSet을 확장했습니다.
Set은 무엇보다도 데이터가 중복되는 것을 허용하지 않으므로, 데이터가 같은지를 확인하는 작업은 Set의 핵심 작업입니다.
따라서 equals()와 hashCode()메소드를 구현하는 부분은 Set에서 매우 중요합니다.
List에는 정의되어있지만 Set에는 정의되어있지 않는 메소드는 어떤 것이 있을까?
Set은 순서가 없습니다. 따라서 순서가 매개 변수로 넘어가는 메소드나, 수행결과가 데이터의 위치와 관련된 메소드들은 Set인터페이스에서 필요가 없습니다. 그러므로 get(int, index) 나 indexOf(Object o)와 같은 메소드들은 존재하지 않습니다.
HashSet의 생성자들에 대해 살펴보자(4개)
HashSet 클래스에는 아래와 같이 4개의 생성자가 존재합니다.
HashSet()
public HashSet() {
map = new HashMap<>();
}데이터를 저장할 수 있는 16개의 공간과 0.75의 로드 팩터를 갖는 객체를 생성합니다.
public HashSet(Collection<? extends E> c)
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}매개변수로 받은 컬렉션 객체의 데이터를 HashSet에 담습니다.
public HashSet(int initialCapacity)
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}매개변수로 받은 개수만큼의 데이터 저장공간과 0.75의 로드 팩터를 갖는 객체를 생성합니다.
public HashSet(int initialCapacity, float loadFactor)
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}첫 매개변수로 받은 개수만큼의 데이터 저장공간과 두번째 매개변수로 받은 만큼의 로드팩터를 갖는 객체를 생성합니다.
로드 팩터란?
해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것 입니다.
- 로드 팩터 비율에 따라서 해시 함수를 재작성해야 될지, 또는 해시 테이블의 크기를 조정해야할지 결정합니다. 또한 이 값은 해시 함수가 키들을 잘 분산해주는지를 말하는 효율성 측정에도 사용합니다.
간단하게 말하면 로드팩터가 0.75일 경우 총 버킷의 75%에 달하는 데이터가 적재된다면 배열을 확장합니다.
코드로 살펴보기
public class Main {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
Object o = new Object();
hashSet.add(o);
}
}위와 같은 코드가 있고 실행되었을 경우
HashSet의 내부 함수인
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}가 호출됩니다.
결론
최근에 공부를 계속해오면서 느낀점은 자바를 만든 창조주는 무엇인가를 만들 때 이유 없이 만든 것은 하나도 없다는 생각이 들었습니다. Set에 대해 알고는 있었지만 TreeSet, LinkedHashSet등 다른 Set에 대해서는 잘 알지 못했었는데 이번 기회에 잘 알 수 있게되서 다행이라고 생각했습니다. 그리고 앞으로는 Set을 써야겠다는 판단이 들면 HashSet, TreeSet, LinkedHashSet에 대해 무엇을 써야할지 고민하고 코드를 작성해야겠습니다!!
