해싱함수

목차

Report1 : 103 page의 해싱함수중 나눗셈 방법의 정리와 예제
▶ 해싱의정의
▶ 해싱의 필요성
▶ 정적 해싱
▶ 해싱 테이블(hashing table)
▶ 해싱의 문제점
▶ 해싱 함수(hashing function)
▶ 나눗셈 방법(제산방법=division)

Report2 : 107 page.
(1) 두 다항식을 배열로 나타내어 이들을 곱하는 C프로그램을 작성하시오.
(2) 위 프로그램의 시간 복잡도는 얼마인가?

본문내용

▶ 해싱의정의
여러개의 명칭(identifier)들이 무작위로 들어있는 테이블에서 특정 명칭을 찾고자 하는 경우 원하는 키 값을 가지는 테이블 항목을 검색하기 위해 특정한 변환 함수를 이용하여 키 값을 항목의 주소로 직접 바꿔서 검색하는 방법을 '해싱(Hashing)' 혹은 '분산 기억법(Scatter Storage Technique)'이라고 하는데, 실제적으로 가장 빠른 탐색을 제공한다.
이 방법이 빠른 검색을 제공하는 이유는 단순하다. 즉, 검색할 자료가 보다 잘 정리가 되어 있기때문이다. 다시 말하면, 데이터의 값에 따라 저장되어야 할 공간이 미리 지정되어 있기 때문이다. 이 방법에서 자료의 값에 따라 저장할 공간을 결정하는 함수를 '해싱함수'(hashing function)라고 한다.

▶ 해싱의 필요성
명칭 테이블에서 키 값과 일치하는 명칭을 찾는 방법으로는 테이블에 있는 각각의 명칭을 키 값과 차례로 비교하는 방법이 있다.
이 방법을 사용하면 최악의 경우 n회의 비교가 필요하다. 해싱을 이용하면 해싱 함수가 키 값을 해당 주소로 단번에 변환해 주므로 매우 빠른 검색이 가능하다.

참고 자료

없음