CS Fundamentals

해시 테이블에 대해서 설명해주세요

O(1) 탐색의 비밀 — 해시 함수, 충돌 해결(체이닝 vs 개방 주소법), Java HashMap 내부 구조까지 인터랙티브 시각화로 완전 정복합니다.

2026년 3월 19일 · 약 12분 읽기

Q. "해시 테이블의 동작 원리를 설명하고, 충돌이 발생하면 어떻게 해결하는지 말씀해주세요."

예상 꼬리질문

답변 가이드

"해시 테이블은 키를 해시 함수에 넣어 산출된 인덱스에 값을 저장하는 자료구조입니다. 해시 함수가 키를 배열 인덱스로 변환하므로 평균 O(1)에 삽입, 탐색, 삭제가 가능합니다."

"서로 다른 키가 같은 인덱스로 매핑되는 충돌(Collision)은 피할 수 없습니다. 체이닝(Separate Chaining)은 같은 인덱스에 연결 리스트를 연결하고, 개방 주소법(Open Addressing)은 빈 슬롯을 탐사합니다. Java HashMap은 체이닝을 사용하며, 체인 길이가 8 이상이면 레드-블랙 트리로 변환합니다."

"적재율(Load Factor)이 0.75를 넘으면 배열을 2배로 확장하고 모든 항목을 재해싱(Rehashing)합니다. 키로 사용하는 객체는 반드시 hashCode()와 equals()를 함께 오버라이드해야 합니다."

면접에서 "HashMap의 시간 복잡도가 왜 O(1)인지 설명해주세요"라는 질문은 해시 테이블의 동작 원리를 정확히 이해하고 있는지 확인하는 것입니다.

해시 함수가 키를 어떻게 변환하고, 충돌을 어떻게 해결하는지 인터랙티브 시각화로 직접 체험하며 준비해 보겠습니다.

1. 해시 함수 — 키를 인덱스로 변환하기

꼬리질문: "해시 함수는 어떤 역할을 하고, 좋은 해시 함수의 조건은 무엇인가요?"

해시 테이블의 핵심은 해시 함수(Hash Function)입니다. 임의의 키를 고정 크기 정수(해시 코드)로 변환한 뒤, 나머지 연산으로 배열 인덱스를 결정합니다.

키를 입력하면 해시 함수가 어떻게 인덱스를 결정하는지 확인하세요.

해시 함수 동작 시각화

키를 입력하면 해시 함수가 배열 인덱스로 변환하는 과정을 확인하세요.

0
1
2
3
4
5
6
7

해시 함수: hash = (hash * 31 + charCode) — Java String의 hashCode()와 동일한 알고리즘

2. 충돌 해결 — 체이닝 vs 개방 주소법

꼬리질문: "체이닝과 개방 주소법의 차이를 설명해주세요"

서로 다른 키가 같은 인덱스로 매핑되는 충돌(Collision)은 반드시 발생합니다. 체이닝은 연결 리스트로 같은 버킷에 여러 항목을 저장하고, 선형 탐사는 빈 슬롯을 찾아 이동합니다.

항목을 추가하며 충돌이 어떻게 해결되는지 비교하세요.

충돌 해결: 체이닝 vs 선형 탐사

항목을 추가하며 충돌이 어떻게 해결되는지 비교하세요.

0
1
2
3
4
5
6
7
0/6

3. 적재율과 리사이징

꼬리질문: "Java HashMap의 내부 구조와 리사이징 과정을 설명해주세요"

적재율(Load Factor = 항목 수 / 배열 크기)이 높아지면 충돌 확률이 급증합니다. Java HashMap은 적재율 0.75를 임계값으로, 이를 초과하면 배열을 2배로 확장하고 모든 항목을 재해싱합니다.

항목을 추가하며 적재율 변화와 리사이징을 관찰하세요.

적재율과 리사이징 시뮬레이터

항목을 추가하며 적재율이 0.75를 넘으면 자동 리사이징을 확인하세요.

항목 수

0

배열 크기

4

임계값

3

적재율(Load Factor)0.00
0.75

4. hashCode()와 equals() 계약

꼬리질문: "hashCode()와 equals()의 관계는 무엇인가요?"

Java에서 HashMap을 올바르게 사용하려면 hashCode()와 equals()를 함께 오버라이드해야 합니다. equals()가 true인 두 객체는 반드시 같은 hashCode를 가져야 합니다.

올바른 구현과 위반 케이스의 차이를 확인하세요.

hashCode()와 equals() 계약

올바른 구현과 위반 케이스의 차이를 확인하세요.

// hashCode()와 equals() 모두 오버라이드

class Person {

String name; int age;

@Override equals() { name + age 비교 }

@Override hashCode() { name + age 기반 }

}

put(new Person("Kim", 25), "개발자")

hashCode()=1234 → 버킷[4]에 저장

get(new Person("Kim", 25))

자주 발생하는 문제

퀴즈로 확인하기

개념을 제대로 이해했는지 확인해 보세요.

1 / 3현재 점수: 0점
Case 1: 최악의 시간복잡도
해시 테이블에 n개의 키가 모두 같은 인덱스로 해싱되었다.
탐색의 시간복잡도는?

면접 체크리스트

이 항목들을 자신 있게 설명할 수 있다면 해시 테이블 질문은 준비 완료입니다.

  • - 해시 함수: 키 → 해시 코드 → 나머지 연산 → 배열 인덱스
  • - 충돌 해결: 체이닝(연결 리스트/트리) vs 개방 주소법(선형 탐사)
  • - 적재율: 0.75 초과 시 2배 확장 + 재해싱
  • - Java 8+ 트리화: 체인 길이 8 이상 시 레드-블랙 트리로 변환
  • - hashCode-equals 계약: equals가 true이면 hashCode도 같아야 한다
  • - 시간복잡도: 평균 O(1), 최악 O(n)

참고 자료

의견을 들려주세요

서비스 개선에 큰 도움이 됩니다. 익명으로 자유롭게 남겨주세요.

0 / 1000