여러개의 식별자(identifier)들이 무작위로 들어있는 테이블에서 특정 명칭을 찾고자 하는 경우 원하는 키 값을 가지는 테이블 항목을 검색하기 위해 특정한 변환 함수를 이용하여 키 값을 항목의 주소로 직접 바꿔서 검색하는 방법을 해싱(Hashing)이라고 하는데, 실제적으로 가장 빠른 탐색을 제공한다.
해싱이 빠른 검색을 제공하는 이유는 단순하다. 즉, 검색할 자료가 보다 잘 정리가 되어 있기때문이다. 다시 말하면, 데이터의 값에 따라 저장되어야 할 공간이 미리 지정되어 있기 때문이다. 해싱에서 데이터의 값에 따라 저장할 공간을 결정하는 함수를 해싱함수(hashing function)라고 한다. 이 해싱 함수에 의해서 데이터가 저장될 공간이 정해지므로 O(1)의 복잡도로 탐색할 버킷을 찾을 수 있다.
체인법은 정적 해싱에서의 오버플로를 처리하기 위해 좋은 성능을 보이는 기법이다. 체인법을 사용하면 식별자끼리의 비교를 피할 수 있다는 장점이 있다. 아래 그림은 체인법을 사용 하였을 경우의 해싱 테이블과 그 연결 리스트를 보여주는 그림이다.
체인법을 이용한 정적 해싱 구조
아래의 파일은 체인법을 사용하여 정적 해싱을 구현한 소스 코드이다.
Hashing_Static.c
이올린에 북마크하기
이올린에 추천하기
TRACKBACK 0 AND
COMMENT 2
PREV
