해싱을 이용하여 학번과 학생이름을 삽입하고 검색하고 수정하고 삭제하는 프로그램

소개

해싱을 이용하여 학번과 학생이름을 삽입하고 검색하고 수정하고 삭제하는 프로그램을 만든다.

목차

없음

본문내용

개요
해싱을 이용하여 학번과 학생이름을 삽입하고 검색하고 수정하고 삭제하는 프로그램을 만든다.
해싱은 하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것이다. 짧은 해시 키를 사용하여 항목을 찾으면 원래의 값을 이용하여 찾는 것보다 더 빠르기 때문에 해싱은 데이터베이스 내의 항목들을 색인하고 검색하는데 사용된다.
또한 해싱에 의해 정렬된 이름들 각각은 데이터베이스 내에서 개인들 데이터의 키가 될 수 있다. 데이터 베이스 검색 수법은 일치하는 것이 먼저 발견될 때까지 각 이름들을 글자단위로 확인하기 시작해야만 한다. 그러나, 만약 이름들 각각이 해시된다면 각 이름별로 4자리의 고유한 키를 생성하는 것이 가능해진다.


사용된 기법
해싱 체이닝 기법을 사용하였다. 체이닝은 오버플로우 문제를 해시테이블의 구조변경을 통해 연결리스트로 해결하는 방법이다. 즉, 각 버켓에 고정된 슬롯을 할당하는 것이 아니라 각 버켓에, 삽입과 삭제가 용이한 연결리스트를 할당한다. 버켓 내에서는 원하는 항목을 찾을때 연결리스트를 순차 탐색하면 된다. 해시테이블은 한개의 노드를 가리킬수 있는 포인터 배열로 선언하고, 탐색 키가 버켓으로 들어올 경우 먼저 동적으로 메모리를 할당하여 연결리스트의 노드를 생성한 다음, 이 새로운 노드에 탐색키를 복사한다.다음 단계로 버켓에 연결되어 있는 기존의 연결리스트에서 동일한 탐색 키가 있는지를 검사한다.만약 동일한 탐색 키가 발견되면 오류 메시지를 출력하고 복귀한다. 동일한 탐색 키가 없으면 연결리스트의 맨 끝에 새로운 탐색키를 포함하는 새로운 노드를 연결한다. 만약 기존의 연결리스트가 없으면 해시테이블의 포인터에 새로운 노드를 연결한다.체이닝에서 항목을 탐색하거나 삽입하고자 하면 키 값의 버켓에 해당하는 연결리스트에서 독립적으로 탐색이나 삽입이 이루어진다. 체이닝은 해시 테이블을 연결리스트로 구성하므로 필요한 만큼의 메모리만 사용하게 되어 공간적 사용 효율이 매우 우수하다. 또한 오버플로우가 발생할 경우에도 해당 버켓에 할당된 연결리스트만 처리하게 되므로 수행 시간면에서도 매우 효율적이다.

참고자료

· 없음