알고리즘

해시 (Hash)

키를 해시 함수로 변환해 O(1) 평균 시간에 검색·삽입·삭제를 수행하는 자료구조. 충돌 처리 전략이 성능의 핵심이다.

핵심 포인트

• 충돌 해결: 체이닝(연결 리스트) vs 개방 주소법(선형 탐사 등)
• 해시 함수의 균등 분포가 성능을 결정
• JS Map/Set, Python dict/set 은 모두 해시 기반
• 대표 문제: 두 수의 합(O(n)), 중복 탐지, 빈도 카운팅