에듀테크 프로젝트 대시보드
해시테이블 (Hash Table)
키를 해시 함수로 변환해 배열 인덱스에 저장 · 평균 O(1) 탐색의 비밀
해시테이블은 키(key)를 해시 함수(hash function)에 넣어 나온 정수값을
버킷(bucket) 배열의 인덱스로 바꾸어 값을 저장하는 자료구조입니다.
배열처럼 인덱스로 바로 접근하기 때문에 데이터가 아무리 많아도 평균적으로
O(1) 시간에 탐색·삽입·삭제가 가능합니다. Python의 dict,
JavaScript의 Object/Map이 내부적으로 해시테이블을 사용합니다.
문자열을 입력하면 각 문자의 아스키 코드 합을 버킷 개수(8)로
나눈 나머지가 저장 위치가 됩니다. 같은 인덱스에 여러 키가 몰리면 충돌(collision)이
발생하고, 이를 연결리스트로 이어 붙이는 방식을 체이닝(chaining)이라 합니다.
데이터 개수가 늘어날수록 배열/연결리스트는 선형 탐색 비용이 커지지만, 해시테이블은 거의 일정합니다.
| 자료구조 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|
| 배열 (정렬 안 됨) | O(n) | O(1) | O(n) |
| 연결리스트 | O(n) | O(1) | O(n) |
| 이진 탐색 트리 | O(log n) | O(log n) | O(log n) |
| 해시테이블 | O(1) | O(1) | O(1) |