해싱

본 포스팅은 SW Expert Academy의 ‘SW 문제해결 응용’ 강의를 듣고 공부하며 정리한 노트입니다.

해싱이란?

특정 항목 검색 시, 탐색 키에 대한 산술적 연산으로 키가 있는 위치를 계산하여 바로 찾아가는 방법

해시 테이블

직접 번지 테이블보다 메모리 공간이 적게 필요하다. 키 값 k의 자료를 저장할 위치를 계산하는 해시 함수(h)를 사용한다. 키 값이 k인 자료를 h(k)의 위치에 저장한다. h(k)는 키 값 k의 해시값이라고 한다.

충돌

키 두 개가 동일한 위치가 되는 상황을 충돌이라 한다. 해시 함수가 해시 주소를 공평하게 분배해도 해시 테이블에 저장되는 키에 해당하는 자료의 수가 증가하면 충돌은 불가피하다. 충돌의 해결 방법에는 체이닝과 개방 주소법이 있다.

체이닝

해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키 값을 가지는 자료가 저장될 수 있도록 하는 방법

개방 주소법

해시 함수로 구한 주소에 빈 공간이 없어 충돌이 발생하면 그 다음 위치에 공간이 있는지 조사하는 방법