[자료구조] 해시 테이블 예상 질문

1. 해시테이블은 무엇인가요?

• 키를 해시 함수로 변환하여 배열 인덱스에 값을 저장하는 자료구조로, 복잡도는 평균 O(1)입니다.

2. 해시 테이블의 기본 동작 원리를 설명해보세요.

• 키를 해시 함수에 넣어서 인덱스를 얻고, 해당 인덱스를 가진 배열 위치에 데이터를 저장/조회합니다.

3. 배열과 해시 테이블의 차이는 무엇인가요?

• 배열은 인덱스로만 값에 접근이 가능하지만, 해시 테이블은 키를 해시 값으로 변환하여 접근 가능합니다.

4. 해시 충돌에 대해 설명해주세요.

• 해시 충돌이란 여러 데이터들이 같은 해시 값을 갖는 것을 뜻합니다. 해시 충돌이 일어나면 특정 해시에 데이터가 집중되며 너무 많은 해시 충돌은 해시 테이블의 성능을 떨어뜨립니다. 해시충돌을 해결하는 방법은 체이닝와 오픈 어드레싱이 있습니다.

5. 해시 충돌이 발생하면 어떻게 해결할 수 있나요?

체이닝과 오픈어드레싱으로 해결할 수 있습니다.
체이닝은 하나의 버킷에 연결리스트나 트리를 추가하여 데이터를 저장하는 방법이고,
오픈 어드레싱은 버켓을 탐사하여 빈 공간을 찾고, 빈 공간에 데이터를 저장하는 방법입니다.
오픈 어드레싱은 충돌이 나면 다음칸을 확인하는 선형 탐사와 1칸, 4칸, 9칸 등 떨어진 곳을 탐색하는 이차 탐사, 다른 해시 함수를 한번 더 적용하는 더블해싱이 있습니다.

6. 체이닝과 오픈 어드레싱의 장단점을 비교해주세요.

체이닝의 장점으로는 구현이 간단하며 삭제가 쉽고, 확장 시 충돌 관리에 유연합니다. 단점으로는 포인터나 리스트/트리로 인해 메모리가 추가 소모되며 캐시 효율이 떨어집니다.
오픈 어드레싱의 장점으로는 추가 자료구조가 필요 없으며, 캐시 친화적입니다. 단점으로는 삭제가 복잡하며 Load Factor가 커지면 성능이 급격히 나빠지며 클러스터링 문제로 성능 저하 가능성이 있습니다.

7. 해시 충돌이 발생하면 성능이 어떻게 되나요?

평균 O(1)이지만 충돌이 심하면 최악 O(n)입니다. 체이닝에서는 연결리스트 탐색, 오픈 어드레싱에서는 탐사 비용이 증가합니다.

8. 해시 테이블의 평균 시간 복잡도와 최악 시간 복잡도는 어떻게 되나요?

삽입/삭제/검색 모두 평균 O(1), 최악 O(n)

9. Load Factor란 무엇인가요?

Load Factor는 적재율을 뜻하며, 버킷에 저장된 원소수를 버킷 개수로 나눈 것을 의미합니다.
적재율이 1이 가까울수록 충돌 확률이 커지며, 탐색시간이 늘어나게 됩니다.

10. 해시 함수(Hash Function)는 어떤 특성을 가져야 좋은 함수인가요?

• 균등성(값이 고르게 분포), 결정성(같은 입력은 같은 해시값), 효율성(빠르게 계산 가능), 낮은 충돌률

11. 데이터베이스 인덱스와 해시 테이블은 어떤 차이가 있나요?

• 해시 테이블은 메모리에 적합하며 평균 O(1). 범위검색이 불가능합니다.
• 데이터베이스 인덱스는 디스크 I/O에 최적화되어 있으며 평균O(log n). 범위검색이 가능합니다.
  DB는 범위 검색때문에 주로 트리구조 인덱스를 사용합니다.

12. 실제 백엔드 서비스에서 해시 테이블을 활용한 사례를 설명해보세요.

1. 세션 저장

• 사용자 로그인 시 sessionId → sessionData 매핑.
• 세션 조회 시 O(1)에 가까운 속도로 탐색 가능.

2. 캐시

• Redis 같은 인메모리 DB는 내부적으로 해시 테이블을 활용.

3. 로드 밸런싱

• 분산 서버에 요청을 나눌 때, 키를 해시값으로 바꿔 특정 서버에 매핑.
• 서버 추가/삭제 시에도 최소한의 재배치만 발생.

13. 해시 테이블에서 메모리 효율이 중요한 이유는 무엇인가요?

• 충돌을 줄이려고 큰 배열을 잡으면 메모리가 낭비되고, 반대로 너무 너무 작으면 충돌이 많아져 성능이 저하되기 때문입니다.