코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
자료구조 — 효율적인 데이터 관리의 핵심 → 기초 자료구조
hash("apple") → 3 → table[3] = "사과"
hash("banana") → 7 → table[7] = "바나나"
// 검색: hash("apple") → 3 → table[3] = "사과" — O(1)!
연산 복잡도:
| 연산 | 평균 | 최악 |
|------|------|------|
| 검색 | O(1) | O(n) |
| 삽입 | O(1) | O(n) |
| 삭제 | O(1) | O(n) |
왜 최악이 O(n)?
모든 키가 같은 인덱스로 해시되면 (충돌) → 하나의 리스트가 됨 → O(n)
하지만 좋은 해시 함수를 쓰면 이런 일은 거의 발생하지 않습니다.
실생활의 해시 테이블:
- JavaScript: Object, Map
- Python: dict
- Java: HashMap
- DB: 해시 인덱스여러분, 오늘은 자료구조의 핵심 중의 핵심, 해시 테이블을 배워보겠습니다.
해시 테이블은 키를 값에 매핑하는 자료구조인데요, 평균 O(1)에 모든 연산이 가능해요.
그림 왼쪽을 보세요, 문자열 키들이 있죠.
이 키들이 가운데 해시 함수를 거쳐서 숫자 인덱스로 변환됩니다.
해시 함수는 임의의 데이터를 고정된 크기의 정수로 바꿔주는 마법 같은 함수예요.
예를 들어 apple이라는 키는 해시 함수를 거치면 인덱스 3이 되고요.
banana는 인덱스 7이 되고, cherry는 1, date는 5가 됩니다.
그림 오른쪽의 배열을 보시면, 각 인덱스 위치에 키-값 쌍이 저장되어 있어요.
이게 바로 해시 테이블의 핵심 원리입니다.
검색할 때도 똑같이 해시 함수를 적용하면 바로 위치를 알 수 있어요.
배열 인덱스로 직접 접근하니까 O(1)인 거죠, 정말 빠르죠?
그림 왼쪽 아래의 복잡도 상자를 보세요.
검색, 삽입, 삭제 모두 평균 O(1)이라고 적혀 있어요.
하지만 최악의 경우에는 O(n)이 될 수도 있는데, 이건 나중에 충돌을 배울 때 알아볼게요.
실생활에서 해시 테이블은 어디에 쓰일까요?
Python의 딕셔너리, JavaScript의 Object와 Map이 모두 해시 테이블이에요.
데이터베이스의 인덱싱, 캐시, 심볼 테이블도 해시 테이블을 사용합니다.
연락처 앱에서 이름으로 전화번호를 찾는 것도 해시 테이블의 원리와 같아요.
배열은 인덱스로만 O(1) 접근이 가능하지만, 해시 테이블은 키로 O(1) 접근이 가능해요.
이것이 바로 해시 테이블이 가장 많이 사용되는 자료구조인 이유입니다.
다음 블록에서는 이 마법의 핵심인 해시 함수를 더 깊이 파헤쳐 보겠습니다.