컬렉션, List, Set, Map, 검색, Stack,Queue, Synchronizaton, immodified

컬렉션

Collection 개념적: 자료구조와 관련된 플레임워크를 칭함.

Collection 소스적?: 실제로는 존재하는 인터페이스고 해당 인터페이스를 구현한 애들이 List, Set임

Map은?: 키와 값쌍을 다루기에 사용방법이 달라서 Collection에 같이 묶어서 구현하지 못했음.

Entry: 키와 값 쌍을 이룬 ... 이거 이전에 일단 Entry의 뜻은 목록의 한 항목을 의미함.

축구 엔트리도 같은 맥락임. 목록의 한 값은? element. 암튼 그럼 Entry의 정체는 객체일까? 값일까?

Entry는 Primitive Data Type으로 표현이 불가하니 당연히 class 이다. 그럼 어디에 있을까?

따로 java 파일이 있지는 않지만, interface Map.Entry 의 형태로 선언되어 있다.

Map안에 있는 항목들을 나타내는 개념으로서 Java에서는 존재하는거다.

Collection
List	Set	Map
ArrayList	HashSet	HashMap
Vector	TreeSet	HashTable
LinkedList		TreeMap
		Properties

Collection

public interface Collection<E> extends Iterable<E>
기능	메서드/필드	설명
추가	boolean add(E e)	컬렉션 제네릭 변수와 같은 타입이면 저장 추가 가능
추가	boolean addAll(Collection<? extends E> c)	컬렉션 통짜로 추가
조회	boolean contains(Object o)	해당 오브젝트 equals() true를 찾음
	boolean containsAll(Collection<?> c)	다 포함되어 있나를 찾음
	boolean isEmpty()	비어있나
	int size()	총 사이즈
삭제	void clear()	완전 클리어
	boolean remove(Object o)	하나만 제거 성공하면 트루
	boolean removeAll(Collection<?> c)	파라미터 녀석 탐색하며 전부 제거
	boolean removeIf(Predicate<? super E> filter)	함수형인터페이스 Predicate의 test를 걸러서 true가 나오게 하는 filter역할의 함수로 구현을 하면 내부적으로 true가 나온놈들을 전부 삭제해버린다.
	boolean retainAll(Collection<?> c)	교집합을 구한다.
기타	Iterator<E> iterator()	반복자를 반환하는 매서드 내부적으로 무엇을 기준으로 줄이 세워질지는 컬렉션에서 설명할건 아니다.
	default Stream<E> parallelStream()	스트림을 생성함. 그런데 싱크로나이즈가 적용되어 스레드 작업의 결과를 보장하는
	default Spliterator<E> spliterator()	스플리테이터를 생성하는 함수
	default Stream<E> stream	스트림을 생성함. 스트림 설명은 다음에... 일단 데이터 통로를 하나 만드는데 거기엔 데이터들이 순서에 맞게 줄서 있다 라고 생각 그런걸 만드는 함수
	Object[] toArray()	크기가 정해져있는 딱딱한 배열의 형태를 생성
	<T> T[] toArray(T[] a)	특정 오브젝트 타입의 배열을 생성 보면 클래스에 아니 인터페이스에서 미리 사전에 약속한 제네릭이 아니라 자체적으로 다른 제네릭을 사용하는걸 알 수 있음.

Predicate

영어뜻=서술하다, 서술어

실제 구현: 인터페이스임.함수형 인터페이스임. 역할은 오브젝트가 들어갈때 그것이 같은지 다른지를 불리언값을 리턴하는 로직들을 가지고있는 인터페이스임.

함수형 인터페이스

추상메서드를 하나만 가지고 있음.

함수형 인터페이스를 매개변수로 가지고 있는 어떠한 매서드를 사용하려면 당연히 매개변수에 함수형 인터페이스를 구현한 객체를 넣어야겠지. 그런데 한수형 인터페이스는 어차피 구현해야되는 매서드는 단 한개 뿐이기에 담과 같은 람다식의 적용을 받을 수 있음.

//함수형 인터페이스 정의
@FunctionalInterface
public interface Converter<T, R> {
    // T: 입력 타입, R: 반환 타입 
    //이게 우리가 인터페이스 사용할때 구현해야될 추상 매서드
    //함수형 인터페이스라면 반드시 하나가 존재한다.
    R convert(T t);
    
    // 디폴트는 추상이 아니기에 그냥 존재해도 상관 없다.
    default void printInputType(T t) {
        System.out.println("입력 타입: " + t.getClass().getSimpleName());
    }
}

//함수형 인터페이스를 활용하는 클래스
public class DataProcessor<T, R> {
    private T data;
    
    public DataProcessor(T data) {
        this.data = data;
    }
    
    // 함수형 인터페이스를 매개변수로 받는 메소드
    public R processData(Converter<T, R> converter) {
        if (converter == null || data == null) {
            return null;
        }
        
       //뭐 이런식으로 클래스에서 함수형 인터페이스를 받았어 그래
       //이상 없이 잘 받으면 뭘 하고 싶은데? 를 여기에 구현해야함.
       //추상매서는 별개임. 추상매서드는 다음단계 현재 이 클래스의 매서드를
       //호출하는 스레드 쪽에서 추상매서드를 구현해야하고,
       //여기는 그런 추상매서드가 구현될거라는걸 가정하고 올바른 로직을 짜야함.
       
        // 데이터 처리 전 타입 정보 출력
        converter.printInputType(data);
        // 실제 데이터 변환 처리
        return converter.convert(data);
    }
}

//진짜 중요한 시작
public class FunctionalInterfaceExample {
    public static void main(String[] args) {
        //클래스 하나 생성
        DataProcessor<String, Integer> stringProcessor = 
            new DataProcessor<>("123");
            
        //익명클래스 방식으로 함수형인터페이스를 넣어줄거야.
        Integer result1 = stringProcessor.processData(
            new Converter<String, Integer>() {
                @Override
                public Integer convert(String str) {
                //컨버터의 동작 구현. 스트링을 인트로 변환시키는걸 구현했네
                    return Integer.parseInt(str);
                }
            }
        );
        System.out.println("익명 클래스 결과: " + result1);
        // 출력결과:
        // 입력 타입: String
        // 익명 클래스 결과: 123
        
        //람다식 방식으로 함수형 인터페이스 매개변수를 구현할거야.
        //이게 자바 웹개발자들 트렌드라고 하네요... 숏코딩이긴하네..
        Integer result2 = stringProcessor.processData(
            str -> Integer.parseInt(str)
        );
        System.out.println("람다식 결과: " + result2);
        // 출력결과:
        // 입력 타입: String
        // 람다식 결과: 123
        
        //메소드 참조 방식으로 함수형 인터페이스를 구현할거야인데..
        //이건 람다식의 한 종류임. 람다식의 메소드 참조 기법을 사용한건데
        //아래의 2개 코드는 동일한 코드이다. 프로세스데이타의 추상매서드인 
        //convert의 매개변수와 반환값이 일치할경우 이런식으로 또 줄여버린다..
        
        //Integer result3 = stringProcessor.processData( (x) -> Integer.parseInt(x) );
        Integer result3 = stringProcessor.processData(Integer::parseInt);
        System.out.println("메소드 참조 결과: " + result3);
        // 출력결과:
        // 입력 타입: String
        // 메소드 참조 결과: 123

        // 예제 2: Integer to String 변환
        DataProcessor<Integer, String> intProcessor = 
            new DataProcessor<>(456);
        
        String result4 = intProcessor.processData(num -> 
            String.format("숫자: %d", num)
        );
        System.out.println("Integer to String 결과: " + result4);
        // 출력결과:
        // 입력 타입: Integer
        // Integer to String 결과: 숫자: 456

        // 예제 3: List<String> to Integer 변환
        List<String> stringList = Arrays.asList("A", "B", "C");
        DataProcessor<List<String>, Integer> listProcessor = 
            new DataProcessor<>(stringList);
        
        Integer result5 = listProcessor.processData(list -> 
            list.stream()
                .mapToInt(String::length)
                .sum()
        );
        System.out.println("List 처리 결과: " + result5);
        // 출력결과:
        // 입력 타입: ArrayList
        // List 처리 결과: 3  // A, B, C 각각의 길이(1)의 합
    }
}

Splitator

split + iterator : 반복자 자료구조인데 나누는게 되는 반복자임. 이게 나누는게 된다는게 중요한 점은. 병렬 프로그래밍 때문이다.

병렬 프로세스에서 일반 반복자 호출시에 싱크로나이즈가 보장되지 않으면 처리가 겹치면서 의도치 않은 결과를 가져가게 되는 현상이 발생하는데 스레드의 개수만큼 충분히 나눌수 있는 스플리테이터를 사용하게 되면 병렬 프로세스를 처리할 수 있다는 원리

List 컬렉션:

Interface List<E>

Collection 인터페이스를 상속한 동적 크기 배열 개념

배열 자료구조 그 이상의 기능을 제공하면서 크기를 동적으로 할당가능하고, 교환 정렬 등 함수들도 구현되어 있음

개념이라고 칭하는건 여기엔 List 컬렉션엔 여러 종류가 있기 때문

ArrayList: 가장 단순한 배열 개념과 유사

Vector: 동기화된 매서드 및 필드를 보장하는 자료구조임.

LinkedList: 연결리스트 자료구조이다. 배열과 동일한 매서드를 사용하지만 순서개념이 실제 메모리의 순서랑 달리 주소를 일일히 참조하는 형태이기에 그 주소만 바꾸면 된다. 즉 교환 추가 삭제가 아주 자유롭고 빠르면서 실제 정렬 순서를 보장하는

List 인터페이스에서 추가로 구현해야되는 함수들

Collection에는 없는 개념인 index 개념이 매서드에 추가되어진게 대부분이다.

public interface List<E> extends Collection<E>
기능	메서드/필드	설명
수정	void add(int index, E element)	첫번째 인자인 인덱스에 두 번째 인자인 요소를 추가한다.
	boolean addAll(int index, Collection c)	지정된 위치에 컬렉션의 모든 요소를 삽입하는 메서드
	E set(int index, E element)	지정된 위치의 요소를 새로운 요소로 대체하는 메서드
	void replaceAll(UnaryOperator<E> operator)	리스트의 모든 요소를 주어진 연산자를 적용한 결과로 대체하는 메서드
조회	E get(int index)	지정된 위치의 요소를 반환하는 메서드
	int indexOf(Object o)	요소의 첫 번째 등장 위치를 반환하는 메서드. 없으면 -1 반환
	int lastIndexOf(Object o)	요소의 마지막 등장 위치를 반환하는 메서드. 없으면 -1 반환
	List subList(int fromIndex, int toIndex)	리스트의 지정된 범위의 뷰를 반환하는 메서드. 원본은 멀쩡
삭제	E remove(int index)	지정된 위치의 요소를 제거하고 그 요소를 반환하는 메서드
기타	ListIterator<E> listIterator()	List 순회를 위한 ListIterator를 반환하는 메서드
	ListIterator<E> listIterator(int index)	지정된 위치부터 순회할 수 있는 ListIterator를 반환하는 메서드
	void sort(Comparator<? super E> c)	주어진 Comparator를 사용하여 리스트를 정렬하는 메서드

UnaryOperator

Unary: 단항

Operator: 연산자

UnaryOperator: 단항 연산자

실제 구현은 함수형 인터페이스로 단일 추상메서드인 identity() 메서드를 보유하고 있다. 우리는 replaceAll에 identity()매서드를 구현한 람다식을 인자로 넣어주는게 일반적이겠지. 그게 자바가 의도한 클린 코드방식이니까

단항연산자라고 실제 +1 ==2 뭐 이런거 넣는게 아니다. 실제로 리스트를 순차적으로 반복하면서 해당 값을 만날때 무슨 동작을 할지를 구현해주는거다.

static <T> UnaryOperator<T>

identity()

inputValueType == returnValueType 은 보장되어야 한다.

Iterator

Collection Interface에서 부터 이미 존재하던 녀석임. Collection Interface는 extends Iterable<E> 이기에 Iterator 클래스를 만드는 iterator() 매서드를 구현해야한다.

그래서 이 클래스의 역할은? 자료구조의 내부를 어떻게 탐색하면 되는지 그 순서를 제공하는 클래스라고 한다. 무서운건 완전히 독립된게 아니라. 특히 추가는 없으면서 삭제는 가능하다는 점이다. 다음에 올 녀석을 삭제해버리는 어마무시한 매서드를 통해 실제 삭제를 시킨다.

Modifier and TypeMethod and Description

default void	forEachRemaining(Consumer<? super E> action) Performs the given action for each remaining element until all elements have been processed or the action throws an exception. -> replaceAll처럼 내부 전체를 돌면서 구현한 동작을 처리함
boolean	hasNext() Returns true if the iteration has more elements. -> 반복문 안의 조건문으로 주로 사용
E	next() Returns the next element in the iteration. -> 일반적으로 탐색하는 이유
default void	remove() Removes from the underlying collection the last element returned by this iterator (optional operation). -> 예외적으로 얘는 있으면 안됨의 조건에 해당하면 호출할듯

public interface Consumer<T> //역시 이 자식도 함수형 인터페이스
void accept(T t) // 이 함수를 람다식으로 구현하면 된다.

ListIterator

Iterator를 상속하는 녀석 특히 '인덱스' 개념이 추가되어진 'List' 인터페이스에서 특수하게 구현하는 녀석이다.

일반 반복자와 차이

1. 기존에 단방향인 넥스트가 리스트 아이터레이터에서는 넥스트 프리비어스 양방향이 존재한다.

-> 인덱스 때문에 추가된 개념

-> 만약 순서가 보장되지 않는 인덱스가 존재하지 않는 자료구조인 Map이나 set에 양방향을 구현하려면 너무 빡세지기 때문에 next() remove()만 존재하는 일반반복자와 확장된 리스트반복자 2개를 따로 만들어 둔거다.

2. 기존에 삭제를 제외하면 수정하는 부분은 거의 없던 개념을 넘어서 추가도 존재하는 녀석이다.

->양방향이 존재하기에 가능한 개념이다.

->이전 이후 개념이 확실하고 간단하다. -> 수정 삭제 등을 수행했을때 반복자의 핵심인 순서 보장이 간단하다.

Modifier and TypeMethod and Description

void	add(E e) Inserts the specified element into the list (optional operation).
boolean	hasNext() Returns true if this list iterator has more elements when traversing the list in the forward direction.
boolean	hasPrevious() Returns true if this list iterator has more elements when traversing the list in the reverse direction.
E	next() Returns the next element in the list and advances the cursor position.
int	nextIndex() Returns the index of the element that would be returned by a subsequent call to next().
E	previous() Returns the previous element in the list and moves the cursor position backwards.
int	previousIndex() Returns the index of the element that would be returned by a subsequent call to previous().
void	remove() Removes from the list the last element that was returned by next() or previous() (optional operation).
void	set(E e) Replaces the last element returned by next() or previous() with the specified element (optional operation).

여기서 애매하게 하고 넘어가면 안되는 개념들이 3개 존재한다고 생각함.

1. Cursor

현재 인덱스 같은 개념이다. 그런데 이걸 인덱스라고 표현을 안한다. 인덱스는 진짜 해당 엘리먼트가 존재하는 그 위치를 딱 찝는 개념이면. cursor는 바로 그 직전이라고 한다. 숫자적으로 정확한 구현은 다음과 같다.

A= [0,1,2,3]

인덱스는 총 0 1 2 3 인덱스 총 4개가 존재하고

커서는 0 1 2 3 4 총 5개가 존재하며 첫번째 인덱스 앞에 그리고 마지막 인덱스 뒤에 해서 한 개가 항상 더 많은 구조

이렇게 하는 이유는 아직 그 철할까지 내가 받아들이기는 힘들지만, 반복자의 의미인 순차 탐색에 적합한 개념구조라고 한다.. current value가 아니라 항시 next() previous()로 값을 탐색하는 특징에 적합하다고 한다..

next() 이전에 current cursor가 마지막 cursor이면 끝이고

previous() 이전에 current cursor가 첫번째 cursor이면 끝이다.

그래서 처음에 ListIterator를 어떻게 생성하냐가 중요한

listIterator(): cursor가 0에서 시작

listIterator(int index): 지정된 위치에서 cursor 시작 -> listIterator(alist.size()): cursor가 끝으로 지정되어 있음.

2. void add(E e) : 그래서 어디에 추가된다는건데????

아무 설명 없이 넘어가면 그냥 끝에 추가되나보다 하고 넘어가는데 그게 아니다. 현재 cursor 바로 그 위치에 추가되고 cursor는 ++가 된다.

A=[0, 1, 2]이고 cursor는 1인 상태라면 next()의 결과는 1인 상황. 이때 add(4)하면

A=[0, 4, 1, 2]가 되고 cursor는 2가 되고 next()의 결과는 1을 보장하게 된다.

왜냐고 물어봤다. 구글 + AI 그런데 결론은 이게 반복자 개념의 철학이라고 한다...

3. void set(E e): 뭘 어떻게 수정한다는건데?

A=[0, 1, 2] cursor=0 lastRet=-1 이건 쌩 초기 상태이다. lastRet은 가장 최근에 리턴받은 인덱스 참조값이다. 여기서 next()호출
A=[0, 1, 2] cursor=1 lastRet=0 next()==0 여기서 한번 더 next()호출

A=[0, 1, 2] cursor=2 lastRet=1 next()==1 여기서 이제 set(5) 호출하면 어떻게 변하는냐?

A=[0, 5, 2] cursor=2 lastRet=1 즉 lastRet을 기억하고 있다가 해당 인덱스로 가서 값을 바꿔치기 하는게 set() 매서드

Comparator

함수형 인터페이스이다. Compare 함수를 구현해서 사용하면 된다. 당연 람다식으로

int compare(T o1, T o2)

o1 - o2 로 생각한다. o1이 더 작으면 음수 반환, 같은면 0, 더 크면 양수 반환

이렇게 되게 구현하면 오름차순으로 정렬되게 된다.

당연히 반대면 내림차순으로 정렬되게 됨.

ArrayList

가장 기본적인 리스트 그자체라고 생각 속도도 빠르고 메모리 용량도 최적화가 잘되어 있다는게 장점일 듯 안그러면 쓸 이유가 거의 없을거 같아 <- 이건 추측에 기반

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

List에는 없는 ArrayList에서 구현된 특수 매서드들
매서드	설명
Object clone()	깊은 복사 XXX 얕은 복사로 만들어진 참조 리스트를 반환
void ensureCapacity(int minCapacity)	minCapacity값으로 ArrayList의 메모리 용량을 확보함. 주로 대용량 데이터를 추가하는 등의 작업이 예상되면 성능 최적화로 사용
protected void removeRange(int fromIndex, int toIndex)	지정된 범위만큼 요소들을 삭제하고 다시 ArrayList 조정
void trimToSize()	ArrayList의 메모리용량을 현재에 맞게 딱 줄이는 메서드. 추가 삭제 등의 작업이 없을거 같을때 메모리 용량 최적화로 사용

Vector

ArrayList와 사용방법은 거진 완벽히 동일하나 모든 필드 및 매서드가 synchronized화 되어있어서 멀티 스레딩 작업때 유용한 자료구조. 이거 사용하는게 좋겠네

LinkedList

이것도 ArrayList와 사용방법이 거진 완벽히 동일하나 내부 자료 관리 방식이 다른 형태이다. 메모리 용량을 많이 먹지만, 수정 삭제 등의 작업에서 압도적인 성능을 보임.

Set Interface

수학에서 집합 생각하면 됨. public interface set<E> extends Collection<E>

컬렉션 인터페이스에서 구현된 매서드 외에 특별하게 set에서 따로 선언된건 없어보임. 그저 Collection의 매서드들을 '집합' 개념을 따르게 구현해주면 됨. 모든 엘리먼트는 중복될 수 없다. 들어간 순서를 따로 보장하지 않는다. 해당 인터페이스를 구현한 자료구조는 HashSet, LinkedHashSet, TreeSet 등이 있다.

Abstract Set

모든 Set 구현체의 뼈대 토대를 다지는 클래스이다.

public abstract class AbstractSet<E>
extends AbstractCollection<E>
implements Set<E>

Modifier and TypeMethod and Description

boolean	equals(Object o) Compares the specified object with this set for equality.
int	hashCode() Returns the hash code value for this set.
boolean	removeAll(Collection<?> c) Removes from this set all of its elements that are contained in the specified collection (optional operation).

Methods inherited from class java.util.AbstractCollection add, addAll, clear, contains, containsAll, isEmpty, iterator, remove, retainAll, size, toArray, toArray, toString

HashSet

Set도 결국 메모리에 저장되는 자료구조이다. 이를 어떻게 관리할지에대한 개념에서 HashTable 개념을 사용하기에 HashSet이다.

매서드 자체는 독특할게 없다. 즉 Collection에서 사용하는 그 매서드 그대로 쓴다. index 개념이 추가되지 않았기 때문 (그런데 실제로는 있지만 그게 여기서 사용할정도로 뭔가 의미가 있는게 아니다. 그저 메모리상 인덱스인거...)

하지만, 생성자는 독특한게 있다.

ConstructorsConstructor and Description

HashSet()

Constructs a new, empty set; the backing HashMap instance has default initial capacity (16) and load factor (0.75).

HashSet(Collection<? extends E> c)

Constructs a new set containing the elements in the specified collection.

HashSet(int initialCapacity)

Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and default load factor (0.75).

HashSet(int initialCapacity, float loadFactor)

Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and the specified load factor.

새로운개념!! int initialCapacity 와 float loadFactor

그런데 이 부분은 이미 디폴트 값이 있다. 왜냐하면 HashSet() 이미 있자나...그래서 그냥 기본값 쓰면된다.

되지만, 내부적으로 왜 initialCapacity와 loadFactor가 있는가를 설명하려면... HashTable을 가져와야 함.

번외 HashTable

public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, Serializable

이 클래스는 키를 값에 매핑하는 해시 테이블을 구현합니다.

해시 테이블에서 객체를 성공적으로 저장하고 검색하려면 키로 사용되는 객체가 메서드 hashCode 와 equals메서드를 구현해야 합니다.

인스턴스에는 Hashtable성능에 영향을 미치는 두 가지 매개변수가 있습니다 . 초기 용량 과 부하 계수입니다 . 용량 은 해시 테이블의 버킷 수 이고 초기 용량 은 해시 테이블이 생성될 당시의 용량입니다. 해시 테이블이 열려 있다는 점에 유의하세요 . "해시 충돌"의 경우 단일 버킷에 여러 항목이 저장되며, 이는 순차적으로 검색해야 합니다. 부하 계수는 해시 테이블의 용량이 자동으로 늘어나기 전에 얼마나 가득 찰 수 있는지를 측정하는 것입니다.

initialCapacity는 즉 생성된 직후 버킷 수를 의미함.

해시 충돌이란 key의 HashCode()를 버킷의 값으로 반환하는 과정에서 같은 버킷의 값이 나올경우를 의미

ex) initalCapacity==16 이라 hashCode()%16==0 인 key가 2개라면 버킷 0값이 충돌되는 경우가 발생.

"해시충돌"의 경우엔 단일 버킷에 여러 항목이 저장된다. 그리고 이는 순차적으로 검색되기 위해 즉 순서가 차례대로 저장된다는 뜻.

부하계수는 일반적으로 0.75 인데 이 의미는 해시테이블에 저장된 총 데이터 개수/ 버킷의 개수 이다. loadFactor값은 0.75가 넘어갈때 버킷의 개수를 증가 시켜 또 데이터를 받을 수 있는 상태를 만든다. 이게 왜 이런거냐면 총 16개의 버킷인데 하나의 버킷에만 16*0.75=12개가 집중 부하된다면 데이터 조회할때마다 순차적으로 하나만 총 12개를 조회때리니까 성능이 낮아진다. 그래서 100프로가 아니라 0.75로 지정했다고 한다. 0.25 이런식으로 낮아지게 되면 버킷의 개수가 압도적으로 너무 데이터 대비 많아지니까 메모리 용량을 기하급수적으로 잡아먹게 된다. 거의 3배 잡아먹으니까.. 그래서 합의 점이 0.75라는거 같다.
그럼 애초에 initalCapacity를 실제 메모리 데이터 개수*0.75 = 데이터개수 -> x = 데이터개수*100/75 -> 따라서 그냥 1.4배로 줘버리면 되는거 아닌가? 라는데 음 잘 모르면 건들지마시오!! 하지만, 난 할게요.

LinkedHashSet 와 TreeSet

위에 HashSet의 사례는 데이터를 저장할때 내부적으로 HashTable을 사용한다고 했는데 사실은 HashMap을 사용한다. LinkedHashSet과 TreeSet도 마찬가지로 저장을 LinkedHashMap과 TreeMap을 사용하는 set이다.

set이란 개념과는 별개로 컴퓨터 내부적으로는 key==value인 Map 개념을 사용하는것과 다르지 않다는 의미.

Differences Between HashSet, LinkedHashSet, and TreeSet:

FeaturesHashSetLinkedHashSetTreeSet

Internal Working	HashSet internally uses HashMap for storing objects	LinkedHashSet uses LinkedHashMap internally to store objects	TreeSet uses TreeMap internally to store objects
When To Use	If you don’t want to maintain insertion order but want to store unique objects	If you want to maintain the insertion order of elements then you can use LinkedHashSet	If you want to sort the elements according to some Comparator then use TreeSet
Order	HashSet does not maintain insertion order	LinkedHashSet maintains the insertion order of objects	While TreeSet orders the elements according to supplied Comparator. By default, objects will be placed according to their natural ascending order.
Complexity of Operations	HashSet gives O(1) complexity for insertion, removing, and retrieving objects	LinkedHashSet gives insertion, removing, and retrieving operations performance in order O(1).	While TreeSet gives the performance of order O(log(n)) for insertion, removing, and retrieving operations.
Performance	The performance of HashSet is better when compared to LinkedHashSet and TreeSet.	The performance of LinkedHashSet is slower than TreeSet. It is almost similar to HashSet but slower because LinkedHashSet internally maintains LinkedList to maintain the insertion order of elements	TreeSet performance is better than LinkedHashSet except for insertion and removal operations because it has to sort the elements after each insertion and removal operation.
Compare	HashSet uses equals() and hashCode() methods to compare the objects	LinkedHashSet uses equals() and hashCode() methods to compare it’s objects	TreeSet uses compare() and compareTo() methods to compare the objects
Null Elements	HashSet allows only one null value.	LinkedHashSet allows only one null value.	TreeSet does not permit null value. If you insert null value into TreeSet, it will throw NullPointerException.
Syntax	HashSet obj = new HashSet();	LinkedHashSet obj = new LinkedHashSet();	TreeSet obj = new TreeSet();

Map Interface

public interface Map<K, V>

Collection 인터페이스랑 완전 별개의 개념. 정리하지만 Collection은 Set과 List를 위한 개념이고 특히 List는 추가로 인터페이스에서 인덱스와 관련된 선언들이 굉장히 많았고, Set은 Collection을 구현하는거 만으로 충분했지만, 내부적으로는 Map 자료구조가 필요했었다.

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

-> 키는 중복될 수 없다.

This interface takes the place of the Dictionary class, which was a totally abstract class rather than an interface.

-> 과거에는 딕셔너리 추상클래스를 사용하였던거 같다. 이거를 상속받은게 hashtable인데 이거 문서를 봐도 좀 족보가 꼬였다. 꼬였는데 풀지 않는건 과거 소스를 최신 SDK로 돌리더라도 정상 작동하는게 자바의 철학이라 그런거 같다.

The Map interface provides three collection views, which allow a map's contents to be viewed as a set of keys, collection of values, or set of key-value mappings. The order of a map is defined as the order in which the iterators on the map's collection views return their elements. Some map implementations, like the TreeMap class, make specific guarantees as to their order; others, like the HashMap class, do not.

-> TreeMap은 순서가 있고 정렬이 가능하지만, HashMap은 불가능하다는 내용

(중략)

Many methods in Collections Framework interfaces are defined in terms of the equals method. For example, the specification for the containsKey(Object key) method says: "returns true if and only if this map contains a mapping for a key k such that (key==null ? k==null : key.equals(k))." This specification should not be construed to imply that invoking Map.containsKey with a non-null argument key will cause key.equals(k) to be invoked for any key k. Implementations are free to implement optimizations whereby the equals invocation is avoided, for example, by first comparing the hash codes of the two keys. (The Object.hashCode() specification guarantees that two objects with unequal hash codes cannot be equal.) More generally, implementations of the various Collections Framework interfaces are free to take advantage of the specified behavior of underlying Object methods wherever the implementor deems it appropriate.

-> contains 관련 함수를 사용할때 결국 equals() 매서드가 호출 될 수 밖에 없는데 해당 내용 최적화에 신경 써야 한다는 내용으로 이해함. 반드시 equals()란 연산으로 때리면 안되고, null 체크 가능성 없는 예외 체크 등등 빠르게 처리할 수 있는 코드로 전처리

중첩된 클래스 요약중첩된 클래스수정자 및 유형인터페이스 및 설명

static interface

Map.Entry<K,V>

맵 항목(키-값 쌍).

void	clear() 이 맵에서 모든 매핑을 제거합니다(선택적 작업).
default V	compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 지정된 키와 현재 매핑된 값(또는 null현재 매핑이 없는 경우)에 대한 매핑을 계산하려고 시도합니다.
default V	computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction) 지정된 키가 아직 값과 연결되지 않았거나 에 매핑된 경우 null, 제공된 매핑 함수를 사용하여 해당 값을 계산하고 이 맵에 입력합니다.
default V	computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 지정된 키에 대한 값이 존재하고 null이 아닌 경우, 키와 현재 매핑된 값을 고려하여 새 매핑을 계산하려고 시도합니다.
boolean	containsKey(Object key) 지정된 키에 대한 매핑이 이 맵에 포함되어 있는 경우 true를 반환합니다 .
boolean	containsValue(Object value) 이 맵이 하나 이상의 키를 지정된 값에 매핑하는 경우 true를 반환합니다 .
Set<Map.Entry<K,V>>	entrySet() Set이 맵에 포함된 매핑의 뷰를 반환합니다. 뷰는 수정을 해도 원본에 영향을 주지 않아요.
boolean	equals(Object o) 지정된 객체와 이 맵을 비교하여 동일한지 확인합니다.
default void	forEach(BiConsumer<? super K,? super V> action) 이 맵의 각 항목에 대해 지정된 동작을 모든 항목이 처리되거나 동작에서 예외가 발생할 때까지 수행합니다.
V	get(Object key) 지정된 키가 매핑된 값을 반환하거나, null이 맵에 키에 대한 매핑이 없는 경우 해당 값을 반환합니다.
default V	getOrDefault(Object key, V defaultValue) 지정된 키가 매핑된 값을 반환하거나, defaultValue이 맵에 키에 대한 매핑이 없는 경우 해당 값을 반환합니다.
int	hashCode() 이 맵의 해시 코드 값을 반환합니다.
boolean	isEmpty() 이 맵에 키-값 매핑이 포함되어 있지 않으면 true를 반환합니다 .
Set<K>	keySet() Set이 맵에 포함된 키의 뷰를 반환합니다 .
default V	merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction) 지정된 키가 아직 값과 연관되어 있지 않거나 null과 연관되어 있는 경우, 해당 키를 주어진 null이 아닌 값과 연관시킵니다.
V	put(K key, V value) 지정된 값을 이 맵의 지정된 키와 연결합니다(선택적 작업).
void	putAll(Map<? extends K,? extends V> m) 지정된 맵의 모든 매핑을 이 맵으로 복사합니다(선택 작업).
default V	putIfAbsent(K key, V value) 지정된 키가 아직 값과 연결되지 않았거나 값에 매핑되어 있는 경우 null해당 키를 주어진 값과 연결하여 을 반환하고 null, 그렇지 않으면 현재 값을 반환합니다.
V	remove(Object key) 이 맵에서 키에 대한 매핑이 있으면 이를 제거합니다(선택적 작업).
default boolean	remove(Object key, Object value) 지정된 값에 현재 매핑되어 있는 경우에만 지정된 키에 대한 항목을 제거합니다.
default V	replace(K key, V value) 지정된 키에 대한 항목이 현재 어떤 값에 매핑되어 있는 경우에만 해당 항목을 바꿉니다.
default boolean	replace(K key, V oldValue, V newValue) 현재 지정된 값에 매핑되어 있는 경우에만 지정된 키의 항목을 바꿉니다.
default void	replaceAll(BiFunction<? super K,? super V,? extends V> function) 모든 항목이 처리되거나 함수에서 예외가 발생할 때까지 해당 항목에 대해 주어진 함수를 호출한 결과로 각 항목의 값을 바꿉니다.
int	size() 이 맵에서 키-값 매핑의 수를 반환합니다.
Collection<V>	values() Collection이 맵에 포함된 값의 뷰를 반환합니다 .

public interface BiFunction<T, U, R>

함수형 인터페이스이다. 추상 매서드: R apply(T t, U, u)

의미: 2개의 인자를 받아 결과 값을 토해내는 매서드를 구현한다. 여러 유사한 함수형 인터페이스와의 차이점은 제네릭을 총 3개를 사용하는 만큼 인자와 반환 자료형에 제한을 따로 주고 있지 않다는 것.

Map.forEach(BiConsumer<? super K, ? super V> action)

기존 Iteratable의 forEach() 매서드와 사뭇 다르다

void forEach(Consumer<? super T> action)

Consumer는 역시 함수형 인터페이스로 반환값이 없는 void accept(T t)를 구현해야한다. 인자 하나에 대해 어떤 액션을 취하고자 할때 사용

BiConsumer도 함수형 인터페이스이다. 반환값이 없는 void accept(T t, U u)를 구현해야함. 인자 2개에 대해 액션을 취하고자 할때 사용

forEach의 내부 구현은 인자 액션을 가지고 Map의 모든 EntryElement에 적용하여 동작을 구현하는것이다. 예를들어 forEach((k, v)-> Sysout.println(k +"=" + v)); 이런식의 구현도 가능할 것이다.

HashMap / TreeMap / LinkedHashMap

Iteration Order	no guaranteed order, will remain constant over time	sorted according to the natural ordering	insertion-order
Get / put / remove / containsKey	O(1)	O(log(n))	O(1)
Interfaces	Map	NavigableMap, Map, SortedMap	Map
Null values/keys	allowed	only values	allowed
Fail-fast behavior	Fail-fast behavior of an iterator cannot be guaranteed, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification	Fail-fast behavior of an iterator cannot be guaranteed, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification	Fail-fast behavior of an iterator cannot be guaranteed, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification
Implementation	buckets	Red-Black Tree	double-linked buckets
Is synchronized	implementation is not synchronized	implementation is not synchronized	implementation is not synchronized

Fail-fast behavior

시스템 설계 에서 fail-fast 시스템은 장애 를 나타낼 가능성이 있는 모든 조건을 인터페이스에서 즉시 보고하는 시스템입니다. fail-fast 시스템은 일반적으로 결함이 있는 프로세스를 계속 진행하려고 시도하는 대신 정상적인 작동을 중단하도록 설계되었습니다. - Wiki -

Map 인터페이스를 상속받은 위 3마리들은 전부 Fail-Fast 동작을 보장한다. 반복자를 사용하는 경우에 말이다.

특히 반복자를 사용하는 함수에서 Map.remove()를 하게되면 논리적 결함이 없더라도, 의도 자체가 잘못되었다 판단하고 정상 동작도 바로 에러가 떠버리게 된다.

fail-fast를 구현하기 위해 내부적으로 반복자는 카운팅 계수가 존재한다. 만약 반복자 안에 있는 매서드로 수정을 시도하여 카운팅 계수를 증가시키면서 Map의 계수도 증가시키는게 아니라, Map 자체의 함수로 수정하여 계수를 증가시켰는데 내부 반복자의 계수와 다르다?? 바로 fail-fast 동작해버리는 원리로 이런 시스템을 구현함.

암튼 이런 시스템은 Gradle이나 Compiler등 다양한 분야에서 사용되어 삽질을 막아준다.

Is synchronized

HashTable이란 클래스가 있다. 이는 Dictionary를 상속받은 녀석이라고했는데 이 자식은 이제 더 이상 업데이트 안될거다.

Map map = Collections.synchronizedMap(여기에 맵 인스턴스); 이런식으로 처리해버리면 된다..

혹은 ConcurrentMap 의 형태로 애초부터 할당 하는 것도 방법이다. 멀티스레딩을 지원하는 문법이 다양해졌다.

Red-Black Tree

트리 관련 자료구조는 여러개가 있는데 이중에 Red-Black은 나름 빨강-검정 0 or 1 과 유사한 개념과 함수 구현이 가능한 규칙들을 추가하여 항상 최선은 아니지만, 값이 들어올때마다 규칙적으로 리스트럭쳐를 통해 탐색 효율성을 증가시키기위한 자료구조임.

LIFO : FIFO = Stack : Queue

Stack Class

public class Stack<E> extends Vector<E>

boolean	empty() Tests if this stack is empty.
E	peek() Looks at the object at the top of this stack without removing it from the stack.
E	pop() Removes the object at the top of this stack and returns that object as the value of this function.
E	push(E item) Pushes an item onto the top of this stack.
int	search(Object o) Returns the 1-based position where an object is on this stack.

Methods inherited from class java.util.Vector add, add, addAll, addAll, addElement, capacity, clear, clone, contains, containsAll, copyInto, elementAt, elements, ensureCapacity, equals, firstElement, forEach, get, hashCode, indexOf, indexOf, insertElementAt, isEmpty, iterator, lastElement, lastIndexOf, lastIndexOf, listIterator, listIterator, remove, remove, removeAll, removeAllElements, removeElement, removeElementAt, removeIf, removeRange, replaceAll, retainAll, set, setElementAt, setSize, size, sort, spliterator, subList, toArray, toArray, toString, trimToSize

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:

Deque<Integer> stack = new ArrayDeque<Integer>();

Deque 인터페이스를 추천하고 있는 자바... 아우...

Deque Interface : 구현체들ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList

public interface Deque<E>
extends Queue<E>

A linear collection that supports element insertion and removal at both ends. The name deque is short for "double ended queue" and is usually pronounced "deck". Most Deque implementations place no fixed limits on the number of elements they may contain, but this interface supports capacity-restricted deques as well as those with no fixed size limit.

This interface defines methods to access the elements at both ends of the deque. Methods are provided to insert, remove, and examine the element. Each of these methods exists in two forms: 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 Deque implementations; in most implementations, insert operations cannot fail.

The twelve methods described above are summarized in the following table:

-> 요약: 데크 인터페이스는 좀 더 확장된 매서드를 제공할 수 있다. 양면에서 사용가능하며 스택의 역할도 큐의 역할도 가능하다. 이름은 stack이라 이름짓고 Deque 구현체 할당해버리거나, queue라 이름 짓고 Deque 구현체 할당해버리면 다양한 양면으로 사용가능한게 장점이라고 한다...

Summary of Deque methods

	First Element (Head)		Last Element (Tail)
	Throws exception	Special value	Throws exception	Special value
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

This interface extends the Queue interface. When a deque is used as a queue, FIFO (First-In-First-Out) behavior results. Elements are added at the end of the deque and removed from the beginning. The methods inherited from the Queue interface are precisely equivalent to Deque methods as indicated in the following table:

Comparison of Queue and Deque methods

Queue Method	Equivalent Deque Method
add(e)	addLast(e)
offer(e)	offerLast(e)
remove()	removeFirst()
poll()	pollFirst()
element()	getFirst()
peek()	peekFirst()

Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class. When a deque is used as a stack, elements are pushed and popped from the beginning of the deque. Stack methods are precisely equivalent to Deque methods as indicated in the table below:

Comparison of Stack and Deque methods

Stack Method	Equivalent Deque Method
push(e)	addFirst(e)
pop()	removeFirst()
peek()	peekFirst()

Note that the peek method works equally well when a deque is used as a queue or a stack; in either case, elements are drawn from the beginning of the deque.

This interface provides two methods to remove interior elements, removeFirstOccurrence and removeLastOccurrence.

Unlike the List interface, this interface does not provide support for indexed access to elements.

-> 리스트랑은 다르다고 한다. Deque로 감싼 순간 인덱스 개념을 허용하지 않으니까

While Deque implementations are not strictly required to prohibit the insertion of null elements, they are strongly encouraged to do so. Users of any Deque implementations that do allow null elements are strongly encouraged not to take advantage of the ability to insert nulls. This is so because null is used as a special return value by various methods to indicated that the deque is empty.

Deque implementations generally do not define element-based versions of the equals and hashCode methods, but instead inherit the identity-based versions from class Object.

Queue Interface: 구현체 LinkedList, ConcurrentLinkedQueue

팍 식었다.. 그냥 Deque 사용하자. 귀찮다.

'Learn > 이것이 자바다' 카테고리의 다른 글

람다식, 함수형 프로그래밍, 메소드 참조, 생성자 참조 (1)	2024.12.11
[이것이 자바다 확인문제] chapter 15 (0)	2024.12.10
[이것이 자바다] chapter 13 확인문제 (0)	2024.12.04
제네릭, 와일드카드 (0)	2024.12.03
[이것이 자바다] chapter 12 확인 문제 (0)	2024.12.03

컬렉션

Predicate

함수형 인터페이스

Splitator

List 컬렉션:

Interface List<E>

List 인터페이스에서 추가로 구현해야되는 함수들

UnaryOperator

Iterator

ListIterator

Comparator

ArrayList

Vector

LinkedList

Set Interface

Abstract Set

HashSet

번외 HashTable

LinkedHashSet 와 TreeSet

Map Interface

public interface BiFunction<T, U, R>

Map.forEach(BiConsumer<? super K, ? super V> action)

HashMap / TreeMap / LinkedHashMap

Fail-fast behavior

Is synchronized

Red-Black Tree

LIFO : FIFO = Stack : Queue

Stack Class

Deque Interface : 구현체들ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList

Queue Interface: 구현체 LinkedList, ConcurrentLinkedQueue

'Learn > 이것이 자바다' 카테고리의 다른 글

티스토리툴바