Set에 대하여 2 : 주요 구현체

이전 글(https://baby-care-dev.tistory.com/47)에서는 Set의 구조와 메서드에 대해 알아봤다. 메서드 동작은 알았지만 구현체별로 어떻게 내부가 처리되는지도 궁금하다. 예를 들면 TreeSet이나 LinkedHashSet은 어떻게 순서를 보장하는지 등 말이다. 이번에는 구현체별 특징과 공통점/차이점에 대해 알아보자.

 

Set 상속 구조

---

Set 상속 구조

위 그림에 나온 구현체들 보다 많은 구현 클래스들이 존재하는데, 일단 이정도만 알아도 될 듯 싶다. 모두 공통적으로 AbstractSet이라는 추상 클래스를 상속받고 있다. 이 AbstractSet에서 추상화된 공통점을 파악할 수 있으니 먼저 알아보자.

 

AbstractSet

---

제공하는 메서드는 equals, hashCode, removeAll이다. equals부터 알아보자.

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {
    public boolean equals(Object o) {
        if (o == this)
            return true;

        if (!(o instanceof Set))
            return false;
        Collection<?> c = (Collection<?>) o;
        if (c.size() != size())
            return false;
        try {
            return containsAll(c);
        } catch (ClassCastException | NullPointerException unused) {
            return false;
        }
    }
    
    //...
}

인자로 받은 o의 참조값이 동일하면 true, o가 Set 타입이 아니면 당연히 false, size가 다르면 false이다. 마지막으로 containsAll로 모든 원소들을 순회하며 비교한 결과를 리턴하고 도중에 ClassCast가 잘못되거나 Null 참조가 발생하면 false를 반환한다. 실무에서 도메인 로직 짤 때에는 containsAll 정도만 호출해서 코드를 간결하게 할 때도 있는데, 성능상 이점을 얻기 위해 여러 전처리를 통해 early exit하는게 눈에 띈다.

 

이번엔 hasCode를 보자.

public int hashCode() {
    int h = 0;
    Iterator<E> i = iterator();
    while (i.hasNext()) {
        E obj = i.next();
        if (obj != null)
            h += obj.hashCode();
    }
    return h;
}

iterator로 원소들을 순회하여 각 해시코드 값을 더한 값을 반환한다. hashCode에 대한 지식이 없다보니 이렇게 해도 중복이 안나나 싶다. 나중에 더 공부해봐야겠다.

 

마지막으로 removeAll을 보자.

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;

    if (size() > c.size()) {
        for (Object e : c)
            modified |= remove(e);
    } else {
        for (Iterator<?> i = iterator(); i.hasNext(); ) {
            if (c.contains(i.next())) {
                i.remove();
                modified = true;
            }
        }
    }
    return modified;
}

전달받은 인자가 null이면 NPE를 발생시킨다. 현재 Set이 전달받은 컬렉션의 사이즈보다 크면 현재 Set을 기준으로 순회하여 remove를 수행한다. 재미있는 점은 modified라는 boolean 변수와 remove(e)의 반환값을 비트 OR 연산자(|=)로 비교한다는 것이다. 전달받은 컬렉션의 사이즈가 더 크면 전달받은 컬렉션을 기준으로 순회하는데, 같은 원소가 발견되면 Iterator에서 바로 remove해준다.

그리고 제거 여부(변경 여부)를 알려주는 modified 값을 반환한다.

 

구현 클래스들 간단히 알아보기

---

먼저 각 구현 클래스들 정의를 알아보자. Java doc 기준이다.

HashSet

해시 테이블을 이용하여 Set 인터페이스를 구현한 클래스이다. 해시 테이블로 HashMap을 사용하고 순서는 보장하지 않는다. 원소에 null을 허용한다. 해시 테이블을 사용하기 때문에 add, remove, cotains, size 같은 오퍼레이션들을 상수 시간에 수행한다.

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    @java.io.Serial
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a new, empty set; the backing {@code HashMap} instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }
    
    //...
}

LinkedHashSet

순서를 보장하는 HashSet이다. HashSet은 HashMap을 이용하고, LinkedHashSet은 LinkedHashMap을 이용한다. HashSet과 마찬가지로 add, contains, remove 오퍼레이션을 상수 시간에 수행한다. 

LinkedHashSet 생성자

TreeSet

SortedSet을 상속받은 NavigableSet을 구현한 클래스로 Comparator에 의해 순서를 보장하는 Set이다. add, remove, contains 오퍼레이션을 log(n)의 시간 복잡도로 수행한다. 내부에 NavigableMap을 테이블로 가지고 있는데, NavigableSet를 상속한 TreeMap이 실제로 할당된다. 생성시 별도의 Comparator를 인자로 받지 않으면 NaturalOrder로 정렬이 되고, 받으면 해당 Comparator 규칙으로 정렬된다.

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    /**
     * The backing map.
     */
    private transient NavigableMap<E,Object> m;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a set backed by the specified navigable map.
     */
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }


    public TreeSet() {
        this(new TreeMap<>());
    }
    
    public TreeSet(Comparator<? super E> comparator) {
    	this(new TreeMap<>(comparator));
    }
}

EnumSet

Enum 타입만 원소로 받는 Enum에 특화된 Set이다. 데이터가 비트 단위로 표현되어 매우 빠른 연산을 자랑한다. Enum 내 상수가 선언된 순서로 정렬된다. Enum이 null일 수 없으므로 null을 원소로 받으면 NPE를 발생시킨다. 특이한 점은 Enum 타입을 분석하여 해당 Enum의 상수 개수가 64개 이하이면 RegularEnumSet을 반환하고, 초과하면 JumboEnumSet을 반환한다.

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>
    implements Cloneable, java.io.Serializable
{
    // declare EnumSet.class serialization compatibility with JDK 8
    @java.io.Serial
    private static final long serialVersionUID = 1009687484059888093L;

    /**
     * The class of all the elements of this set.
     */
    final transient Class<E> elementType;

    /**
     * All of the values comprising E.  (Cached for performance.)
     */
    final transient Enum<?>[] universe;

    EnumSet(Class<E>elementType, Enum<?>[] universe) {
        this.elementType = elementType;
        this.universe    = universe;
    }
    
   public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
    Enum<?>[] universe = getUniverse(elementType);
    if (universe == null)
        throw new ClassCastException(elementType + " not an enum");

    if (universe.length <= 64)
        return new RegularEnumSet<>(elementType, universe);
    else
        return new JumboEnumSet<>(elementType, universe);
	}
}

EnumSet 예시

위와 같이 알파벳순으로 BASEBALL, LOL, SOCCER, TAEKWONDO를 EnumSet에 넣었지만 출력은 Sports에 선언된 순서인 SOCCER, BASEBALL, LOL, TAEKWONDO로 된다.

CopyOnWriteArraySet

thread-safe한 Set이다. 스냅샷 형태의 Iterator를 사용하므로 비용이 비싸고, add와 같은 변경작업은 특히 더 심하니(변경이 일어날 때마다 Snapshot 생성) 주의해서 쓰도록 하자.

 

메서드별 구현체 차이점

---

add

HashSet, LinkedHashSet, TreeSet은 모두 내부적으로 가지고 있는 map에 put하여 처리한다. 각각 사용하는 map 구현체가 달라 어떤 map 구현체인지에 따라 추가하는 방식이 정해진다. HashSet을 보면 아래와 같이 HashMap에 인자로 전달받은 원소와 더미 Object 하나를 put한다.

HashSet의 add 오퍼레이션

EnumSet은 아래와 같이 비트연산으로 바로 추가하여 빠르다. 비트연산에 대해서는 조금 더 공부해봐야겠다.

public boolean add(E e) {
    typeCheck(e);

    long oldElements = elements;
    elements |= (1L << ((Enum<?>)e).ordinal());
    return elements != oldElements;
}

CopyOnWriteArraySet은 add연산을 CopyOnWriteArrayList에 맡긴다.

CopyOnWriteArraySet의 add

CopyOnWriteArrayList의 addIfAbsent는 아래와 같이 스냅샷을 가지고 오고 lock을 잡고 안에 있는 배열을 복사해서 넣는 비용이 큰 작업을 수행한다.

CopyOnWriteArrayList

size, isEmpty

모두 내부에 저장하고 있는 map이나 array의 사이즈를 가지고 와 개수를 반환(return)하거나 0과 비교해 boolean값을 반환(isEmpty)한다.

contains

HashSet, LinkedHashSet, TreeSet 모두 각자 가지고 있는 map의 contains에 의존한다. EnumSet은 아래와 같이 비트 비교 연산을 수행한다.

public boolean contains(Object e) {
    if (e == null)
        return false;
    Class<?> eClass = e.getClass();
    if (eClass != elementType && eClass.getSuperclass() != elementType)
        return false;

    return (elements & (1L << ((Enum<?>)e).ordinal())) != 0;
}

CopyOnWriteArraySet은 내부 array를 순회하며 찾기 때문에 다른 Set에 비해 성능상 약점이 있다.

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    Object[] es = getArray();
    return indexOfRange(o, es, 0, es.length);
}

private static int indexOfRange(Object o, Object[] es, int from, int to) {
    if (o == null) {
        for (int i = from; i < to; i++)
            if (es[i] == null)
                return i;
    } else {
        for (int i = from; i < to; i++)
            if (o.equals(es[i]))
                return i;
    }
    return -1;
}

 

마지막으로 Set 구현체별 성능 비교

---

구현체별로 add 성능을 측정하기 위해 KoreanLetter라는 완성형 한글 2350자를를 모두 상수로 담은 enum을 만들고 무식하게 add해보았다.

구현체별 성능

EnumSet이 가장 빠를 것이라고 기대했지만 의외로 하위권이었다. HashSet, LinkedHashSet, TreeSet, EnumSet, CopyOnWriteArraySet 순서로 원소 추가가 빨랐다. 구현할 비즈니스 로직에 따라 다르겠지만 왠만하면 HashSet을 쓰는 것이 나아보인다.