Linked List

Next와 Prev는 포인터이면서 노드이다.
링크드 리스트의 의의는 스택,큐,해시테이블과 같은 데이터 구조를 구현하는데 사용된다.

LinkedList의 주요 특징

• 더블 링크드 리스트 구조: LinkedList의 각 노드는 데이터 요소와 이전 노드와 다음 노드를 가리키는 두 개의 링크로 구성됩니다. 이 링크를 통해 순차적인 탐색, 요소의 삽입 및 삭제 작업을 수행할 수 있습니다.
• 동적 크기 조정: LinkedList는 내부적으로 연결된 노드들로 구성되어 있으며, 요소의 추가나 삭제 시 필요에 따라 크기를 동적으로 조정할 수 있습니다. 이는 배열(Array)과 달리 크기 제한에 대한 걱정 없이 요소를 추가하거나 삭제할 수 있다는 장점을 가지고 있습니다.
• 느린 접근 시간: LinkedList는 인덱스를 기반으로 한 빠른 랜덤 액세스를 제공하지 않습니다. 원하는 위치의 요소에 접근하기 위해서는 첫 번째 노드부터 순차적으로 탐색해야 합니다. 따라서 요소를 검색할 때는 LinkedList보다 배열(ArrayList 등)을 사용하는 것이 더 효율적입니다.
  (애초에 연속적으로 있지 않으니까 노드가 필요하고 Offset(배열에서는 어디가 처음인지 아는게 중요한데 이때 운이 좋으면 초반에 있을수도 있고 아니면 저 끝에 있을수도 있는데 그 차이 정도)의 개념이 없음)
• 중간 삽입 및 삭제의 효율성: LinkedList는 중간에 요소를 삽입하거나 삭제하는 작업에 용이합니다. 이 작업은 해당 위치의 이전 노드와 다음 노드의 링크만 변경하면 되기 때문에 배열에 비해 효율적입니다.

Big-O 표기법

• 알고리즘의 빠른정도를 나타내는것

fail-fast

내가 관심가지는 노드에 블로킹 당했지만 복구시에 알려줌(A라는 스레드가 CPU 사용시간이 끝나서 B라는 스레드가 CPU를 점하고 다시 A로 돌아가면..??)

자바 콜렉션 프레임워크의 view

• 원본에 있는 데이터를 참조하여 일부를 보는것

Bulk

• Bulk란 대량의 요소를 한번에 처리하는 개념을 의미함

1. addAll(Collection<? extends E> c): 주어진 컬렉션 c의 모든 요소를 현재 컬렉션에 추가합니다.
2. removeAll(Collection<?> c): 주어진 컬렉션 c와 현재 컬렉션의 공통 요소를 모두 제거합니다.
3. retainAll(Collection<?> c): 현재 컬렉션과 주어진 컬렉션 c의 교집합인 요소만을 남기고 나머지 요소를 제거

Hash

• 해시(Hash)는 임의의 크기를 갖는 데이터[Key]를 고정된 크기의 값으로 변환하는 알고리즘입니다.

• 눈사태효과(Avalanche Effect) : 만약 내가 '안녕하세요'라는 파일을 보냈고 해시값으로 변환시켜 체크섬이 나왔다. 그러면 여기서 '안녕하세요. 홍길동입니다.' 라는 약간의 작은변화가 생긴다면 그 해시값은 얼마나 차이가 날까?
  -> 해시값이 적게 차이가 나는게 자명하다! 문제는 이렇게 되면 안녕하세요와 홍길동이라는 키값이 뭔지를 쉽게 파악이 할 수 있다.
  이를 방지하기 위해 값을 일부러 크게 변화 시킴

• 해시는 사람이 만든 알고리즘이다보니 '안녕하세요'와 '반갑습니다'가 같은 값이 띠일때도 있다. 이를 회피하기 위한 알고리즘도 있음(아래 설명하는 충돌해결 메커니즘)

• Hash Table

• 데이터 검색에서 사용되는 해시 알고리즘은 주로 해시 테이블(Hash Table)이라는 자료구조를 구현하는 데에 활용

• 키값과 해시값으로 구현되어있음

• 체크섬
  번호 등에 오류가 존재하는 바의 여부를 확인하기 위해 추가로 끼워넣는 번호

1. 해시 함수 (Hash function): 해시 함수는 입력 데이터를 해시 코드로 변환하는 알고리즘입니다. 입력 데이터의 특성에 따라 해시 함수는 고유한 해시 코드를 생성해야 합니다. 이 해시 코드는 버킷의 인덱스로 사용되어 데이터를 저장하고 검색할 수 있게 합니다.
2. 버킷 (Bucket): 버킷은 데이터를 저장하는 해시 테이블의 각 요소입니다. 일반적으로 배열 형태로 구성되며, 각 버킷은 데이터를 저장하기 위한 공간을 가지고 있습니다. 해시 코드에 따라 버킷의 인덱스로 매핑되어 데이터가 저장됩니다.
3. 데이터 (Data): 해시 테이블에 저장되는 실제 데이터입니다. 데이터는 키-값 쌍의 형태로 저장될 수 있으며, 키를 통해 데이터에 접근하고 검색할 수 있습니다. 각 데이터는 해시 함수를 통해 생성된 해시 코드에 따라 적절한 버킷에 저장됩니다.
4. 충돌 해결 메커니즘 (Collision resolution mechanism): 해시 함수를 통해 생성된 해시 코드는 고유해야 하지만, 서로 다른 데이터가 동일한 해시 코드를 가질 수 있습니다. 이를 "충돌(collision)"이라고 합니다. 충돌이 발생할 경우에는 충돌 해결 메커니즘이 필요합니다. 일반적으로 충돌을 해결하기 위해 체이닝(Chaining) 또는 개방 주소법(Open addressing)과 같은 방법을 사용합니다.
5. 로드 팩터 (Load factor): 로드 팩터는 해시 테이블에 저장된 데이터의 양과 버킷의 수 사이의 비율을 나타냅니다. 로드 팩터는 해시 테이블의 성능에 영향을 미치는 중요한 요소로서, 적절한 로드 팩터를 유지하기 위해 필요에 따라 버킷의 크기를 동적으로 조절할 수 있습니다.

해시 테이블은 다음과 같은 과정으로 동작함
1. 해시 함수를 선정한다.(주로 MD5가 선택됨)
키의 일부분 혹은 전체를 Input으로 하여 해시 함수에 의한 결과값을 도출한다.
(위의 결과값을 해시값이라고 하며 이는 인덱스로 취급된다.)

Set
자바에서 Set은 중복되는 요소가 없는 컬렉션 인터페이스