이중 해싱3 [알고리즘] ep4+++) 비활성화 방식 삭제 문제) 크기가 M인 해시테이블에 키 값을 입력받아 저장하고, 개방주소법 중 이중 해싱을 이용하여 충돌을 처리하는 해시테이블 프로그램을 작성하시오. [프로그램 요구사항]1) 해시테이블의 사이즈 M = 23 으로 정의할 것. 2) 이중해싱에 기반해야 하며 h 및 h’은 각자 적절히 정의하여 사용할 것. 3) 저장 원소는 0에서 99 사이의 정수로 제한할 것. 4) 삽입(i) 명령시, 중복 키 또는 해시테이블이 만원일 경우 적절한 안내 메시지와 함께 명령수행을 거절할 것. 5) 탐색(f) 또는 삭제(r) 명령시, 함께 주어진 키가 존재하지 않을 경우 NoSuchKey를 반환 및 인쇄할 것. [주의]인쇄(p) 명령시에만, 아래 예시처럼 현재 해시테이블의 내용을 두 개의 라인으로 보여줄 것. 윗 라인은.. 2024. 7. 19. [알고리즘] ep4++) 개방주소법 구현(선형 조사, 이중 해싱) 문제1) 크기 M인 해시테이블에 n개의 키 값을 입력받아 저장하고, 개방주소법 중 선형조사법을 이용하여 충돌을 처리하는 해시테이블 프로그램을 작성하시오. [구현 조건]- 해시테이블은 크기가 M인 배열로 동적 할당한다.- n은 M보다 작은 자연수로 최대 삽입 개수다.- 입력 키는 중복이 없는 6자리 또는 8자리의 임의의 자연수(학번)다. - 키 x에 대한 해시함수 h(x) = x % M 을 사용한다.- 저장된 키 값이 없는 빈 버켓은 0으로 처리한다. [입력]- 해시테이블의 크기 M과 입력 데이터의 크기 n을 입력받는다.- 삽입(i), 탐색(s) 명령어를 순서에 상관없이 반복하여 입력받는다. i x> : 키 x를 해시테이블에 삽입s x> : 키 x가 해시테이블에 존재하는지 탐색 e : 프로그램 종료 [출.. 2024. 7. 19. [알고리즘] ep4) 해시테이블(hashtable) 선형검색에 반해 해시테이블의 검색시간은 평균적으로 상수시간이다 (사전에 삽입된 모든 키가 충돌하는 최악의 경우는 O(n))해시테이블의 상수시간이 가능한 이유는 "해시함수"를 통해 바로 접근하기 때문이다ㅁ해시테이블(hashtable): 버켓배열 + 해시함수(key, address) 맵핑에 의해 구현된 사전 ADT※ key-value는 키와 값을 직접 연결하는 방식이라면, key-address는 키가 실제 데이터의 위치(주소)를 가리키는 방식 e.g. 컴파일러의 심볼 테이블, 환경변수들의 레지스트리, 소규모 DB, 브라우저 캐시 ㅇ버켓배열(bucket array) = 테이블 버켓을 슬롯(slot)이라고도 한다 ㅇ해시함수(hash fucntion): 맵핑하는 역할e.g. h(x) = x % Mh(x)는 정.. 2024. 7. 18. 이전 1 다음
