Hashing이란?
대부분의 탐색 방법들은 탐색 키를 저장된 키 값과 반복적으로 비교하면서 탐색을 원하는 항목에 접근합니다. 반면 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근합니다. 이렇게 키 값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블이라 부르며, 해시 테이블을 이용한 탐색을 해싱(Hashing)이라 합니다.
Hashing이 나온 이유?
Hashing이 나오게 된 배경은 위에서 설명한 시간복잡도 보다 더욱 빠른 탐색을 필요로 할 때입니다. Hashing은 이론적으로 의 시간 안에 탐색을 끝마칠 수도 있습니다. Hashing은 보통 사전과 같은 자료 구조를 구현할 때에 최상의 선택이 됩니다.
사전 구조
사전 구조는 맵이나 테이블로 불리기도 합니다. 사전 구조는 다음과 같이 탐색 키, 그리고 탐색 키와 관련 있는 값 이렇게 2가지 종류의 필드를 가집니다.
-
영어 단어나 사람의 이름같은 탐색 키
-
단어의 정의나 주소 또는 전화 번호와 같은 탐색 키와 관련된 값
사전 구조에서는 유일한 탐색 키를 사용하기도 하고 동일한 탐색 키를 허용하기도 합니다. 예를 들면, 주민등록번호에 의하여 학생들을 관리하느 ㄴ사전 구조는 유일한 탐색키를 사용하는 경우입니다. 그러나 영어 사전의 경우 철자가 동일한 단어가 많은 의미를 가질 수 있기 때문에 중복되는 탐색키를 사용합니다.
Hashing의 구조
Hashing에서는 자룔를 저장하는 데 배열을 사용합니다. 배열은 원하는 항목이 저장된 위치르 ㄹ알고 있을 경우 매우 빠르게 자료를 삽입하거나 꺼낼 수 있습니다. 리스트와 같이 저장된 위치를 찾기 위해 다음 노드로 옮기는 등의 작업이 전혀 없으므로 시간복잡도는 매우 빠릅니다. Hashing이란 어떤 항목의 탐색키만을 가지고 바로 항목이 저장되어 있는 배열의 인덱스를 결정하는 기법입니다.
