이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 자료구조 — 효율적인 데이터 관리의 핵심 → 자료구조 — 효율적인 데이터 관리의 핵심 → 기초 자료구조
Hash function design, collision resolution (chaining/open addressing), load factor, rehashing, O(1) analysis, HashMap implementation, and applications.
hash("apple") → 3 → table[3] = "사과"여러분, 오늘은 자료구조의 핵심 중의 핵심, 해시 테이블을 배워보겠습니다.
해시 테이블은 키를 값에 매핑하는 자료구조인데요, 평균 O(1)에 모든 연산이 가능해요.
그림 왼쪽을 보세요, 문자열 키들이 있죠.
이 키들이 가운데 해시 함수를 거쳐서 숫자 인덱스로 변환됩니다.
해시 함수는 임의의 데이터를 고정된 크기의 정수로 바꿔주는 마법 같은 함수예요.
예를 들어 apple이라는 키는 해시 함수를 거치면 인덱스 3이 되고요.
banana는 인덱스 7이 되고, cherry는 1, date는 5가 됩니다.
그림 오른쪽의 배열을 보시면, 각 인덱스 위치에 키-값 쌍이 저장되어 있어요.
이게 바로 해시 테이블의 핵심 원리입니다.
검색할 때도 똑같이 해시 함수를 적용하면 바로 위치를 알 수 있어요.
배열 인덱스로 직접 접근하니까 O(1)인 거죠, 정말 빠르죠?
그림 왼쪽 아래의 복잡도 상자를 보세요.
검색, 삽입, 삭제 모두 평균 O(1)이라고 적혀 있어요.
하지만 최악의 경우에는 O(n)이 될 수도 있는데, 이건 나중에 충돌을 배울 때 알아볼게요.
실생활에서 해시 테이블은 어디에 쓰일까요?
Python의 딕셔너리, JavaScript의 Object와 Map이 모두 해시 테이블이에요.
데이터베이스의 인덱싱, 캐시, 심볼 테이블도 해시 테이블을 사용합니다.
연락처 앱에서 이름으로 전화번호를 찾는 것도 해시 테이블의 원리와 같아요.
배열은 인덱스로만 O(1) 접근이 가능하지만, 해시 테이블은 키로 O(1) 접근이 가능해요.
이것이 바로 해시 테이블이 가장 많이 사용되는 자료구조인 이유입니다.
다음 블록에서는 이 마법의 핵심인 해시 함수를 더 깊이 파헤쳐 보겠습니다.
선생님: 배열은 인덱스 번호로 O(1) 접근이 가능한데, 해시 테이블은 뭐가 다를까요?
학생: 배열은 숫자 인덱스만 가능하지만, 해시 테이블은 문자열 같은 키로도 O(1) 접근이 가능해요!
선생님: 맞아요! 그러면 해시 테이블이 O(1)을 달성하는 비결은 뭘까요?
학생: 해시 함수가 키를 숫자 인덱스로 변환해서 배열처럼 직접 접근하는 거예요.
선생님: 정확해요. 그런데 만약 두 개의 키가 같은 인덱스로 변환되면 어떻게 될까요?
학생: 그게 충돌인데, 체이닝이나 개방 주소법으로 해결한다고 들었어요.
선생님: 아주 잘 알고 있네요! 충돌 해결은 이후 블록에서 자세히 배울 거예요.