12-2 (고급 탐색 구조: 해싱)

해싱: 해시 함수에 문자열 입력값을 넣어 특정한 값으로 추출하는 것.

해시함수: 해싱에서 킷값으로부터 레코드가 저장될 위치를 계산하는 함수

해시 테이블: 해시 함수에 의해 계산된 위치에 레코드를 저장한 테이블

 

ex) 탐색키가 모두 1~1000사이의 정수라고 가정하면 가장 빠르게 탐색할 수 있는 방법은 1000개의 항목을 가지는 배열을 만드는 것임. 자료의 삽입과 탐색은 탐색키를 인덱스로 생각하고 그 위치에 저장하거나 읽어오면 됨.

이 경우의 해쉬 함수는 h(key)=key가 됨. 시간복잡도는 O(1)임. 

그러나 만약 탐색키가 문자열이거나 실수, 또는 굉장히 큰 정수면 메모리가 부족해진다. 이 경우 탐색키를 더 이상 직접 배열의 인덱스로 사용할 수 없고, 대신에 탐색키를 작은 정수로 대응시키는 해시 함수가  필요함.

 

해시함수는 탐색키를 입력받아 해시주소를 계산하는데, 삽입/삭제/탐색 연산은 모두 이 주소에서 이뤄짐.

 

해싱의 구조: 해시 테이블은 M개의 버킷으로 이루어지는 테이블이고, 하나의 버킷은 여러 개의 슬롯을 가짐. 하나의 슬롯에는 하나의 레코드가 저장된다.

킷값 key가 입력되면 해시 함수로 연산한 결과 k(key)가 해시주소가 되고 이를 인덱스를 사용하여 항목에 접근하게 됨.

버킷이 충분하지 않으면 경우에 따라 서로 다른 키가 해시함수에 의해 같은 주소로 계산되는 상황이 발생.

=> 충돌, 충돌을 일으키는 키들을 동의어라고 함.

 

ex) h(홍길동)=>3, h(이순신)=>2, h(장영실)=>5, h(임꺽정)=>3

그 결과 '홍길동'과 '임꺽정'이 같은 주소로 계산되어 충돌이 발생함. <동의어>

이런 경우에는 만약 버킷에 여러 개의 슬롯이 있다면 서로 다른 슬롯에 저장하면 됨. 그러나 충돌이 슬롯 수보다 더 많이 발생할 수 있는데, 이런 상황을 오버플로우라고 함.