해시테이블

해시테이블(Hash Table)은 키-값 쌍을 $O(1)$에 저장하고 검색하는 자료구조입니다.

해시 함수

$$h(key) = key \mod m$$

키를 배열 인덱스로 변환합니다. 좋은 해시 함수는 충돌을 최소화합니다.

충돌 해결

체이닝 (Chaining)

같은 인덱스에 연결리스트로 저장. 연결리스트 활용.

개방 주소법 (Open Addressing)

충돌 시 다음 빈 슬롯을 찾음. 선형 탐사, 이차 탐사 등.

Python의 dict

Python의 딕셔너리가 바로 해시테이블입니다. 이미 매일 쓰고 있었다는 사실