Week 5

Week 5
: 이해하는데 한 세월

---

✍️  6월 첫째 주 멘토링을 시작했다!
지금까지 공부하면서 이해의 비중보다는 블로그와 노션에 글을 올려야 한다는 강박이 점점 심해지는 것을 느껴서 이번 주에는 글을 작성하기 보단 아이패드에 그려가면서 조금 더 이해한 뒤에 글을 작성하려고 했던 한 주다.
그래서 게시글도 하나밖에 작성하지 못했는데, 그 글도 수정할 내용이 산더미다.
책을 빠르게 읽으면서 5주차에 공부한 내용을 정리해야겠다!

이번 주는 Collection Framework에 대해 집중적으로 공부했고, Set과 Map 그리고 스레드에 대해 공부했다.
(스레드는 맛보기 스푼정도만)

---

1. Generic Type Erasure

기존에는 타입 체크를 런타임 시점에서 수행해서 잘못된 타입으로 캐스팅 했을 경우 ClassCastException 예외가 발생하고,
해당 예외를 확인하는 과정이 오래걸리는 등의 단점이 존재했었다.
이를 해결하기 위해서 Generic 개념이 추가되고, Generic Type Erasure 를 통해 강한 타입 체크를 컴파일 타임에 수행하므로써 런타임 전에 예외가 발생하여 빠르게 문제되는 부분을 수정 할 수 있다.

객체의 제네릭이 Bounded(<T extends Parent>, <T super Child>) 타입으로 설정되어 있다면 컴파일 시 Generic Type Erasure가 강한 타입 체크가 일어나고 타입 정보는 바이트 코드 상에서 사라진다.
하지만 Un-Bounded 타입으로 설정되어 있다면 컴파일러에 의해 해당 제네릭을 Object로 변경하고, 여기서 직접적인 캐스팅이나 Bridge Method로 제네릭에 대한 타입을 명시해주지 않는다면 강한 타입 체크에 의해 컴파일 에러가 발생하게 된다.

이렇게 Generic Type Erasure에 의해 컴파일 타임에서 강한 타입 체크가 발생하고, 해당 객체의 타입 정보를 바이트 코드에 담지 않고 런타임 시점으로 넘기게 되면 런타임에서 해당 객체의 타입 정보를 알 수가 없기 때문에 그리고 알 필요가 없기 때문에 ClassCastException 예외가 발생하지 않는다. 이미 컴파일 단계에서 제네릭 타입 소거에 의해서 타입 체크가 끝났기 때문이다.

+) Type Token이란?

 

2. Cache Algorithm

페이지와 프레임은 메모리를 일정한 크기의 공간으로 나누어 관리하는 단위.
📍 페이지 : 물리 메모리에 할당되는 단위 혹은 일정한 크기로 나뉘어진 블록
📍 프레임 : 가상 메모리에 할당되는 단위 혹은 일정한 크기로 나뉘어진 블록

1) FIFO (First In, First Out)
선입선출 알고리즘을 이용해 페이지 교체 작업을 수행한다.
먼저 들어온 페이지를 가장 먼저 빼고, CPU에서 요청한 Page Fault 페이지를 해당 자리에 넣는다.

2) LRU (Least Recently Used)
최근까지 가장 오랫동안 사용되지 않은 페이지를 제외 대상에서 우선순위로 둔다.
이 때, 각 페이지 마다 계수기가 존재해 해당 페이지가 얼마나 참조되지 않았는지 확인한다.

3) LFU (Least Frequently Used)
최근에 가장 참조된 횟수가 적은 페이지를 제외 대상의 우선순위로 둔다.
각 페이지마다 참조 횟수를 기억할 변수를 갖게해서 사용할 때 마다 1씩 증가하여 이를 비교해서 제외 대상을 도출한다.

 

3. Set

Set 자료구조는 순서에 상관없이 중복을 제거하여 객체 내에 데이터를 담는다.
Java에서는 HashSet, TreeSet, LinkedHashSet이 대표적이다.

📍HashSet
내부적으로 HashMap 객체를 생성해 작동하며, 순서에 상관없이 객체에 데이터를 담는다.
HashMap의 해시 알고리즘을 이용해 담길 데이터의 해시코드 값을 통해 인덱스에 접근하므로 O(1)의 시간 복잡도를 가지지만,
해시 충돌로 인해 하나의 인덱스에 데이터 쏠림 현상이 발생하면 심할 경우 O(h/n)의 시간 복잡도를 가질 수도 있다.

📍TreeSet
내부적으로 TreeMap 객체를 생성해 작동하는데, 이로 인해 TreeSet은 이진 탐색 트리 > Red-Black 이진 트리 구조를 가지고 있다.
때문에 데이터를 조회하는 것에 있어 O(logN) 시간 복잡도를 가지는데, 대표적인 Set 구현체 중에서 가장 느린 성능을 가지고 있다.
하지만 LinkedList 처럼 노드 간의 연결로 구성되어 있기 때문에 데이터를 담는 순서대로 저장된다.

 

4. Priority Queue (우선순위 큐)

사실 Queue 자료구조를 구현한 클래스에 대해서 많이 찾아보지는 못했다.
간단히 알고 있는 것은 완전 이진 트리(Complete Binary Tree) 구조를 가지기 때문에 특정 조건에 의한 우선순위 정렬에 이점을 가지고 있으며, 대표적으로 Heap 이 있다.

멘토님께서 게임의 랭킹 시스템을 예시로 들어주셨는데 정확히 와닿지는 않아서 조금 더 찾아봐야 할 것 같다.
나는 적절한 예시가 떠오르지 않는데 멘티님께서 스케쥴링에서 사용 할 수 있을 것 같다고 말씀해주셨다. 해당 부분도 알아봐야겠다!

+) Redis 에서는 우선순위 큐를 지원한다. 왜?

 

5. Hash Collision

해시 충돌. Key 값은 다르지만 해시 함수에 의해 해당 Key에 대한 해시코드가 중복되어 해당 인덱스가 비어 있지 않는 현상을 말한다.
이를 방지하기 위해 두 가지 방법이 존재하며, Java의 HashMap 클래스는 Separator Chining 을 구현하여 사용한다.

📍 Separator Chining
해시 충돌이 일어난 데이터를 해당 인덱스에 연결하는 방식을 말한다. Node 클래스의 next 필드가 이에 해당한다.
마치 LinkedList 클래스처럼 해시 충돌이 일어난 인덱스에 들어온 순서대로 연결하는 방식으로 구현되기 때문에 이렇게 Chaining된 데이터를 조회 할 때는 O(h/n)의 시간 복잡도를 가진다.

📍 Open Address
만약 메모리에 공간이 남아 있다면 남은 공간을 찾아 해시 충돌이 일어난 중복 데이터를 빈 공간에 담는다.
메모리 공간이 커지면 커질 수록 남아 있는 공간을 찾는 효율이 떨어지는 단점이 존재한다.

+) Open Address 에 대한 내용이 잘 기억나지 않는다. 조금 더 알아보자!
++) 그리고 멘티님께서 Rehashing 이라는 키워드를 말씀해주셨는데, 이는 재해싱이라는 의미로 HashMap은 Load Factor라는 값을 가지는데 현재 할당된 메모리의 사용량이 Load Factor 만큼 도달하게 되면 메모리 공간을 늘리고 기존 메모리에 담긴 데이터의 해시코드를 리해싱 작업을 하여 늘어난 메모리 공간에 재할당 해주는 작업을 의미한다.

---

추가적으로 공부할 내용들

💥 Context-Switch

💥 동시성 문제 해결 방법 > Synchronized 용례 찾아보기 > 대용량 트래픽의 상황에서 요청이 밀린다면?

💥 Atomic Operation, JNI(Java Native Interface)

💥  Thread Lock, Monitor

💥 Semaphore Mutex

📚 Type Token

📚 페이징과 프레임의 개념에 대해서 정확히 파악하기

---

💭 이번 주는 자료구조에 대해 이해하느라고 오랜 시간이 소요된 한 주다. 원래 목표는 Thread에 대한 내용까지 읽어보기라도 하는 것이 목표였는데, 생각보다 이해하는데 오래걸렸던 것 같다. 까먹기 전에 얼른 블로그에 정리 해야겠다.

얼른 자바의 신을 끝내야 다음 책으로 넘어가는데 나는 왜이렇게 이해가 더딘지..😿
그래도 지금까지 이렇게 이해 할 수 있다는게 나름의 다행인 것 같다..!
이제 자바의 신을 리뷰할 주차도 얼마 안남았는데, 더 치열하게 공부해야겠다!