자바의 신 책을 학습 하면서 내용 정리

Set 인터페이스

중복 제거와 효율적인 입력, 삭제, 탐색 을 위해 만들어짐

구현체

• HashSet : 순서가 전혀 필요 없는 데이터를 해시 테이블에 저장.
  Set 중에 가장 성능 좋음.
• TreeSet: 저장된 데이터의 값에 따라 정렬되는 Set.
  Red-black tree 형태로 값이 저장되며 HashSet 보다는 약간 느림
• LinkedHashSet: 저장된 순서에 따라 값이 정렬됨.
  이 셋 중에서 가장 느림

HashSet

• 내부적으로 객체의 동등성을 비교 할 때 Object 의 hashcode 메서드를 사용한다
• Serializable, Cloneable, Iterable, Collection, Set 을 구현하였다.
• 기본 생성자 사용 시 16개의 공간과 0.75 의 로드팩터를 갖는 객체를 생성.
  - 로드팩터 값이 클 수록 데이터를 찾는 시간이 증가

버킷

내부의 실제 요소를 저장하기 위한 공간

위 코드는 실제 HashSet 의 코드.

내부에 map 형태로 만들어져 있는데, 실제로는 내부의 값을 저장하기 위해 HashMap 을 사용하는 형태로 구현됨

하지만 HashMap 내부는 HashTable 을 기반으로 구현 되었기 때문에 같은 버킷의 형태를 가지게 됨

HashTable 의 버킷은 배열 로 구현되어 있으며 배열의 요소 하나 하나가 일반적으로 LinkedList 를 가지고 있음. 이유는 해시 충돌을 대비하기 위함.

하지만 이건 '일반적인 경우' 에 한정하는데, 그 이유는 Separate Chaining(LinkedList 로 해시 충돌을 해결하는 방식) 은 해시 충돌이 빈번히 발생 할 수록 성능이 떨어지는 문제 때문. 버킷 내부 요소의 LinkedList 의 size 가 8 이상이 되면 버킷 요소를 Tree 자료구조를 갖게 변경. 그리고 size 가 6 이하가 되면 다시 LinkedList 로 변경하여 최적화를 시도.

add(E element)

데이터를 삽입한다

• 해시 충돌이 일어나지 않을 경우: O(1)
• 해시 충돌이 일어날 경우: O(n)
  - Chaining, Open addressing 을 이용하여 해시 충돌을 해결

contains(Object o)

지정한 객체가 존재하는지 확인

• 언제나 O(1) 의 시간 복잡도 로 탐색 가능

remove(Object o)

매개 변수로 넘어온 객체를 삭제

• 시간 복잡도는 언제나 O(1) 로 기대 할 수 있음
• 위에서 설명 하였듯, 해시 충돌을 대비 한 최적화 로직의 적용으로 버킷의 구조를 변경하여 언제나 상수 시간 대의 시간복잡도를 기대 할 수 있음

Queue 인터페이스

데이터를 순서대로 저장하며 정해진 순서에 따라 요소를 꺼내 써야 하는 경우 용이함

public interface Queue<E> extends Collection<E> {
    
    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

구현체

• LinkedList: 이중 연결 리스트. FIFO 를 적용하기 용이함
• ArrayDeque: 동적으로 크기가 조절되는 배열로 구현된 덱(Double-Ended Queue). FIFO, LIFO 를 지원.
• PriorityQueue: 우선순위 큐. 우선순위에 따라 정렬되며 가장 우선순위 가 높은 요소가 먼저 제거됨.

boolean add(E element)

Queue 의 맨 뒤에 요소를 추가 후 true 리턴. O(1)

만일 용량 제한을 위배하는 경우 IllegalStateException 발생

boolean offer(E element)

용량 제한을 위배하지 않는 경우에만 요소를 추가. O(1)

용량 제한을 위배하는 경우 false 리턴.

E remove(E element)

Queue 의 맨 앞의 값을 제거 하며, Queue 에 데이터가 존재하지 않는 경우에는 NoSuchElementException 발생

E poll()

Queue 의 맨 앞의 값을 제거, 데이터가 존재하지 않을 때는 null 리턴

E element()

맨 앞의 요소를 조회. 존재하지 않으면 NoSuchElementException 발생

E peek()

맨 앞의 요소를 조회. 존재하지 않으면 null 리턴.