자료구조와 알고리즘에 대해 설명해주세요

자료구조는 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조이고
알고리즘이란 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임을 의미합니다.

Java Collection Framework란 무엇인가요?

컬렉션 프레임워크란 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스들의 집합을 의미합니다.
이러한 컬렉션 프레임워크는 Collection 인터페이스와 Map인터페이스로 나뉘며, Collection 인터페이스 하위에는 List,Queue,Set 인터페이스가 있습니다.

참고 - 객체만 담을 수 있고, 이는 객체의 주소를 담는 것이기에 null도 저장 가능

배열과 ArrayList가 무엇인지

배열이란 동일한 데이터 타입의 값들을 연속된 메모리 공간에 저장하는 자료구조이며, 크기를 동적으로 변경할 수 없습니다.
이러한 배열의 요소는 메모리에 연속적으로 저장되며, 각 요소는 고유한 인덱스를 가지므로 Random Access가 가능합니다.(물리적 저장순서와 논리적 저장순서가 일치하기에 인덱스 통해 빠르게 접근)
배열은 데이터 개수가 정해져있고, 접근이 빈번할 경우 사용하기 좋은 자료구조이나, 중간에 요소가 삽입되거나 삭제되는 경우엔 적합하지 않는 자료구조입니다.
또한 배열은 공간 지역성이 보장되어 요소 접근 시 Cache hit 가능성이 커 캐시의 효율성을 높일 수 있습니다.


ArrayList는 동일한 데이터 타입의 값들을 연속된 메모리 공간에 저장하며, 크기를 동적으로 변경할 수 있는 자료구조입니다.(요소 추가 시 동적으로 크기 증가)
ArrayList는 내부적으로 데이터를 (Object[])배열에 저장하고 있어, 각 요소가 인덱스를 가지고 있고, 이를 바탕으로 Random Access가 가능합니다.
ArrayList는 데이터 개수가 정해져 있지 않고, 접근이 빈번할 경우 사용하기 좋은 자료구조입니다.
이 또한 공간지역성이 보장되어 요소 접근 시 Cache hit 가능성이 커 캐시의 효율성을 높일 수 있습니다.


참고
Random Access란 데이터의 특정 위치에 직접 접근할 수 있는 것을 의미, 메모리 상 시작 주소 + (인덱스 x 데이터 타입 크기(참조형 변수 크기 4byte))를 통해 해당 인덱스 빠르게 접근 가능
공간지역성이란, 관련된 데이터들이 연속적인 메모리 주소에 위치하면 그 데이터를 빠르게 읽거나 쓸수 있다.
캐시 히트는 필요한 데이터가 캐시에 있다면 캐시에서 빠르게 데이터를 가져오는 것을 의미, 캐시 히트 가능성이 높다는 것은 캐시에서 이 데이터를 찾을 확률이 높다는 것

배열의 시간복잡도
접근(O(1)) : 배열의 특정 인덱스에 위치한 요소에 바로 접근 가능
삽입(O(n)) : 중간에 요소를 삽입하려면 이후의 모든 요소를 하나씩 밀어야 함
삭제(O(n)) : 중간의 요소를 삭제하려면 이후의 모든 요소를 하나씩 당겨야 합니다.
검색(O(n)) : 특정 요소를 찾기 위해서는 순차적으로 검색을 해야 함

ArrayList도 접근은 O(1), 삽입의 경우 빈자리가 있을때 맨 끝에 추가한다면 O(1)
내부가 꽉찼을때 끝에 추가할때는 O(N), 중간의 경우 당연히 O(N)
삭제의 경우 삭제 뒤에 애들을 앞으로 떙겨야 하기에 O(n), 근데 마지막 값을 지운다면 O(1)일듯

차이를 물어보면 배열의 경우 한번 생성되면 크기를 변경할 수 없는 반면, ArrayList는 동적으로 크기가 조절됨. 요소를 추가하거나 제거할때 자동으로 크기가 변경됨

캐시의 효율성에 대해 설명해주세요.

CPU는 필요한 데이터를 RAM에서 가져올 수 있지만, 이렇게 직접 데이터를 읽는 것은 상대적으로 느립니다.
이를 위해 훨씬 빠른 속도를 가진 메모리인 캐시를 사용하며, 필요한 데이터가 캐시에 있다면 캐시에서 빠르게 데이터를 가져올 수 있는데 이를 캐시히트가 발생되었다고 합니다.
하지만 캐시의 크기는 매우 작기에, 모든 데이터를 저장할 수 없고, CPU는 어떤 데이터를 캐시에 저장할지 결정하는데 이때 중요한 원칙이 공간지역성입니다.
이는 메모리에 인접한 위치에 있는 데이터는 함께 사용될 가능성이 높다는 원리인데, 배열의 경우 모든 요소가 메모리 상 연속적으로 위치해있습니다.
따라서 한번에 여러 요소를 캐시에 저장할 수 있고, 이후 배열에 접근할때 빠른 속도를 얻을 수 있습니다.
요약하자면 배열의 요소들은 메모리상에 인접해 있기때문에, 한번에 여러 요소를 캐시에 저장할 수 있고, 그래서 CPU가 배열의 데이터에 빠르게 접근할 수 있습니다.



참고 - 컴퓨터에서 데이터를 읽을때, 주소가 연속적인 메모리 위치에 있는 데이터를 읽는 것이 흩어진것 보다 효과적
왜냐하면 컴퓨터는 메모리에서 블록 단위로 데이터를 읽음. 따라서 배열과 같이 데이터가 연속적인 메모리 위치에 있으면, 컴퓨터는 한번에 여러데이터 읽을 수 있따.
이것이 한번에 여러 요소를 캐시에 저장할 수 있다는 의미.
데이터가 메모리의 여러 위치에 있으면, 컴퓨터는 여러 블록을 읽어야 함(접근하는데 더 많은 시간이 듬)
연관 데이터를 가능한 가까이 두는것이 캐시를 효율적으로 사용하고 성능을 높이는데 사용
캐시 라인을 기반으로 읽어옴 예를들어 arr[0]이 캐시에 로드되면,arr[1],arr[2]등 같은 캐시라인에 있는 배열 요소도 같이 캐시에 로드됨
즉 cpu가 램에서 데이터를 가져올때 캐시 라인 단위로 가져옴(일반적으로 64바이트)
따라서 cpu가 arr[0]의 값을 가져올때 캐시는 arr[0]을 포함하는 메모리 블록을 가져오며 여기엔 arr[0]제외 인접 데이터들도 포함됨
따라서 arr[1],arr[2]는 캐시에 저장되고 나중에 접근할때는 RAM에 접근할 필요 X

LinkedList에 대해 아시는 대로 설명해주세요.

LinkedList란 각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다.
이러한 링크드 리스트의 종류로는 단방향, 양방향, 원형 링크드리스트들이 존재합니다.
LinkedList의 각 요소는 메모리상에 불연속적으로 배치되어 있습니다.
따라서 특정 인덱스 요소에 접근하려면 ArrayList와 다르게 순차적으로 하므로 접근에 최적화된 자료구조는 아닙니다
하지만 삽입 삭제가 빈번하게 일어나는 경우에는 유용한 자료구조이며, CPU 스케쥴링이나 메모리 관리 등에서 사용되는
큐나 스택등의 자료구조를 구현하는데 사용될 수 있습니다.

ArrayList와 LinkedList의 차이에 대해 설명해주세요.

ArrayList는 동적 배열의 형태를 가지고 있어, 데이터가 메모리 상에서 연속적으로 배치됩니다.
이로 인해 인덱스를 통해 빠르게 요소에 접근하는 것이 가능합니다. 이를 'random access'라고 합니다.
그러나 이런 특성 때문에 중간에 새로운 요소를 삽입하거나 기존 요소를 삭제할 때는 배열의 요소들을 이동시키는 추가적인 작업이 필요합니다
.이는 비효율적일 수 있습니다. 또한, 배열이 꽉 차면 크기를 늘려야 하며 이 과정에서도 시간이 소요됩니다. 하지만 ArrayList의 공간 지역성이 보장되므로, 캐시 히트 가능성이 높아져서 캐시의 효율성이 좋습니다.

반면, LinkedList는 연결 리스트의 형태를 가지며, 각 요소가 메모리 상에서 불연속적으로 배치됩니다.
이로 인해 인덱스를 통한 빠른 접근이 어렵습니다. 대신, LinkedList는 노드의 연결 정보만 변경함으로써 요소의 삽입과 삭제를 매우 효율적으로 수행할 수 있습니다.
특히, 리스트의 시작 부분(head)나 끝 부분(tail)에서의 삽입 및 삭제는 매우 빠릅니다.
그러나 LinkedList는 공간 지역성이 보장되지 않아 캐시 히트 가능성이 낮으며, 이로 인해 캐시의 효율성이 상대적으로 떨어집니다.

요약하자면, 요소의 접근이 주로 이루어지는 경우에는 ArrayList를, 요소의 삽입과 삭제가 빈번하게 이루어지는 경우에는 LinkedList를 사용하는 것이 더 효율적일 수 있습니다."

참고 - ArrayList 값 연속정 저장 : Random Access, LinkedList는 값이 산재되어 저장되어 있음
첫번째 위치에 insert/remove DoublyLinkedList의 경우 O(1), ArrayList의 경우 O(N)
마지막 위치에 insert/remove DoubleLinkedList의 경우 O(1), ArrayList의 경우 O(1) or O(N)
중간에 insert/remove Doubly : O(N) or searchtime + O(1), ArrayList : O(N)
값으로 search는 둘다 O(N)이지만 ArrayList가 나음
인덱스로 값을 get, LinkedList의 경우 O(N), ArrayList의 경우 O(1)
값으로 remove 시 둘다 O(N)

왜 ArrayList의 캐시 효율성이 더 좋은지 가능한 상세히 설명해주세요

공간 지역성(spatial Locality)는 컴퓨터 프로그램에서 사용하는 데이터가 메모리의 특정 구간에 집중되어 있는 경향을 말합니다.
즉, 한번 참조된 데이터 근처의 데이터가 곧 이어서 참조될 가능성이 높다는 의미이며, 이는 CPU 캐시의 설계와 밀접한 관계가 있습니다.
CPU 캐시는 주기억장치(RAM)에 비해 매우 빠른 속도를 가지지만 그만큼 용량이 작아서 전체 메모리를 저장할 순 없습니다.
따라서 CPU는 프로그램이 주로 참조하는 데이터를 캐시에 저장합니다. 이때 공간지역성이 있다면 한번 참조된 데이터 주변의 데이터가
곧 이어서 참조될 가능성이 높으므로 이러한 데이터를 캐시에 미리 가져와 놓으면 메모리 접근 시간을 줄일 수 있습니다.
ArrayList는 메모리 상에서 연속적인 데이터를 저장하는 구조를 가지고 있습니다. 따라서 한 데이터가 CPU 캐시에 로드되면 그 근처의 데이터도 함께 로드되게 됩니다.
이후 이 근처의 데이터에 접근하게 되면, 이미 캐시에 데이터가 존재하므로 캐시 히트가 발생하고, 메모리 접근 시간이 크게 줄어듭니다.
반면 LinkedList는 노드들이 메모리의 여기저기에 분산되어 저장됩니다.
각 노드는 자신의 다음 노드에 대한 참조만을 가지고 있으며, 이 참조는 메모리상의 아무 곳에나 위치할 수 있습니다.
따라서 한 노드를 참조했다고 해서 그 근처의 노드가 곧바로 참조될 확률이 낮습니다. 이것이 LinkedList에서 공간지역성이 보장되지 않는 이유입니다.
이로 인해 LinkedList를 사용할때는 캐시 히트 가능성이 상대적으로 낮아지고, 이에 따라 캐시의 효율성이 떨어집니다.

Array와 LinkedList의 차이점에 대해 설명해주세요

이둘의 주요 차이점은 데이터가 메모리에 저장되는 방식과 각 요소에 대한 접근 방식에 있습니다
배열은 'Random Access'를 지원합니다. 이는 배열의 요소들이 메모리 상에서 연속적으로 위치하기 때문에 가능한 것입니다
따라서, 인덱스를 통해 배열의 특정 요소에 직접 접근할 수 있으며, 이러한 접근은 일정한 시간복잡도인 O(1)를 가집니다
반면에 LinkedList는 'Sequential Access'를 지원합니다. LinkedList의 요소들은 메모리 상의 임의의 위치에 있으며, 각 요소(노드)는 다음 요소를 가리키는 링크를 가지고 있습니다
이 링크를 따라가면서 요소에 접근해야 하기 때문에, 특정 요소에 접근하는 데는 시간복잡도 O(N)이 소요됩니다
배열에서 요소의 삽입 또는 삭제는 복잡한 작업입니다. 배열은 고정된 크기를 가지므로, 삽입 또는 삭제를 위해서는 배열의 크기를 조정하거나, 요소들을 재배치해야 합니다.
이러한 작업은 시간복잡도 O(N)이 소요됩니다.
반면에 LinkedList에서는 삽입 및 삭제 작업이 상대적으로 간단합니다. 특정 위치에 삽입 또는 삭제를 위해서는 단지 몇 개의 링크를 조정하면 되므로, 이 작업은 일반적으로 시간복잡도 O(1)을 가집니다.
배열은 '정적 메모리 할당'을 사용합니다. 즉, 배열이 생성될 때 그 크기가 고정되며, 메모리 상에 연속적으로 할당됩니다. 따라서, 배열의 크기는 변경할 수 없습니다.
반면에 LinkedList는 '동적 메모리 할당'을 사용합니다. LinkedList의 요소(노드)는 필요에 따라 생성되고, 각 노드는 메모리 상의 임의의 위치에 할당됩니다. 이러한 특성 덕분에 LinkedList는 필요에 따라 크기를 동적으로 변경할 수 있습니다."

참고 - 배열은 스택 영역에 할당되고, LinkedList는 힙 영역에 할당되는 것이 일반적입니다.

스택과 큐의 차이점에 대해 설명해주세요

스택은 세로로된 바구니와 같은 구조로, 자료가 쌓이는 구조를 가지고 있습니다.
이것은 Last in First out 특성을 가지고 있어, 가장 나중에 넣은 데이터를 가장 먼저 꺼내게 됩니다.
큐는 가로로된 통과 같은 구조로, 데이터가 한쪽 방향으로만 흐르는 구조를 가지고 있습니다.
이는 First in First Out 특성을 가지고 있어, 가장 먼저 넣은 데이터를 가장 먼저 꺼냅니다.


참고 - LinkedList는 노드를 앞이나 뒤에 추가시 제거하는 시간이 상수 시간에 가능
이러한 스택은 배열로 구현하는 경우, 데이터를 제거할때 실제 데이터를 지울 필요가 없고, top 인덱스를 지우는 것만으로도
데이터의 삽입과 삭제를 효과적으로 관리할 수 있습니다.
이러한 큐는 배열로 구현하게 되면 데이터를 제거할때마다 남은 데이터를 앞으로 당겨야 하는 비효율성이 있습니다.
따라서 LinkedList와 같이 삽입 삭제가 용이한 자료구조로 구현하는것이 일반적입니다.

힙에 대해 아시는 대로 설명해주세요.

힙은 최솟값 또는 최대값을 빠르게 찾아내기 위해 완전 이진트리 형태로 만들어진 자료구조입니다.
힙에는 최대힙과 최소힙 두가지 유형이있습니다.
최대힙에서는 부모의 노드값이 그 자식 노드값보다 항상 크거나 같습니다.
그리고 최소힙에서는 부모의 노드 값이 그 자식 노드값 보다 항상 작거나 같습니다. 이러한 힙을 사용하면 데이터 최댓값 또는 최솟값을 상수시간에 찾아낼 수 있으며, 삽입과 삭제는 로그 시간에 할 수 있기에 효율적입니다.

참고
이진트리 - 모든 노드의 최대 차수를 2로 제한한것
완전(complete) 이진트리 - 모든 노드의 최대 차수 2 제한 + 마지막 레벨을 제외한 모든 노드 채워져 + 모든 노드는 왼쪽부터 채워져야함
포화이진트리(perfect binary tree) 이진트리 - 완전 이진 트리 조건 + 마지막 레벨을 제외한 모든 노드는 두개의 자식 노드를 가짐
상수시간 - 데이터 크기와 무관하게 일정한 시간을 필요로 한다는 것
예를들어 배열에서 특정 인덱스의 값을 읽는 작업은 배열의 크기와 상관없이 항상 동일한 시간이 소요됨
보통 배열로 구현하는 것이 효율적

왜 힙의 삽입,삭제 연산의 시간복잡도는 O(logN)인지 설명해주세요.

힙은 완전 이진 트리의 형태를 띄고있기에 노드의 수가 늘어남에 따라 트리의 높이는 logN에 비례합니다(각 레벨에서 노드의 수가 두배로 늘어나므로 log에 비례)
힙에서 삽입 및 삭제 연산은 루트 노드에서 시작하여 leaf 노드까지의 경로를 따라 이루어집니다.
이 때문에 이러한 연산들은 트리에 높이에 비례하는 시간이 걸리며 이로인해 삽입 삭제 연산은 O(logN)이됩니다.


예를 들어 삽입 연산의 경우 새로운 요소는 처음에 트리의 가장 하위 레벨(leaf노드)에 추가되고,그 후 힙 속성을 유지하며 적절한 위치로 이동합니다.
이러한 연산은 새 요소를 부모 노드와 비교하며 진행되므로, 트리의 높이만큼의 비교가 이루어집니다.
힙에서 가장 크거나 작은 요소를 삭제하면 일반적으로 루트 노드가 삭제됩니다.
이후 트리의 가장 하위 레벨에서 하나의 노드를 루트로 이동시키고, 이 노드를 자식과 비교하며 적절한 위치로 이동시킵니다.
이러한 연산 또한 트리의 높이에 비례하는 시간이 걸립니다.

우선순위큐가 무엇인지와 동작원리에 대해 설명해주세요.

우선 순위 큐란 각각의 요소들이 우선순위를 가지고 있고, 요소들의 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조입니다.
우선순위 큐는 자료를 추가하는 작업과, 삭제하는 작업 모두 지원하며 데이터를 추가할때는 우선순위에 따라 적절한 위치에 삽입되며, 데이터를 제거할때는 항상 가장 높은 우선순위의 항목이 제거됩니다.
이러한 우선순위큐를 구현하기 위해서 일반적으로 힙이라는 자료구조를 구현합니다.

따라서 모든 정점은 자신의 자식 요소보다 우선순위가 높다는 성질과, 완전 이진 트리의 성질로 인해 삽입,삭제 시 O(logN)의 시간복잡도를 보입니다.
또한 우선순위가 가장 높은 요소는 루트에 위치하므로, 이를 조회하는데에는 상수의 시간이 걸립니다.

참고 - 힙은 형제노드와 대소 비교를 안함

우선순위큐를 힙이 아닌 다른 자료구조로 구현한다면 어떻게 될까요?

힙이 아닌 배열 이나 연결리스트를 통해서도 구현할 수 있습니다.
배열로 구현시, 배열의 새로운 요소를 추가하는 것은 O(1)의 시간복잡도를 가지며, 새 요소는 배열의 마지막에 추가됩니다.
삭제시에는 가장 우선순위가 높은 요소를 찾아 삭제하는데 O(N)의 시간복잡도를 가집니다.(모든 요소 탐색) 조회 또한 가장 우선 순위가 높은 요소를 찾는데 O(N)의 시간복잡도를 가집니다.
연결리스트로 구현시 삽입에 O(1)시간복잡도를 가집니다.(새 요소는 리스트의 시작 또는 끝에 삽입됨)
삭제 시에는 O(N)이 걸립니다(전체 탐색)
조회의 경우에도 O(N)의 시간복잡도를 가집니다.(전체 탐색)

덱(deque)에 대해 설명해주세요

덱(Deque)은 "Double-Ended Queue"의 줄임말로, 앞과 뒤에서 데이터의 삽입과 삭제가 모두 가능한 자료구조입니다. 이 특성 때문에 덱은 큐(Queue)와 스택(Stack)의 연산을 모두 지원합니다. 덱은 유연성이 높아서 필요에 따라 스택처럼 Last-In-First-Out(LIFO) 방식으로 동작하게 할 수도 있고, 큐처럼 First-In-First-Out(FIFO) 방식으로 동작하게 할 수도 있습니다.

hash와 hash Function이 무엇인지 설명해주세요

Hash란 일반적으로 key가 Hash Function을 통과하여 암호화되어 나온 결과물을 의미하고, Hash Function은 임의의 길이의 입력값을 고정된 길이의 암호화된 출력으로 변환해 주는 함수를 뜻합니다.
이러한 해시 함수는 어떤 입력 값에도 항상 고정된 길이의 해시값을 출력하고, 입력 값이 아주 일부만 변경되어도 전혀 다른 결과값을 출력하는 특징을 가집니다.(즉 출력물로 유추 불가)


참고 - 왜 사용할까??
해시 함수를 사용하면 원하는 데이터를 찾는데 필요한 시간을 줄일 수 있습니다.
예를들어 배열에서 특정 값을 찾으려면 보통 원하는 값을 찾을때 까지 배열의 모든 요소를 탐색해야 하므로 시간이 오래걸릴 수 있습니다.
하지만 해시 테이블을 사용한다고 하면, 특정 키의 해시 값을 계산하여 바로 해당 위치에 접근할 수 있으므로, 상대적으로 빠른 시간안에 원하는 값을 찾을 수 있습니다.

또한 해시 함수는 단방향성을 가지므로, 해시 값을 통해 유추가 어려워 데이터의 보안성 또한 높일 수 있다.


Constant Time Complexity: 해시 테이블에서 데이터의 조회, 삽입, 삭제 연산은 일반적으로 평균 시간 복잡도가 O(1)입니다. 즉, 데이터의 양에 관계없이 거의 일정한 시간이 걸립니다. Direct Access: 해시 함수의 결과값은 배열의 인덱스처럼 사용됩니다. 이 인덱스를 사용해서 직접 해당 위치에 접근할 수 있기 때문에 데이터를 빠르게 찾을 수 있습니다.

해시 충돌이 무엇인지 혹시 아시나요?

해시 충돌이란 입력한 키 값이 다름에도 불구하고, 같은 해시값이 나오는 경우를 의미합니다.

이러한 해시 충돌은 불가피한것인가요??

일반적으로 해시 충돌은 불가피한 현상입니다. 저는 이 이유를 비둘기집 원리와 함께 설명드리고자 합니다.
비들기집 원리는 간단히 말해서, 만약 n개의 비둘기집에 n+1마리의 비둘기가 있다면, 적어도 하나의 비둘기 집에는 두마리 이상의 비둘기가 있다는 원리입니다.
해시함수의 경우, 일정한 크기의 해시 테이블에 많은 입력을 매핑해야 하는 상황에서 이 원리가 적용됩니다.
즉, 한정된 수의 버킷에 무한히 많은 키를 매핑해야하는데, 이 경우엔 어떤 해시 함수를 사용하더라도 충돌은 불가피 합니다.
물론, 실제로는 무한히 많은 키를 다루는 것은 아니지만, 주어진 입력 데이터의 가능한 모든 조합이 해시 테이블의 슬롯 수보다 많을 가능성이 높습니다.
예를들어 문자열을 키로 사용한다고 가정해 보겠습니다. 문자열은 알파벳,숫자,특수 문자등 다양한 문자의 조합으로 이루어질 수 있고, 그 길이에도 제한이 없습니다.
이렇게 가능한 조합이 거의 무한대에 가까운 데이터를 키로 사용할때, 이를 저장하기 위한 해시 테이블의 크기를 그만큼 무한대에 가까운크기로 만들 수 없습니다.
따라서 해시 함수와 해시 테이블의 설계 과정에서 충돌을 최소화하는 것이 중요하며, 이를 효과적으로 처리하는 방법을 갖추는 것이 중요합니다.

해시 충돌을 해결하는 방법에 대해 가능한 상세히 설명해주세요.

해시 충돌(안 일어난다면 탐색,삽입,삭제 연산이 모두 O(1))을 해결하는 대표적인 방법에는 개방 주소법(Open Addressing)과 분리 연결법이 있습니다.
개방 주소법은 한 버킷에 오직 하나의 엔트리만 저장되는 방식으로, 충돌 발생 시 다른 버킷에 데이터를 저장합니다..
충돌이 발생한 경우 probing을 바탕으로 다음 슬롯을 찾아가는데, 이러한 probing 방법에는 선형 탐사법, 제곱 탐사법, 이중 해싱 등이 있습니다.

분리 연결법(Seperate Chaining)은 개방 주소법과 달리 한 버킷 당 들어갈 수 있는 엔트리 수에 제한을 두지 않는 방식입니다.
이는 해시 충돌이 일어난 경우 해당 버킷에 연결된 리스트에 데이터를 추가합니다.
하지만 개방 주소법에 비해 추가적인 메모리 공간(다음 노드를 가리키는 포인터 공간)이 필요합니다.

지금까지 설명드린 두가지 방법외에도, (해시 테이블의 Load Factor가 높은 경우엔) 크기가 더 큰 새로운 테이블을 만들어 기존 데이터를 옮겨 사용하거나
체이닝 방법을 통해 연결리스트가 너무 길어졌다면, 재해싱을 통해서 너무 길어진 리스트의 길이를 나누어 다시 저장하는 방법도 있습니다.


데이터가 적은 경우엔 일반적으로 개방 주소법이 더 빠릅니다.(충돌이 발생해도 추가적인 메모리 공간 없이 원래 해시테이블 내에서 충돌을 해결하기에)

부가 내용들
선형 탐사법 : 해시 충돌이 일어난 경우, 해시값에서 고정된 폭만큼 옮겨 다음 빈칸을 찾는 방법
-> 간단하지만 테이블의 연속된 공간에 데이터가 몰리고, 같은 해시값이 나올수록 탐색 효율이 계속 나빠짐.(해시 충돌이 해시 값 전체에 균등한 경우 유용)

제곱 탐사법 : 탐사폭이 제곱으로 늘어남.(ex: 2의 1제곱, 2제곱 ~~~~)
데이터가 메모리 공간에 균등하게 분포되지 않고, 특정 제곱값에만 집중될 수 있음.(탐색의 연쇄적 충돌은 선형보단 덜함)

이중 해싱(로드 팩터 높은 경우) : 충돌 시 항목을 저장할 다음 위치를 결정할때, 원래 해시 함수와 다른 별개의 해시 함수를 사용하는 방법
이 방법은 이전 방법에 비해 균일하게 데이터를 분포시킬 수 있습니다.하지만 두번째 해시 함수를 통해 새로운 해시값을 생성해서 추가 연산을 요구하게 되며, 이를 바탕으로 탐색 경로를 설정하기에, 빈 슬롯을 찾기 위해 메모리 내 여러 위치를 불규칙하게 접근하게 됩니다.


Load Factor(적재율)는 해시 테이블에서 현재 저장된 엔트리의 수와, 해시 테이블의 전체 버킷수의 비율을 나타냄(엔트리수 / 전체 버킷 수)
load factor가 1에 가까워질수록 충돌 확률 증가, 로드 팩터가 높다면 보통 재해싱을 통해 더 큰 크기로 확장.(즉 새로운 버킷에 재배치)
반면 너무 낮다면 메모리 사용이 비효율적일 수 있다.

해시 테이블의 기본 개념을 간단히 되짚어보면, 해시 테이블은 키를 입력으로 받아 해시 함수를 통해 해당 키에 대한 인덱스 값을 생성하고, 그 인덱스에 해당하는 위치에 값을 저장하는 자료구조

체이닝으로 충돌을 해결하면, (리스트로 데이터가 저장되어있기에) 원하는 값을 찾기 위해 해당 인덱스(해시값)에 연결된 모든 키를 확인해야 될 수 있다.(탐색 및 삭제에 O(k : 키의 갯수))
참고 - 충돌이 일어나지 않는다면, 즉 각각의 키가 유일한 해시값을 가진다면, 탐색+삽입+삭제는 O(1)
참고 - 개방 주소법으로 해결하면 탐색 및 삭제의 시간 복잡도는 로드 팩터에 비례합니다.

HashSet에 아시는 대로 설명해주세요.

HashSet은 Set인터페이스 구현체 중 하나입니다. HashSet은 중복된 요소를 허용하지 않는데, 이때 같음은 equals() 메서드와 HashCode() 메서드로 판단합니다.
그리고 순서를 보장하지 않습니다. 이러한 HashSet은 내부적으로 HashMap을 사용하고, 각각의 요소들이 해시 함수를 통해 결정되는 버킷에 저장됩니다.
따라서 특정 요소를 찾거나 추가하거나 삭제하는데, 상수시간이 걸립니다.
하지만 해시 충돌이 발생한다면 O(n)의 시간복잡도를 가질수있습니다.(체이닝으로 해결 후 모든 요소가 동일한 버킷에 해시되는 경우)

꼬리질문 - 왜 입력 순서가 보장되지 않을까요??? 데이터 해싱된 값에 따라 저장되는 위치가 달라지기 때문에 순서가 보장되지 않습니다.
만약 순서가 보장되어야 하는 상황이라면 LinkedHashSet을 사용하면 됩니다.

참고 - hashCode()는 객체를 HashSet에 추가할때 해당 객체의 저장 위치 결정
equals() 메서드는 해시 충돌이 일어날 때, 실제로 동일한 객체인지를 판별

TreeSet에 아시는 대로 설명해주세요.

TreeSet은 Set인터페이스 구현체 중 하나로 HashSet과 같이 중복을 허용하지 않습니다.
이러한 TreeSet의 가장 중요한 특징 중 하나는 자동 정렬기능입니다. TreeSet에 요소를 추가하면, 요소는 자연 순서 또는 TreeSet을 생성할때 제공한 Comparator에 따라 자동정렬됩니다.
방금 말한 자연 순서란 요소가 Comparable 인터페이스를 구현하고 있는 경우 해당 객체 compareTo 메서드를 통해 결정됩니다.
TreeSet은 내부적으로 레드 블랙 트리라는 자료 구조를 사용합니다.
따라서 추가,삭제,검색 작업은 모두 log(n)의 시간복잡도를 가집니다. 이는 정렬된 상태를 유지하면서 이러한 연산을 수행하는 경우에 유용합니다.
참고 - 삽입 및 삭제 시 트리의 균형을 유지하기 위한 재배치가 필요

BST(Binary Search Tree, 이진탐색트리)와 Binary Tree(이진트리)에 대해 설명해 주세요.

이진 탐색 트리란 이진 트리의 일종으로, 특정한 규칙에 따라 데이터를 저장하는 구조입니다.
각 노드의 왼쪽 서브트리에는 현재 노드의 값보다 작은 값들을, 오른쪽 서브트리에는 현재 노드의 값보다 큰 값들을 저장하는 방식으로 작동합니다.
이러한 방식 덕분에 이진탐색 트리에서는 일반적으로 데이터 검색,삽입,삭제 등의 작업을 로그 시간 내에 처리할 수 있습니다.(편향된 경우엔 O(N))

하지만 이진 탐색 트리는 데이터가 이미 정렬되어있거나(12345 순으로 삽입한다고 생각해보자), 특정 패턴을 따라 삽입되는 경우 트리가 한쪽으로 치우쳐진 편향트리가 될 수 있습니다.
이런 경우 트리의 높이가 높아져서 탐색,삽입,삭제 등의 연산이 O(N)에 비례합니다.
따라서 이진 탐색 트리를 사용할때는 이런 문제를 고려해야 하면 이를 보완하기 위한 트리로 AVL 트리나 레드블랙 트리같은 균형 이진 탐색 트리가있습니다.

반면 이진 트리는 모든 노드가 최대 두개의 자식 노드를 가지는 트리 구조를 말합니다.
이러한 이진 트리는 빠른 데이터 삽입,삭제,검색이 가능하며, 이러한 연산은 보통 O(N)의 시간복잡도를 가집니다.
이러한 이진트리는 대개 정렬되지 않은 데이터를 저장하거나, 이진 탐색이 아닌 다른 트리 기반 알고리즘을 구현할때 사용합니다.
또한, 트리의 높이(height)를 최소화하여 효율적인 탐색을 할 수 있도록 균형 잡힌 트리(balanced tree)를 사용하는 경우도 있습니다. 대표적인 균형 잡힌 트리로는 AVL 트리, Red-Black 트리 등이 있습니다
참고 - 중위 순회 방식으로 정렬된 순서대로 읽을 수 있음.

꼬리질문 - 둘의 차이점에 대해 설명해주세요.
둘다 트리의 형태를 가진 데이터 구조이지만, 그 구조와 사용 방식에서 차이점이 있습니다.
이진 트리는 각 노드가 최대 두개의 자식 노드를 가질수 있는 트리 데이터 구조입니다.
이진 트리에서 노드는 특별한 순서로 배열되지 않습니다. 이는 이진 트리에서의 데이터 검색,삽입,삭제 연산이 효율적이지 않을 수 있습니다.
이러한 이진 트리는 주로 트리 순회나 트리 기반 알고리즘의 구현 등에 사용합니다.
반면 이진 탐색 트리는 이진 트리의 한 종류이지만, 데이터가 특정한 순서를 따라 배열됩니다. 모든 노드는 왼쪽 서브 트리의 노드들보다 크고 오른쪽 서브 트리의 노드들 보다 작습니다.
이러한 특성으로 인해 연산을 효율적으로 수행할 수 있습니다.
그러나, 이러한 성능은 트리가 균형이 잡혀있는 경우에만 보장됩니다.
즉 요약하자면, 주요 차이점은 데이터의 정렬 상태에 있습니다.
참고 - 이진 트리는 모든 노드를 방문해야 할 수 있겠지???

꼬리질문2 - 이진 탐색 트리의 연산 과정들에 대해 설명해주세요.
이진 탐색 트리에서 검색 연산은 루트 노드에서 시작합니다.
검색하려는 값이 루트 노드의 값보다 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 이동합니다.이 과정에서 검색하려는 값이 나타날때까지 반복합니다.
삽입 연산 또한 루트 노드에서 시작하며, 삽입하려는 값이 루트 노드의 값보다 작으면 왼쪽, 크면 오른쪽으로 이동합니다.
이 과정을 적절한 위치를 찾을때까지 반복합니다.
삭제의 경우에는 삭제하려는 노드를 찾은후, 그 노드가 자식노드를 가지고 있는지 확인합니다.
이때 리프노드라면 그냥 삭제하고, 하나의 자식 노드가 있으면 삭제하려는 노드를 제거하고 그 자식 노드를 삭제된 노드의 부모 노드로 연결합니다.
그리고 두개의 자식 노드가 있으면 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값이나 또는 왼쪽 서브트리의 가장 큰 값을 찾아 교체하게됩니다.
참고 - 자식 두개 일때 BST 특성을 유지하기 위해 위와 같이 진행

AVL 트리와 Red Black 트리에 대해 설명해주세요

AVL 트리와 Red black 트리 모두 BST의 단점인 트리의 불균형을 해결하기 위해 고안된 자료구조로 트리의 균형을 맞추어 탐색시간을 최소화하는데 사용됩니다.
탐색 시간을 O(log N)으로 유지하면서 삽입,삭제 연산을 효율적으로 처리할 수 있도록 개발된 자료구조입니다.
이진 탐색 트리는 탐색이나 삽입,삭제 연산시 평균적으로 O(log N)의 시간복잡도를 보입니다.
그러나 트리의 구조가 한쪽으로 치우쳐져 있거나, 노드의 갯수가 많아질수록, 탐색 시간이 더욱 증가할 수 있습니다.
이러한 문제를 해결하기 위해 AVL 트리와 Red-Black 트리가 개발되었습니다.
AVL 트리는 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1이하인 트리를 의미합니다.
이러한 트리 구조를 유지하기 위해 삽입,삭제 연산시에는 회전(rotate)연산을 이용해 트리의 균형을 맞추어줍니다.
Red-Black 트리는 AVL 트리보다 균형을 덜 맞춘 대신, 노드의 색깔을 이용하여 트리의 균형을 유지하는 BST입니다.
레드 블랙 트리는 모든 노드가 레드 또는 블랙 중 하나의 색깔을 가지도록 구성되며, 일정한 규칙에 따라 노드를 삽입,삭제 하며 균형을 유지하며 다음과 같은 규칙을 따릅니다.
루트 노드는 블랙이다, 모든 리프 노드는 블랙, 레드노드의 자식 노드는 모두 블랙, 어떤 노드에서 루트 노드까지 경로상에 있는 블랙 노드의 수는 모두 같다.
이러한 규칙을 통해 red-black 트리는 균형을 맞추면서도 AVL트리보다 회전 연산의 발생 횟수가 적어 더욱 효율적인 탐색이 가능합니다.
이러한 레드블랙 트리의 탐색 시간은 O(log N : 편향트리가 안되게끔 균형을 유지하므로)입니다.

AVL 트리와 Red-Black 트리중 어떤 경우에 어떤 트리를 사용하면 좋을까요?
AVL 트리는 트리의 높이를 균형 잡히게 유지하기때문에 탐색 중심의 연산이 많은 경우 유리합니다.
반면 Red-Black 트리는 삽입과 삭제가 빈번히 일어나는 경우 유리합니다.왜냐하면 Red-Black 트리는 AVL 트리에 비해 리밸런싱 연산이 덜 발생하기 때문입니다.
위 질문에 대한 추가질문 나올시
AVL 트리는 자식 노드들 간의 높이가 최대 1이 되도록 유지하는 자료구조입니다.즉 트리의 균형을 비교적 엄격하게 유지합니다.
이러한 특성때문에 AVL 트리는 깊이가 작고, 탐색 연산에 있어 효율적입니다.
하지만, 이러한 엄격한 균형 유지로 인해 삽입,삭제 시 발생할 수 있는 회전연산이 빈번히 발생합니다.
반면 AVL 트리는 노드 색상을 이용하여 트리의 균형을 부분적으로만 유지합니다.
즉 AVL트리에 비해 균형 조건이 덜 엄격하고, 리밸런싱 연산이 덜 빈번하게 발생합니다.
하지만 AVL트리에 비해 트리의 높이가 조금 더 높아질수있어, 탐색 연산이 AVL트리보다 조금 덜 효율적일순 있습니다.

참고 - (자가)균형 이진 트리란 모든 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 특정 값 이하면 이진 트리를 의미합니다.(AVL,REd-black)
균형 이진 트리의 목적은 트리의 높이를 최소화하여 연산의 효율성을 보장하는 것입니다.

레드 블랙 트리에 대해 아시는 한 상세히 설명해주세요.

레드 블랙 트리는 이진 탐색 트리의 확장 개념으로, 어떠한 연산이 일어나더라도 상대적으로 균형을 유지하는 특성이있습니다.
레드블랙 노드는 총 5가지의 규칙을 가지고있습니다.
첫번째로 각 노드는 레드 혹은 블랙이라는 색을 가지며, 이 색 정보는 노드 균형 유지를 위해 사용됩니다.
두번째로 트리의 루트노드는 항상 블랙입니다.세번째로 모든 리프노드(null또는 NIL 노드)는 블랙입니다.
네번째로 레드 노드의 자식은 언제나 블랙입니다. 즉 레드 노드가 연속으로 등장할수 없습니다.
마지막으로 모든 노드에 대해 해당 노드로부터 자손인 리프 노드에 이르는 모든 경로에는 동일한 개수의 블랙 노드가 있습니다.
또한 특성에 대해 조금더 설명드리자면, 루트 노드부터 리프노드까지의 모든 경로 중 최소 경로와 최대 경로의 크기비율은 2보다 크지 않습니다.(ex: 검검검, 검빨검빨 ....)
이러한 상태를 balanced 상태라고 합니다.
그리고 노드의 자식이 없는 경우, 자식 노드를 가리키는 포인터에 NIL 값을 저장하고 이를 리프노드이며, 검정색으로 간주하여 규칙(마지막 규칙)을 유지하게 됩니다.

삽입 연산시에는 값을 삽입하다보면 Double Red가 발생할수있습니다.(일반적으로 삽입되는 노드는 레드 생각으로 설정)
이때 엉클노드 즉 부모의 형제노드가 검정이면 Restructing, 빨강이면 Recoloring을 진행하게 됩니다.
Restrucing은 현재 인서트된 노드, 그 노드의 부모노드, 조부모 노드를 가지고 진행합니다.
이때 세 노드를 오름차순으로 정렬 후, 가운데 값을 부모로 만들고 나머지 둘을 자식으로 하게됩니다.
이후 가운데 값을 검정, 나머지 두 자식을 빨강색으로 하게됩니다.
이는 다른 서브트리에 영향을 끼치지 않아 한번에 Restrucint이면 끝나게 됩니다.(이러한 연산 진행 시 더블레드 해결 전후의 black 노드의 갯수 변화가 없으므로)
또한 자체 시간 복잡도는 O(1)에 끝나지만(순서 결정 - 상수, 트리로 만드는- 상수, 노드 구조바꾸기 - 상수) 어디에 삽입될지 위치를 찾아야 하므로 수행시간은 O(log N)입니다.
리 컬러링은 현재 인서트된 노드의 부모와 그 형제를 검정으로 하고 조부모를 빨강으로 합니다.
이때 조부모가 루트노드가 아니고, 서브트리인 경우 더블레드가 발생할 수 있기에 여러번 진행 될 수 있습니다.
연산 자체는 O(1)이지만, root까지 연산이 계속될수 있기에 최악의 경우 log(N)입니다. 이러한 규칙을 통해 레드-블랙 트리는 삽입,삭제 연산이 일어날때 트리의 균형을 유지하게 됩니다.

삭제의 경우에는 그 노드가 레드 색상일 경우는 제거해도 균형 규칙을 위반하지 않기에 간단히 삭제해도됩니다.
그러나 삭제 노드가 블랙인 경우에는 균형을 재조정해야합니다. 블랙 노드를 삭제하면 그 경로에 있는 블랙 노드 숫자가 줄어들어 규칙에 위반하기 때문입니다.
이를 위해 삭제된 블랙 노드의 자리를 차지하는 노드의 색을 블랙으로 변경합니다.
그런데 이때 새로운 노드가 이미 블랙이였다면,이중 흑색 노드가 되어 따로 처리를 해야 합니다.
이때 형제 노드가 레드 노드이면, 형제 노드를 블랙, 부모 노드를 레드로 변경후, 부모 중심으로 왼쪽 회전을 합니다.
형제노드가 블랙이고, 형제 양쪽 자식이 모두 블랙인 경우, 이중 블랙 노드에서 블랙하나를 제거하고, 형제 노드를 레드로 변경한 후, 부모 노드에 블랙을 추가합니다.
형제 노드가 블랙이고, 형제 노드의 왼쪽 자식은 레드, 오른쪽 블랙인 경우, 형제 노드를 레드로, 형제 노드의 왼쪽 자식을 블랙으로 변경후, 형제 노드 중심으로 오른쪽 회전합니다.
형제 노드가 블랙이고, 형제 노드의 오른쪽 자식은 레드인 경우, 부모 노드의 색을 형제에게 넘기고, 부모는 검, 형제 노드의 오른쪽 자식은 검으로변경 후 부모 기준 좌회전을 합니다.
이러한 삭제 연산은 O(log N)의 시간복잡도를 가집니다.
왜냐하면 레드 블랙트리는 균형 이진 탐색 트리의 한종류이기에, 높이가 log N을넘지 않습니다.
삭제 연산은 탐색,삭제 및 앞서 말한 밸런싱 과정을 거치는데, 탐색 및 삭제는 log N의 시간복잡도를 가지며, 재 균형화 작업은 상수 시간 복잡도(루트 까지 반복되는 경우 이또한 log(N)를 가집니다.
따라서 삭제 연산의 시간복잡도는 O(log N)입니다.

참고 - 리컬러링에서 부모랑 엉클을 검정으로막 바꿔도되나? - 바꿔도 black depth는 일제히 1 증가하기에 문제 없습니다.

트리와 그래프에 대해 설명해주세요.

둘다 복잡한 객체 간의 관계를 표현하는데 사용하는 자료구조입니다.
트리는 계층적인 구조를 가지는 그래프의 일종입니다.
트리는 루트 노드라 불리는 최상위 노드가 존재하며, 그 아래로 다수의 자식 노드가 붙어있는 형태입니다
즉 부모 노드에서 자식 노드로의 방향성이 있습니다.
이러한 트리는 사이클이 없습니다.즉 어떤 노드에서 출발하여 자신으로 다시 돌아오는 경로가 존재하지 않습나.
그리고 두 노드를 잇는 경로는 유일하다는 특징을 가집니다.
반면 그래프는 트리보다 더 일반적인 구조를 가집니다.
그래프는 노드(or 정점:vertex)와 이들을 연결하는 간선으로 구성됩니다.(간선은 방향성을 가질수도 가지지 않을수도)
요약하자면, 모든 트리는 그래프이지만, 모든 그래프가 트리인것은 아닙니다.
트리는 순환없이 연결된 그래프의 특별한 형태로, 계층적인 구조를 가지나, 그래프는 좀더 일반적인 집합으로, 순환이나 다중 경로를 포함할 수 있습니다.

참고 - 트리 용어 정리
노드 : 트리의 핵심적인 구성 요소로, 정보를 저장, 그래프의 꼭짓점
루트 : 트리의 가장 상위에 위치하는 노드로, 부모 노드가 없는 최상위노드
자식 : 어떤 노드 아래, 부모 : 어떤 노드 위
자손 노드 : 어떤 노드에서 리프 노드에 이르는 경로에 포함된 모든 노드
조상 노드 : 루트 노드에서 어떤 노드에 이르는 경로에 포함된 모든 노드
Leaf Node,Terminal Node : 자식 없는 노드
내부 노드(Internal Node : 중간노드) : 루트 노드나 리프 노드가 아닌 로드
간선 : 노드와 노드 연결하는 선
형제 : 같은 부모를 가지는 노드를 형제 노드 라고함
레벨 : 트리에서 루트 노드가 위치한 곳을 레벨0이라고 하고, 아래로 갈수록 1씩 증가
깊이(depth) : 자신을 제외한 조상 노드의 갯수
높이 : 트리의 높이는 루트 노드에서 가장 멀리 떨어지느 노드의 레벨 : 트리의 최대 레벨
노드의 높이 : 해당 node가 리프 노드면 0이며, 해당 노드의 자식들의 height 중 가장 높은값 + 1
차수 : 트리의 노드가 가지고 있는 자식의 노드 수를 의미

트리를 순회하는 방법에 대해 아시는대로 설명해주세요.

트리를 순회하는 방법에는 주로 전위(inOrder)순회, 중위 순회(inorder), 후위 순회(post-order)가 있습니다.
이 방법들 모두 트리의 모든 노드를 한번씩 방문하지만, 방문하는 순서에서 차이를 보입니다.
전위 순회란 루트 노드를 먼저 방문하고, 그다음 왼쪽 서브트리를, 마지막으로 오른쪽 서브트리를 순회합니다.
중위 순회는 왼쪽 서브트리를 먼저 순회하고, 그다음 루트 노드를 방문 한 후, 마지막으로 오른쪽 서브트리를 순회합니다.
후위 순회는 왼쪽 서브트리를 먼저 순회하고, 그다음 오른쪽 서브트리를 순회한후, 마지막으로 루트 노드를 방문합니다.
이 외에도 level-order 순회가 있습니다. 이는 트리의 노드를 레벨 순서대로, 각 레벨내에서는 왼쪽에서 오른쪽으로 방문합니다.(보통 큐로)

HashTable과 HashMap 무엇인지 말씀해주세요.

HashTable이란 키-값 쌍으로 데이터를 저장하는 자료구조중 하나입니다.해시 충돌이 발생하지 않은 경우 데이터의 조회, 삽입, 삭제 등의 작업을 상수시간(충돌시:O(N))에 처리할 수 있어 자주 사용하는 자료구조입니다. HashTable의 핵심 원리는 Hashing입니다. 해싱을 통해 키를 바탕으로 값을 빠르게 찾을 수 있습니다.
이러한 해싱시에는 다른 값임에도 같은 해시 값을 가지게 되는 해시 충돌이 발생할 수 있습니다.
자바에서는 hash를 사용하는 collection들의 해시 충돌을 해결하기 위해 체이닝 방법을 사용합니다.(임계점 넘으면 리해싱도 진행)
즉 open Address 방식과 같이 다른 공간을 찾아 저장하는 것이 아니라, 해당 버킷에 LinkedList를 추가하여 충돌을 처리합니다.
이러한 해시테이블은 HashMap과 동기화 지원 여부 및 null값 허용 여부에서 차이를 보입니다.
HashMap에서는 null값을 허용하지만 HashTable은 null키나 값이 있으면 NPE를 던집니다.
또한 HashMap은 동기화 처리가 되어있지 않아 멀티 스레드 환경에서 사용할 때 Thread Safe 하지 않은 반면, HashTable은 자체적으로 동기화 기능을 제공하기에, 멀티 스레드 환경에서도 안정적으로 사용할 수 있습니다.
하지만 단일 스레드 환경에서는 동기화가 필요없기에 HashMap이 HashTable보다 더 빠른 성능을 제공합니다.
동기화를 위한 오버헤드가 발생하지 않으며, 자바 8이후로 HashMap은 LinkedList의 크기가 임계값을 넘으면 밸런스 트리로 바꾸는 변경사항을 적용하여 성능이 더욱 향상되었습니다(O(n) -> O(log N).

꼬리질문1 - 그렇다면 멀티쓰레드 상황에서는 HashTable을 사용하는 것이 가장 바람직한가요?
HashTable은 메서드가 동기화 되어있으므로, 한번에 하나의 쓰레드만이 HashTable의 메서드를 사용할 수 있습니다.
이는 공유 자원에 대한 동시 엑세스를 방지하지만 성능에 대한 오버헤드가 발생합니다.
하지만 ConcurrentHashMap은 HashTable과 달리 내부적으로 여러개의 bucket(segment)를 가지며, 각 Segment별로 잠금 처리가 되어 동시에 여러 스레드가 작업을 수행할 수 있습니다.(해시 테이블 개선 버전)
즉, ConcurrentHashMap은 동시에 여러 스레드가 데이터를 읽거나 쓸 수 있도록 허용하므로, 동시성 환경에서 성능 향상을 가져옵니다.
따라서 동시성 환경이라면 HashTable 보다 ConcurrentHashMap을 사용하는 것이 성능적으로 더 좋습니다.

참고 - 멀티스레드 환경이지만 동시에 매우 적은 수의 스레드만 접근한다면 hashtable이나 hashmap이 더 작합할 수 있음


꼬리질문2 - 결국 데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌 나는 현상이 발생하는데도 해시 테이블을 사용하는 이유는 무엇인가요?

먼저, 데이터의 양이 증가하면서 해시 충돌의 가능성이 증가하는 상황에서도 해시 테이블이 유용한 이유는, 여전히 평균적으로 빠른 조회 속도를 제공하기 때문입니다
물론, 해시 충돌이 발생하면 성능이 저하될 수 있지만, 이러한 충돌을 최소화하는 해시 함수의 선택과 충돌이 발생했을 때 이를 해결하는 기법(예: 체이닝 또는 개방주소법 등)을 통해 성능 저하를 최소화할 수 있습니다.
두 번째로, 해시 테이블은 크기가 제한된 공간에서 효율적인 데이터 관리를 가능하게 합니다. 즉, 용량이 큰 데이터 집합을 상대적으로 작은 공간에 매핑하여, 공간 효율성을 극대화합니다. 이는 데이터베이스 시스템, 캐시 메모리와 같이 공간의 제약이 있는 상황에서 매우 중요한 특성입니다
결국, 해시 테이블의 선택은 데이터의 양, 공간 효율성, 그리고 성능 사이에서의 트레이드오프를 고려해 결정됩니다. 충돌의 가능성에도 불구하고, 해시 테이블은 이러한 여러 요소를 적절히 조합하여 매우 효율적인 데이터 구조를 제공하기 때문에 널리 사용되고 있는 것입니다

참고 - 예를들어 10만개의 데이터가 있고,이중 john이라는 이름을 가진 사람을 찾고 싶다고 하자.
배열에서 john을 찾기 위해서는, 첫번째 부터 마지막 요소까지 하나하나 확인(O(N))
반면 해시테이블에서는 John이라는 키가 이미 저장되어있으며, 해당 키에 대응하는 값을 해시 함수를 통해 계산된 인덱스에 저장되어있음.
따라서 즉시 해당 값을 찾아낼 수 있다. 즉 둘의 차이는 값을 어떻게 찾느냐에 따라 다르다.

꼬리질문3 - 동기화된 자료구조란 무엇인가요?
이것은 멀티스레드환경에서 안전하게 사용할 수 있는 자료구조입니다.
멀티스레드 환경에서 여러 개의 스레드가 동시에 접근하면 데이터 불일치가 발생할 수 있습니다.이를 위해 동기화된 자료구조를 사용합니다.
동기화된 자료구조는 일반적으로 락이라는 동기화 기술을 사용하여 여러 스레드가 동시에 접근할 수 없도록 막습니다.
하지만 동기화된 자료구조를 사용하면 락을 획득하고 반납하는 과정에서 오버헤드가 발생하므로, 성능에 영향을 미칩니다.
따라서 가능하면 스레드 안전하지 않은 자료구조를 사용하는 것이 좋을 수 잇찌만, 이 경우에는 스레드간 접근을 제어하기 위한 다른 방법을 사용해야합니다.

참고
hashmap - 삽입(평균 1, 최악의 경우 logn(자바8 이후)), 조회(평균 1: 최악의 경우 log n)), 삭제(1, log n)
hashtable - 삽입(평균 1, 최악의 경우 n), 조회 삭제 다 같음
linkedHashMap : hashmap과 같음
TreeMap : 삽입,조회,삭제 (log n)

LinkedHashMap과 TreeMap에 대해 설명해주세요.

LinkedHashMap은 순서를 고려하는 HashMap의 확장형입니다. 기본적인 HashMap의 특성을 가지면서도, 원소들이 추가된 순서에 따라 이중 연결 리스트로 연결되어 있습니다
이 특성 덕분에 입력 순서가 중요한 상황에서, 예를 들어 최근에 입력된 원소에 빠르게 접근하거나 원소를 순차적으로 처리해야 하는 상황에 적합합니다.
하지만, 이런 순서 정보를 저장하기 위해 추가적인 메모리를 사용하므로, 공간 효율성이 중요한 상황에서는 주의해야 합니다.
반면에 TreeMap은 키-값 쌍을 Red-Black 트리 구조로 저장하는 구현체입니다. 이 트리의 균형 유지 속성 때문에, 삽입, 조회, 삭제 연산에 O(log N)의 시간 복잡도를 가집니다.
특히, TreeMap은 키를 기준으로 자동 정렬하는 기능을 제공하므로, 키에 따른 순서가 중요한 상황에서 유용하게 사용될 수 있습니다. 다만, TreeMap은 동기화를 지원하지 않으므로, 멀티 스레드 환경에서 사용할 때는 주의해야 합니다.

LinkedHashSet에 아시는 대로 설명해주세요.

linkedHashSet은 HashSet의 서브클래스로, 입력 순서에 따라 요소를 저장합니다.
이는 HashSet과 달리 내부적으로 이중 연결 리스트를 유지하기 때문입니다.
그 외에는 HashSet과 유사하게 중복된 요소를 허용하지 않고, equals()와 hashCode() 메서드를 통해 동일성을 결정합니다.

참고 - 노드 내부에 다음 노드와 이전 노드를 가리키는 변수가 있다.