[F-Lab 챌린지 6일차] TIL : 자바의신 23장 - Set & Queue

성수데브리·2023년 7월 4일

f-lab_java

목록 보기

5/73

학습 목표

Set
Queue

학습 결과 요약

HashSet 은 내부적으로 HashMap 으로 구현한다.

학습 내용

Set

특징

순서 상관 없이, 어떤 데이터가 존재하는지 확인하기 위한 용도로 많이 사용한다
요소의 중복 허용 안한다.
null 은 1개 까지만 허용한다
add, equals, hashCode 에 추가 규정을 명시함
- add
  
  Adds the specified element to this set if it is not already present (optional operation). More formally, adds the specified element e to this set if the set contains no element e2 such that Objects.equals(e, e2). If this set already contains the element, the call leaves the set unchanged and returns false. In combination with the restriction on constructors, this ensures that sets never contain duplicate elements.
- equals
  
  Compares the specified object with this set for equality. Returns true if the specified object is also a set, the two sets have the same size, and every member of the specified set is contained in this set (or equivalently, every member of this set is contained in the specified set). This definition ensures that the equals method works properly across different implementations of the set interface.
- hashCode
  
  Returns the hash code value for this set. The hash code of a set is defined to be the sum of the hash codes of the elements in the set, where the hash code of a null element is defined to be zero. This ensures that s1.equals(s2) implies that s1.hashCode()==s2.hashCode() for any two sets s1 and s2, as required by the general contract of Object.hashCode.
  
  set 의 hashCode 는 set 에 있는 요소들의 hashCode 의 합계다.
```
HashSet<Mock> hashSet = new HashSet<>();
Mock a = new Mock("A");
Mock b = new Mock("B");
System.out.println("hashCode a + b = " + (a.hashCode() + b.hashCode()));
hashSet.add(a);
hashSet.add(b);
System.out.println("hashCode hashSet = " + hashSet.hashCode());

------- 출력 결과 -------
hashCode a + b = 724073426
hashCode hashSet = 724073426
```

Set 구현 클래스

https://qph.cf2.quoracdn.net/main-qimg-2b6812dceb05fa46a0cb130d9adf2043

HashSet 데이터 정렬을 하지 않으므로 Set 구현 클래스중 성능이 가장 좋다.
TreeSet 값에 따라 데이터를 정렬한다. red-black 트리 구조로 저장한다. HashSet 보다 약간 성능이 느리다.
LinkedHashSet 연결된 목록 타입으로 구현된 해시 테이블에 데이터를 저장한다. 저장된 순서에 따라서 값이 정렬된다. 그래서 셋 중에서 성능이 가장 느리다.

HashSet

용어 정의

load factor : 해시 테이블 적재율 $n / m$ m : total size of the hash table n : hash table 의 데이터 수
rehashing : 이미 저장된 요소들의 해시 코드를 다시 계산하는 프로세스

특징

HashSet 은 중복된 데이터를 처리할 때 사용하면 유용하다
순서를 보장하지 않는다

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element.
HashSet 요소 순회 성능은 HashSet 사이즈 + 버킷의 수와 비례하므로 초기 용량 설정을 너무 높게 지정하거나 load factor 를 너무 낮게 설정하면 안된다.

Iterating over this set requires time proportional to the sum of the HashSet instance's size (the number of elements) plus the "capacity" of the backing HashMap instance (the number of buckets). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.
동기화를 지원하지 않는다.

생성자

`public HashSet()`
`public HashSet(Collection<? extends E> c)`

Constructs a new set containing the elements in the specified collection. The HashMap is created with default load factor (0.75) and an initial capacity sufficient to contain the elements in the specified collection.

`public HashSet(int initialCapacity, float loadFactor)`

이 생성자를 사용하면 다른 생성자들과 달리 내부적으로 LinkedHashMap 인스턴스를 생성한다.

/**
	 * Constructs a new, empty linked hash set.  (This package private
	 * constructor is only used by LinkedHashSet.) The backing
	 * HashMap instance is a LinkedHashMap with the specified initial
	 * capacity and the specified load factor.
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

`public HashSet(int initialCapacity)`

인스턴스 멤버

HashMap<E, Object> map
```
private transient HashMap<E,Object> map;
```
HashSet 은 내부적으로 HashMap 자료구조를 사용한다.
static final Object PRESENT HashSet 은 내부적으로 HashMap을 사용한다. Key 에 요소를 저장하고 Value 는 더미 객체를 사용한다.
```
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
```

add(E e) HashMap.put 메서드는 key-value 값이 새로운 값이면 null 을 리턴하고 기존에 동일한 key 객체가 있으면 교체한 value 객체를 리턴한다. 그래서 (map.put(e, PRESENT)==null) → true 의미는 중복된 데이터가 아닌 새로운 데이터를 추가했다는 뜻이다.

/**
   * Adds the specified element to this set if it is not already present.
   * More formally, adds the specified element {@code e} to this set if
   * this set contains no element {@code e2} such that
   * {@code Objects.equals(e, e2)}.
   * If this set already contains the element, the call leaves the set
   * unchanged and returns {@code false}.
   *
   * @param e element to be added to this set
   * @return {@code true} if this set did not already contain the specified
   * element
 */
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

clone HashSet 에 재정의된 Clone()은 shallow copy를 한다.

Object.clone 을 호출해 HashSet 참조값을 복사한다.

HashSet 의 필드 HashMap 의 참조값도 복사한다.

public Object clone() {
    try {
				// 참조변수 복사
        HashSet<E> newSet = (HashSet<E>) super.clone(); // Object.clone 호출
        newSet.map = (HashMap<E, Object>) map.clone();
        return newSet;
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

Queue

!https://javagoal.com/wp-content/uploads/2019/12/6-1.png

목록형 자료구조중 요소 접근 방법에 따라 random access, sequential access 있다. !https://upload.wikimedia.org/wikipedia/commons/thumb/a/a7/Random_vs_sequential_access.svg/640px-Random_vs_sequential_access.svg.png
앞서 살펴본 ArrayList 는 index 를 사용해 random access 하게 요소에 접근한다. sequential access 방식의 목록형 자료구조 클래스는 바로 LinkedList 다. LinkedList 는 AbstractSequentialList, Deque 를 상속, 구현하고 있다.
Queue 는 FIFO (First-In-First-Out) 구조로 동작해야 하는데, LInkedList 를 사용하면 가능하다. 왜 그런지는 AbstractSequentialList, Deque 를 먼저 살펴보자.

목록의 중간에 데이터 삽입과 삭제할 때 성능에 유리하다. ArrayList는 특정 인덱스에 삭제, 삽입 후에 이후에 있는 모든 데이터를 옮겨줘하지만 LinkedList 는 앞, 뒤 노드의 참조값만 변경해주면 된다.

AbstractSequentialList

특징

Sequential Access

This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a "sequential access" data store (such as a linked list). For random access data (such as an array), AbstractList should be used in preference to this class.

리스트가 순차적 데이터 저장을 구현하도록 골격이 구현되어 있다.
Sequential Access 동작을 위해 list's list iterator 에 기반하여 get(int index), set(int index, E element), add(int index, E element) and remove(int index) 를 구현했다.

This class is the opposite of the AbstractList class in the sense that it implements the "random access" methods (get(int index), set(int index, E element), add(int index, E element) and remove(int index)) on top of the list's list iterator, instead of the other way around.

Queue

특징

Queue 를 처리하는 것과 관련된 메서드가 지정되어 있다. Queue 구조에서 삽입, 추출, 검사와 관련된 메서드가 지정되어있는데 같은 기능을 하는 메서드가 두 개씩 정의되어 있다.
Throws exception Returns special value
Insert add(e) offer(e)
Remove remove() poll()
Examine element() peek()

one throws an exception if the operation fails, the other returns a special value (either null or false, depending on the operation). The latter form of the insert operation is designed specifically for use with capacity-restricted Queue implementations; in most implementations, insert operations cannot fail.

add, remove, element 는 정의된 동작이 실패했을 경우 예외를 던지고, offer, poll, peek 는 false 또는 null 을 리턴한다. 왜 그럴까? Queue 구현체에 따라 용량에 제한이 있는 경우와 아닌 경우가 있는데 이때 다르게 사용한다.

	Throws exception	Returns special value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

Deque

특징

큐의 맨 앞과 맨 뒤의 값을 용이하게 처리하는 큐와 관련된 메서드가 지정되어있다.
목록의 맨 앞과 뒤 원소를 처리할 수 있으므로 Stack 처럼 LIFO 동작이 가능하다.

LinkedList

특징

AbstractSequentialList 와 Deque 를 상속, 구현함
doubly-linked list 로 동작한다.
동기화 지원 안한다.

생성자

링크드 리스트는 배열의 길이 지정이 필요 없으므로 생성자가 단촐하다.

`public LinkedList()`
`public LinkedList(Collection<? extends E> c)`

인스턴스 멤버

Node<E> first, Node<E> last
```
/**
 * Pointer to first node.
 */
transient Node<E> first;

/**
 * Pointer to last node.
 */
transient Node<E> last;
```
목록의 첫 번째, 마지막 노드의 참조값을 저장한다. !https://www.callicoder.com/static/ffb4ab89e6cfc7e840b8da297b169550/ea544/java-linkedlist-vs-arraylist.jpg

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

LinkedList 에 static 중첩 클래스로 선언되어 있는 Node.

이전 Node 와 다음 Node 의 참조값을 저장한다.

주요 메서드 Node 가 순차적으로 다음 Node 가르키는 관계에서 link, unlink 역할을 하는 아래 메서드로 주요 public 기능들을 구현한다.
- `private void linkFirst(E e)`
- `void linkLast(E e)`
- `void linkBefore(E e, Node<E> succ)`
- `private E unlinkFirst(Node<E> f)`
- `private E unlinkLast(Node<E> l)`
- `E unlink(Node<E> x)`

성수데브리

개발자

이전 포스트

[F-Lab 챌린지 5일차] TIL : 자바의신 22장 - List

다음 포스트

[F-Lab 챌린지 6일차] TIL : 자바의신 23장 - Set & Queue

f-lab_java

학습 목표

학습 결과 요약

학습 내용

Set

특징

Set 구현 클래스

HashSet

용어 정의

특징

생성자

인스턴스 멤버

Queue

AbstractSequentialList

특징

Queue

특징

Deque

특징

LinkedList

특징

생성자

인스턴스 멤버

[F-Lab 챌린지 5일차] TIL : 자바의신 22장 - List

[F-Lab 챌린지 7일차] TIL : 자바의신 24장 - Map

0개의 댓글