[Java] Set , HashSet 살펴보기

 

---

Set ? 

- 집합을 다루는 자료구조

- 중복 x, 순서 x

- 대표적인 구현체 : HashSet / TreeSet / LinkedHashSet / EnumSet

- 내부적으로 Map 자료 구조에 Key에 데이터를 담는다 (Map은 Key의 중복 허용하지 않음)

//java.util.HashSet.class
private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object();

public HashSet() {
    this.map = new HashMap();
}

//..

public boolean add(E e) {
    return this.map.put(e, PRESENT) == null; // HashMap의 Key에 element를 담는다
}

 

Map에 Key 값으로 관리가 되고 있었다니 .. (충격)

 

 

HashSet

- 내부적으로 HashMap<E, Object> map 으로 자료 관리한다

- equals(), hashCode() 사용하여 객체의 동등성 확인

TreeSet 

- NavigableMap<E, Object> m = new TreeMap() 으로 자료 관리한다

- 범위 검색과 정렬에 유리

- HashSet보다 데이터 추가/삭제 시간이 더 걸린다 (??, 트리 구조라서 재배치때문인가 싶음)

- 이진 탐색 트리(binary search tree)로 구현

 

LinkedHashSet

- 순서를 보장하는 HashSet

 

 

참고. 시간 복잡도 

https://gyuwon95.tistory.com/99

[Java] 자바 컬렉션들의 시간 복잡도 (Big O)

---

Interface Set 

- java.util 패키지 위치

- Java Collection Framework

public interface Set<E> extends Collection<E> { // Collection Interface 상속
    int size();

    boolean isEmpty();

    boolean contains(Object var1);

    Iterator<E> iterator();

    Object[] toArray();

    <T> T[] toArray(T[] var1);

    boolean add(E var1);

    boolean remove(Object var1);

    boolean containsAll(Collection<?> var1);

    boolean addAll(Collection<? extends E> var1);

    boolean retainAll(Collection<?> var1);

    boolean removeAll(Collection<?> var1);

    void clear();

    boolean equals(Object var1);

    int hashCode();
    
    //.. 이하 생략
}

 

HashSet<E> 살펴보기

- java.util 패키지 위치

- Set 인터페이스 구현체 

- 내부적으로 HashMap<E, Object> map 에 자료를 저장하고 관리함

 

1) 데이터 추가 

HashSet의 경우 내부적으로 HashMap 을 사용하고, Key에 element를 담는다

// java.util.HashSet
public boolean add(E e) {
    return this.map.put(e, PRESENT) == null;
}

*.put(K key, V, value) 의 경우 키에 대한 값이 있으면 이전 값(=PRESENT)을 리턴하고, 없을 경우 null을 리턴한다

 

2) 데이터 삭제 

- HashMap에 구현된 remove() 메서드 호출

- 값이 존재할 경우 이전 값을 리턴하고, 없을 경우 null 리턴 (HashSet의 값은 클래스 맴버 Object PRESENT로 고정)

public boolean remove(Object o) {
    return this.map.remove(o) == PRESENT;
}

 

3) 데이터 확인 

내부적으로 Map의 containsKey() 호출하여 존재 여부 확인

public boolean contains(Object o) {
    return this.map.containsKey(o);
}

 

4) 교집합, 합집합, 차집합 (by 테스트 학습)

각 instance method 와 stream api 사용하는 경우를 살펴본다

 

초기화 선언

출처 baeldung

public class Test {
    private Set<Integer> setA;
    private Set<Integer> setB;

    private static Set<Integer> setOf(Integer... values) {
        return new HashSet<>(Arrays.asList(values));
    }

    @BeforeEach
    void setUp() {
        setA = setOf(1, 2, 3, 4);
        setB = setOf(2, 4, 6, 8);
    }

	//.. 테스트 작성
}

 

 

Intersection (교집합)

출처 baeldung

 

*.retainAll() 의 경우 AbstractCollection.class에 메서드 호출한다

// java.util.AbstractCollection
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<E> it = this.iterator(); // this = 기준

    while(it.hasNext()) {
        if (!c.contains(it.next())) { // c에 포함되어 있지 않는 경우 this의 해당 요소 삭제
            it.remove();
            modified = true;
        }
    }

    return modified;
}

 

예시

@DisplayName("두 집합의 교집합(Intersection)을 구한다")
@Test
void retainAll() {
    //given
    Set<Integer> givenData = setOf(2, 4);

    //when
    setA.retainAll(setB);

    //then
    assertThat(setA).hasSize(2).isEqualTo(givenData);
    assertThat(setA).containsExactly(2, 4);
}

@DisplayName("stream filter 로 Set의 교집합을 구한다")
@Test
void intersectionByStream() {
    //given
    Set<Integer> givenData = setOf(2, 4);

    //when
    Set<Integer> result = setA.stream().filter(setB::contains).collect(Collectors.toSet());

    //then
    assertThat(result).isEqualTo(givenData);
}

 

 

Union (합집합)

출처 baeldung

 

*.addAll() 의 경우 AbstractCollection.class에 메서드 호출

// java.util.AbstractCollection
public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    Iterator var3 = c.iterator();

    while(var3.hasNext()) {
        E e = var3.next();
        if (this.add(e)) { // this에 c의 요소가 없는 경우 true 리턴
            modified = true;
        }
    }

    return modified;
}


// HashSet.class
public boolean add(E e) {
   return this.map.put(e, PRESENT) == null; // 키 존재하면 이전 값, 없으면 null 리턴
}

 

예시

@DisplayName("두 집합의 합집합(Union)을 구한다")
@Test
void addAll() {
    //given
    Set<Integer> givenData = setOf(1, 2, 3, 4, 6, 8);

    //when
    setA.addAll(setB);

    //then
    assertThat(setA).hasSize(6).isEqualTo(givenData);
    assertThat(setA).containsExactly(1, 2, 3, 4, 6, 8);
}

@DisplayName("Stream concat 으로 Set의 합집합을 구한다")
@Test
void unionByStream() {
    //given
    Set<Integer> givenData = setOf(1, 2, 3, 4, 6, 8);

    //when
    Set<Integer> result = Stream.concat(setA.stream(), setB.stream()).collect(Collectors.toSet());

    //then
    assertThat(result).hasSize(6).isEqualTo(givenData);
}

 

 

Relative Complement (차집합)

출처 baeldung

 

- *.removeAll() 의 경우 AbstractSet.class에 오버라이딩 메서드를 호출한다.

- AbstractCollection 클래스 상속받아 AbstractSet.class에서 오버라이딩한 것으로 확인

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator i;
    Object e;
    if (this.size() > c.size()) { // 사이즈 기준으로 분리 
        for(i = c.iterator(); i.hasNext(); modified |= this.remove(e)) { // this에서 e(c 컬렉션)를 지움
            e = i.next();
        }
    } else {
        i = this.iterator(); // this를 기준

        while(i.hasNext()) {
            if (c.contains(i.next())) { // c 콜렉션에 값이 있으면 remove
                i.remove();
                modified = true;
            }
        }
    }

    return modified;
}

 

예시

@DisplayName("집합 A 기준으로 집합 B에 대한 차집합을 구한다")
@Test
void removeAll() {
    //given
    Set<Integer> givenData = setOf(1, 3);

    //when
    setA.removeAll(setB);

    //then
    assertThat(setA).hasSize(2).isEqualTo(givenData);
    assertThat(setA).containsExactly(1, 3);
}

@DisplayName("stream filter 로 Set의 차집합을 구한다")
@Test
void relativeComplementByStream() {
    //given
    Set<Integer> givenData = setOf(1, 3);

    //when
    Set<Integer> result = setA.stream().filter(a -> !setB.contains(a)).collect(Collectors.toSet());

    //then
    assertThat(result).hasSize(2).isEqualTo(givenData);
}

 

---

참고

자바의 정석 - HashSet (1)

https://www.baeldung.com/java-set-operations