핵심 답변

해시 테이블은 키(Key)를 해시 함수에 넣어 얻은 버킷 인덱스(Hash 값)에 대응하는 원소를 저장하는 자료구조로, O(1)의 평균 탐색 속도를 갖습니다. 서로 다른 키가 동일한 해시 값을 갖는 해시 충돌(Collision)이 발생할 수 있는데, 이를 해결하기 위해 해시 버킷에 연결 리스트를 다는 체이닝(Chaining) 방식과, 비어있는 다른 슬롯을 찾아 저장하는 개방 주소법(Open Addressing - 선형탐사, 제곱탐사 등) 방식이 자주 쓰입니다.

꼬리 질문

• Q. Java의 HashMap은 해시 충돌을 어떤 방식으로 해결하나요?
  • A: 기본적으로 체이닝(Separate Chaining) 방식을 사용합니다. Java 8부터는 하나의 버킷 안에 충돌 노드의 수가 특정 임계치(8개)를 넘어가면 연결 리스트 구조를 레드-블랙 트리(Red-Black Tree)로 변환해 O(N)의 최악의 탐색 시간을 O(logN)으로 최적화합니다.

핵심 답변

배열(Array)은 연속된 메모리 공간에 무조건 데이터가 순차적으로 할당되므로 인덱스를 통한 원소 임의 접근 속도(O(1))가 매우 빠릅니다. 반면 리스트(Linked List)는 내부 노드들의 포인터로 연결되므로 흩어진 메모리에 존재하며, 탐색에는 약하지만(O(N)) 원소들의 중간 및 맨 뒤의 삽입과 삭제가 효율적입니다.

꼬리 질문

• Q. 배열은 크기를 어떻게 변경하나요?
  • A: 정적 배열은 선언 시점에 크기가 결정되어 변경할 수 없습니다. 따라서 만약 크기를 확장하려면, 더 큰 용량의 새 배열을 할당하고 기존 배열 요소들을 모조리 복사(Copy)하는 재할당 작업을 수행해야 합니다.

핵심 답변

가장 핵심적이고 결정적인 차이는 '중복 요소 허용' 여부와 '순서 보장' 유무입니다. List는 값이 언제 들어왔는지 인덱스라는 메모리 주소 순서를 엄격히 유지하며 내부 중복 요소를 무제한으로 허용합니다. 반면 Set은 들어온 순서도 무시하고 값이 중복되면 아예 덮어씌워서 배제하는 집합(Set) 수학 모델을 그대로 따르는 자료구조입니다.

꼬리 질문

• Q. Java의 HashSet에서 요소를 검색하는데 걸리는 시간과 그 원리는 무엇인가요?
  • A: 거의 단 번에 해시 맵처럼 탐색하므로 평균적으로 O(1)이 소요됩니다. 실제 내부 소스코드를 까보면 단순히 HashMap의 위임 객체 껍데기에 불과하며 Map의 Key 슬롯을 값으로 사용하여 동일 해시가 겹치지 않는 HashMap의 강력한 특성을 이용합니다.

핵심 답변

Java를 예로 들면, ArrayList는 내부에 동적 배열을 가지고 데이터를 관리하므로 끝점 추가 O(1), 인덱스 조회에 빠른 조회가 가능합니다. 대신 요소 수가 꽉 차면 더 큰 배열을 만들어 복사해 이사합니다. 반면 LinkedList는 이중 연결 리스트로 구현되어 있어 노드들의 포인터 연결 정보만 바꾸는 삽입/삭제 작업이 중간 및 양쪽 끝에서 O(1) 수준으로 빠릅니다.

꼬리 질문

• Q. 그러면 중간 삽입/삭제를 위해 LinkedList를 무조건 이용하는 것이 좋은가요?
  • A: 아닙니다. LinkedList의 '삽입 O(1)'은 삽입할 노드의 위치를 정확히 알고 있을 경우에 한정되며, 보통 위치를 찾기 위한 탐색 O(N) 비용이 먼저 들기 때문에 실제론 CPU 캐시 적중률(Cache hit)이 월등히 뛰어난 연속된 배열 ArrayList를 주로 권장합니다.

핵심 답변

Stack은 맨 마지막에 넣은 요소가 맨 먼저 나오는 LIFO(후입선출) 구조이며, 함수 호출 스택, 뒤로가기 버튼, 괄호 검사 등에 쓰입니다. Queue는 줄서기처럼 맨 처음에 넣은 요소가 먼저 방출되는 FIFO(선입선출) 구조로 대기열, 프린터 대기열 및 BFS 탐색 알고리즘에 활용됩니다.

꼬리 질문

• Q. 스레드 풀, 또는 요청이 순간적으로 늘어날 땐 스택과 큐 중에 무엇을 앞단에 배치하나요?
  • A: 사용자 요청의 공정성 및 순차 처리를 위해 큐(Queue), 특히 메모리를 고려한 워크 큐 혹은 메시지 큐(Message Queue, Kafka 등) 아키텍처를 도입하여 순차적으로 해소하는 패턴을 사용합니다.

핵심 답변

HashMap은 Key와 Value의 매핑 구조를 저장합니다. 들어온 Key 객체의 hashCode() 반환값을 이용해 버킷 인덱스를 계산하고 배열에 값을 할당합니다. 하나의 인덱스 칸(버킷) 안에 원소는 내부적으로 노드 연결 리스트(또는 해시 충돌시 레드-블랙 트리)를 이용해 엮이는 체이닝기법 기반의 Node 배열 구조를 가집니다.

꼬리 질문

• Q. HashMap의 Load Factor(임계 시간)란 무엇이고, 초과시 어떤 일이 일어나나요?
  • A: Load Factor는 전체 버킷 해시 슬롯 배열 중 얼마나 요소가 채워지면 배열 용량을 재할당할지를 결정하는 비율(기본 0.75)입니다. 이를 초과하면 HashMap은 버킷 배열의 길이를 2배로 확장(Re-hashing)하여 해시 충돌 확률을 낮춥니다.

핵심 답변

서로 다른 키인데 해시 알고리즘 연산 결과가 동일한 인덱스를 가리키는 충돌 현상에 대비하기 위해 두 기법이 쓰입니다.

1. Chaining (체이닝): 충돌난 슬롯에 링크드 리스트를 이어 붙여 줄줄이 저장하기
2. Open Addressing (개방 주소법): 충돌이 난 버킷을 버리고 일정 패턴(선형 탐사 등)으로 남의 빈 버킷에 무단으로 찾아가 값을 집어넣기.

꼬리 질문

• Q. Java의 HashMap은 충돌 해결을 위해 어떤 방식을 사용하나요?
  • A: 체이닝 구조를 채택했습니다. 나아가 자바 8버전 부터는 한 체인 버킷의 리스트 원소 수가 8개 이상 도달하면 단순 링크드 리스트 구조를 레드-블랙 트리로 전환하여 선형 검색 시간복잡도를 줄이도록 최적화되었습니다.

핵심 답변

Tree는 계층형 비순환 그래프로 최상단 루트, 자식 부모 관계로 이루어집니다. 종류로는,

1. 자식 노드가 2개 이하인 이진 트리(Binary Tree)
2. 부모보다 왼쪽 자식이 작고 우측은 큰 이진 탐색 트리(BST)
3. 극단적 한쪽 편향을 막아 스스로 균형을 맞추는 자기 균형 이진 탐색 트리 AVL / Red-Black 트리
4. 최소/최댓값 빠른 탐색을 위해 우선순위를 부여한 완전 이진 트리인 Heap 등이 있습니다.

꼬리 질문

• Q. 데이터베이스 인덱스가 Red-Black 트리 대신 B-Tree(B+Tree)를 주로 사용하는 이유는?
  • A: 이진 트리는 하나의 노드에 자식이 둘 뿐이라 데이터 양이 방대해지면 트리 깊이(디스크 참조 횟수) 폭주가 일어납니다. 반면 B-Tree계열은 한 노드에 자식을 여러 개(Block) 두고 넓게 구성하여 메모리 페이지 참조 횟수를 구조적으로 대폭 줄여줍니다.

핵심 답변

이진 트리는 각 부모 노드가 '최대 2개의 자식(왼쪽, 오른쪽)'만 가질 수 있다는 규칙만 있는 구조입니다. 이진 탐색 트리는 거기에 추가적인 탐색 규칙을 적용한 것으로, 부모 노드를 기준으로 왼쪽 서브 트리에 있는 모든 값은 부모보다 작고, 오른쪽 서브 트리는 항상 부모보다 큰 값을 지녀야 한다는 속성이 부여됩니다.

꼬리 질문

• Q. 이진 탐색 트리에 데이터가 순서대로 (예: 1, 2, 3, 4, 5) 삽입될 경우 문제는 무엇인가요?
  • A: 구조가 한쪽으로 일렬 편향(기울어짐)하여 연결 리스트와 구조가 다를 바 없어지므로, 시간 복잡도가 O(log N)이 아닌 배열 탐색과 같은 O(N)으로 퇴화하게 됩니다.

핵심 답변

힙은 최댓값 혹은 최솟값을 가장 빠르게 단번 구하기 위해 만들어진 자료구조로, 내부적으로 반듯한 이진 트리의 틀을 갖춘 완전 이진 트리(Complete Binary Tree) 모델을 지니고 있습니다. 부모 노드가 무조건 자식 노드보다 항상 크거나(Max Heap) 무조건 작도록(Min Heap) 유지되는 게 특징입니다. 루트가 언제나 최대/최소를 보장해 O(1)에 알 수 있으며 삽입 제거는 스왑 원리로 인해 O(log N)이 소모됩니다.

꼬리 질문

• Q. 힙 삽입 연산 원리에 대해 간단히 말해주세요
  • A: 먼저 트리 최하단 맨 끝 빈자리에 새 노드를 던져 넣은 뒤, 부모가 나보다 나약하다면 스왑(Shift up)하며 정상 균형 구조를 찾을 때까지 거슬러 상승합니다.

핵심 답변

Red-Black 트리는 BST 연산 시 자칫 막대기처럼 O(N)으로 편향 퇴화할 수 있는 문제를 극복하기 위해 스스로 균형을 맞추는 자기 균형 이진 탐색 트리 입니다. 모든 노드는 빨간색 혹은 검은색의 비트 상태를 부여받아 4가지 고유의 서브 트리 컬러 제약 규칙을 준수하며, 위배될 경우 회전(Rotation)을 이용해 트리의 양단 깊이 균형을 물리적으로 강제 맞춤으로써 무조건 탐색, 조작 O(log N)을 보장합니다.

꼬리 질문

• Q. 자바의 TreeMap 및 C++의 map, set이 구현체로 레드블랙 트리를 쓰는 이유가 뭔가요?
  • A: 조회 및 입력 최악이 모두 확고하게 O(log N)으로 안정적이기 때문에 대량의 원소를 안전하게 정렬 상태로 관리해야할 때 최적의 성능을 냅니다.