알고리즘
Hash Table
다른 이름: 해시 테이블 , HashMap , HashSet , dict
정의
키-값 쌍 저장 자료구조. 해시 함수로 키→인덱스 변환, 평균 O(1) 검색/삽입/삭제. 충돌 해결: Chaining(연결 리스트), Open Addressing(선형 탐사). Load Factor(적재율) 0.75 넘으면 리사이징. Python dict, C++ unordered_map, Java HashMap
상세 설명
기술 스펙
- 평균 시간복잡도: O(1) - 검색, 삽입, 삭제
- 최악 시간복잡도: O(n) - 모든 키가 충돌 시
- 공간복잡도: O(n)
- 해시 함수: 키 → 정수 (0 ~ table_size-1)
- Chaining: 같은 인덱스는 연결 리스트
- Open Addressing: 빈 슬롯 찾기 (선형, 이차, 이중 해싱)
- Load Factor: n/m (n=원소 수, m=테이블 크기), 0.75 넘으면 resize
- Rehashing: 테이블 크기 2배로 확장 후 재삽입
실무 활용
- 빠른 검색: 사용자 ID → 프로필 정보
- 중복 제거: Set으로 중복 체크
- 빈도 계산: 단어 개수 세기
- 캐시: LRU Cache (HashMap + LinkedList)
- 백준: 1620 (나는야 포켓몬 마스터), 17219 (비밀번호 찾기)
장점
- 매우 빠름: 평균 O(1) 검색
- 유연성: 모든 타입 키 가능 (해시 가능하면)
- 동적 크기: 자동 리사이징
- 메모리 효율: 배열 대비 공간 절약
단점 및 제약
- 충돌 처리: 해시 함수 품질 중요
- 순서 없음: 삽입 순서 보장 안 함 (LinkedHashMap 사용)
- 최악 O(n): 모든 키 충돌 시
- 리사이징 비용: O(n) 재해싱
호환성
Python dict, C++ unordered_map, Java HashMap, JavaScript Map/Object
표준 정보
표준화 기구: 자료구조 교과서 표준. Donald Knuth
출시 연도: 1953년